2023年7月19日发(作者：)

第6-7章

一．选择/填空

001、设图G的邻接矩阵为101001010，则G的边数为( D )．

10A．5 B．6 C．3 D．4

2、设有向图（a）、（b）、（c）与（d）如下图所示，则下列结论成立的是( A )．

A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的

3、给定无向图G如下图所示，下面给出的结点集子集中，不是点割集的为（ B ）．

A．{b, d} B．{d}

C．{a, c} D．{b, e}

4、图G如下图所示，以下说法正确的是 ( D ) ．

A．{(a, c)}是割边

B．{(a, c)}是边割集

C．{(b, c)}是边割集

D．{(a, c) ,(b, c)}是边割集

5、无向图G存在欧拉通路，当且仅当(D )．

A．G中所有结点的度数全为偶数

B．G中至多有两个奇数度结点

C．G连通且所有结点的度数全为偶数

D．G连通且至多有两个奇数度结点

6、设G是有n个结点，m条边的连通图，必须删去G的( A )条边，才能确定G的一棵生成树．

1 A．m−n+1 B．m−n C．m+n+1 D．n−m+1

7、已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为（B ）．

A．8 B．5 C．4 D．3

8、已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 15 ．

9、连通无向图G有6个顶点9条边，从G中删去 4 条边才有可能得到G的一棵生成树T．

10、如右图 相对于完全图K5的补图为（A ）。

G=

11、给定无向图，如下图所示，下面哪个边集不是其边割集（ B

A、{,}；

B、{,};

C、{,}；

D、{,}。

12、设D是有n个结点的有向完全图,则图D的边数为( A )

(A)n(n−1) (B)n(n+1) (C)n(n+1)/2 (D)n(n−1)/2

13、无向图G是欧拉图,当且仅当( C )

(A) G的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数

(C)G连通且所有结点的度数都是偶数 (D) G连通且G的所有结点度数都是奇数。

14、n阶完全图Kn的边数为 。

12n(n−1)；

15、右图 的邻接矩阵A= 。

2

。 ）0000101101011100；

16、任何(n,m) 图G = (V,E) , 边数与顶点度数的关系是 。

∑d(v)=2mv∈V

17、当n为 时,非平凡无向完全图Kn是欧拉图。

奇数

18、已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,

则T中有 个1度顶点。

答案： 5

19、下面四组数能构成无向图的度数列的有( B )。

A、 2,3,4,5,6,7； B、 1,2,2,3,4；

C、 2,1,1,1,2； D、 3,3,5,6,0。

20、图 的邻接矩阵为( C )。

1011A、0110000001111110；B、111111111111；C、0011；D、111000000110。

21、下列图中是欧拉图的有( A )。

22、下面给出的集合中，哪一个是前缀码？( （2） )

(1) {0，10，110，101111} (2) {01，001，000，1}

3 (3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}

23、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ （4） ）。

(1) 5 (2) 7 (3) 8 (4) 9

24、下图中既不是Eular图，也不是Hamilton图的图是（ B ）

25、一棵无向树的顶点数n与边数m关系是( m=n-1 )。

26、有n个结点的树，其结点度数之和是( 2n-2 )。

27、下面给出的集合中，哪一个不是前缀码( (1) )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}

(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}

28、n个结点的有向完全图边数是( n(n-1) )，每个结点的度数是( 2n-2 )。

29、设G是一棵树，n,m分别表示顶点数和边数，则（ （3） ）

(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

30、任何连通无向图G至少有( 1 )棵生成树。

31、设无向图G有16条边且每个顶点的度数都是2，则图G有( （4） )个顶点。

(1) 10 (2) 4 (3) 8 (4) 16

32、任一有向图中，度数为奇数的结点有( 偶数 )个。

33、在有n个顶点的连通图中，其边数（ （2） ）。

(1) 最多有n-1条 (2) 至少有n-1 条

(3) 最多有n条 (4) 至少有n 条

34、在如下各图中（ B ）欧拉图。

二．综合题

1、设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试

4 (1) 给出G的图形表示； (2) 写出其邻接矩阵；

(3) 求出每个结点的度数； (4) 画出其补图的图形．

解：(1) G的图形如下

001

10(3)v1度数为1，v2度数为2，v3度数为4，v4度数为3，v5度数为2

00(2)G=101101(4)其补图的图形如下

2、图G=，其中V={a, b, c, d, e, f }，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f) }，对应边的权值依次为5，2，1，2，6，1，9，3及8．

(1) 画出G的图形； (2) 写出G的邻接矩阵；

(3) 求出G权最小的生成树及其权值．

解：(1) G的图形如下

011(2)G=010

110100011000010

1001111101001105 (3)最小生成树是{(a,e),(e,c),(b,d),(d,f), (a,b)}权值为1+1+2+3+5=12

3、已知带权图G如右图所示．

(1) 求图G的最小生成树； (2)计算该生成树的权值．

解：(1)最小生成树为{1,3,2,7,5}

(2)权值为1+2+3+5+7=18

4、设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．

解：(1) 相应的最优二叉树图如下

(2)由图得到最优二叉树的权为：131

6 5、已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。

解：D的邻接距阵A和可达距阵P如下：

A=

0 1 0 1 0

0 0 1 0 0

0 0 0 1 1

0 0 0 0 0

1 0 0 0 0

P=

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

0 0 0 0 0

1 1 1 1 1

6、求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树为

权＝148

7、有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种药品？

解：用n个结点表示n个药箱，当两种药箱放一种相同药时，则对应的两点连一条边，则得到一个1n(n−1)无向完全图，因而所求药品数即为该图边数=2。

8、如下图所示的赋权图表示某七个城市v1,v2,,v7及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。

解： 用库斯克（Kruskal）算法求产生的最优树。算法为：

7 w(v1,v7)=1选e1=v1v7w(v7,v2)=4选e2=v7v2w(v7,v3)=9选e3=v7v3w(v3,v4)=3选e=v3v4w(v4,v5)=17选e=v4v5w(v1,v6)=23选e=v1v6

结果如图：

树权C(T)=23+1+4+9+3+17=57（万元）即为总造价

9、无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问结点？

解：∵G（V,E），| E |=V，d（Vi）<3,

设至少有x个节点，由握手定理得：

2×12=∑d（Vi）<6×3+(x-6)×3

2<(x-6) =＞ x>8

故G中至少有9个节点。

10、求下面两个图的最小生成树。

8

G中至少有多少个11、若一个有向图G是欧拉图，它是否一定是强连通的？若一个有向图G是强连通的，它是否一定是欧拉图？说明理由。

答：（1）一个有向欧拉图一定是强连通图。因为G是欧拉图，存在欧拉回路C，G中的每个结点至少在C中出现一次。因而G中任意两点u，v都在C中，相互可达，故G是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。

12、 有向图G如图3-1所示。

（1）求G的邻接矩阵A；

（2）G中v1到v4长度为4的路径有几条？

（3）G中v1到自身长度为3的回路有几条？

（4）G是哪类连通图？

1

1 4

4

6

7

3

2

5 3

2

图3-1

解：

10（1）A=00210100102

A=00100100231100013

A=01000011004

A=1001

014=4可知，v1到v4长度为4的路径有条（e1e1e4e6，e4e6e7e6，e1e2e5e6，e1e3e5e6）。

（2）由A4中a143=1可知，v1到自身长度为3的回路有1条（e1e1e1）（3）由A3中a11。

（4）G是单向连通图。

13、设图G如图1所示，

(1) 求G的邻接矩阵A；

(2) 求A(2),A(3),A(4)，说明从v1到v4的长为2,3,4的路径各有几条；

(3) 求G的可达矩阵P；

9 00答案. (1)

G的邻接矩阵A=0000=0010；

101010202022022000(4)；A=0200242202；

040202(2)

A(2)1010(3)；A=0010从v1到v4的长为2,3,4的路径的条数分别为1,2,2；

(3)

G的可达矩阵为

；

14、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。

答案：

15、设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。

10 答案：.令e1=(v1,v3), e2=(v4,v6)

e3=(v2,v5), e4=(v3,v6)

e5=(v2,v3), e6=(v1,v2)

e7=(v1,v4), e8=(v4,v3)

e9=(v3,v5), e10=(v5,v6)

令ai为ei上的权，则

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，

T的总权和=1+2+3+4+5=15

16(没学，不用做！)、一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?

答案：.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。

∀Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知∀vi,vj∈V有d(vi)+d(vj)≥20,于是G中存在汉密尔顿回路。

设C=Vi1Vi2…Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。

17、设有如下有向图G=，

（1）求G的邻接矩阵；

（2）G中v1到v4的长度为4 的通路有多少条？

（3）G中经过v1的长度为3 的回路有多少条？

（4）G中长度不超过4 的通路有多少条？其中有多少条回路？

解：

11 11（1） A=0011021010，A2=0001010032213A=0000121111

010001425331，A4=001100374243

010001（2） G中v1到v4的长度为4 的通路有4条；

（3） G中经过v1的长度为3 的回路有3条；

（4） G中长度不超过4 的通路有72条，其中有19条回路。

18、如下图所示的赋权图表示某七个城市v1,v2,,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。

解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：

树权C(T)=23+1+4+9+3+17=57即为总造价。

19、在通讯中，八进制数字出现的频率如下：

0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%

求传输它们最佳前缀码（写出求解过程）。

解：用100乘各频率并由小到大排列得权数

w1=5,w2=5,w3=5,w4=10,w5=10,w6=15,w7=20,w8=30

（1） 用Huffman算法求最优二叉树：

12 （2） 前缀码

用 00000传送 5；00001传送 6；0001传送 7；100传送 3；101传送 4；001传送 2；11传送 1；01传送 0 （频率越高传送的前缀码越短）。

补充习题：

课后习题：

第6章：6.5，6.24，6.27，6.35

第7章：7.8, 7.9，7.19，7.20， 7.27，7.28，7.29，7.30

答案：

第6章 图

13

14

第7章 树

15

16