离散数学图论部分综合练习

离散数学图论部分综合练习

本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是图论部分的综合练习。

一、单项选择题

1．设图G的邻接矩阵为

??01100?011?

?10??10000??

?01001????01010??则G的边数为( )．

A．6 B．5 C．4

2．已知图G的邻接矩阵为

，

则G有（ ）．

A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边

3．设图G＝，则下列结论成立的是 ( )．

A．deg(V)=2?E? B．deg(V)=?E? C．?deg(v)?2E D．V?deg(v)?E

v?v?V4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集 D．{(a, d) ,(a, c)}是边割集

5．如图二所示，以下说法正确的是 ( )． A．e是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集

6．如图三所示，以下说法正确的是 ( ) ．

1 D．3 a? ?b ?d ? f

?c ?

e

图一

图二

A．{(a, e)}是割边 B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集

图三

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

图四

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

C．（c）是强连通的 D．（d）是强连通的 应该填写：D

8．设完全图Kn有n个结点(n≥2)，m条边，当（ ）时，Kn中存在欧拉回路．

A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数 9．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 10．无向图G存在欧拉通路，当且仅当( )． A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点

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

A．m?n?1 B．m?n C．m?n?1 D．n?m?1 12．无向简单图G是棵树，当且仅当( )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路．

二、填空题

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

2

2．设给定图G(如图四所示)，则图G的点割 集是 ．

3．若图G=中具有一条汉密尔顿回路， 则对于结点集V的每个非空子集S，在G中删除S 中的所有结点得到的连通分支数为W，则S中结点 数|S|与W满足的关系式为 ．

a? f ? e ? b

? ? c ?d

4．无向图G存在欧拉回路，当且仅当G连通 图四

且 ．

5．设有向图D为欧拉图，则图D中每个结点的入度 ． 应该填写：等于出度

6．设完全图Kn有n个结点(n?2)，m条边，当 时，Kn中存在欧拉回路．

7．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式 ．

8．设连通平面图G的结点数为5，边数为6，则面数为 ． 9．结点数v与边数e满足 关系的无向连通图就是树．

10．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 条边后使之变成树．

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

12．设G＝是有6个结点，8条边的连通图，则从G中删去 条边，可以确定图G的一棵生成树．

13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码．

三、判断说明题

1．如图六所示的图G存在一条欧拉回路．

v1 a v2 e v5 f h b 图六

d g v4 n v3 c

2．给定两个图G1，G2（如图七所示）：

（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．

3

v1

v6

v4

v5

v2

v3

v1 ? v6 ? ? v5

v? 2

? v3

? v4

图八

图七

3．判别图G(如图八所示)是不是平面图， 并说明理由．

4．设G是一个有6个结点14条边的连 通图，则G为平面图．

四、计算题

1．设图G??V，E?，其中V??a1, a2, a3, a4, a5?,

E???a1, a2?，?a2, a4?，?a3, a1?，?a4, a5?，?a5, a2??

（1）试给出G的图形表示； （2）求G的邻接矩阵；

（3）判断图G是强连通图、单侧连通图还是弱连通图？

2．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，试

（1）画出G的图形表示； （2）写出其邻接矩阵； （2）求出每个结点的度数； （4）画出图G的补图的图形． 3．设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试

（1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形．

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

（1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

5．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试

（1）画出相应的最优二叉树； （2）计算它们的权值． 6．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它的权．

五、证明题

1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的． 2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的

4

补图G中的奇数度顶点个数相等．

3．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．

参考解答

一、单项选择题

1．B 2．D 3．C 4．C 5．A 6．D 7．D 8．C 9．A 10．D 11．A 12．A

二、填空题

1．15 2．{f}，{c，e} 3．W?|S| 4．所有结点的度数全为偶数 5．等于出度 6．n为奇数 7．v-e+r =2 8．3 9．e=v-1 10．4 11．5

12．3 13．0

三、判断说明题

1．解：正确．

因为图G为连通的，且其中每个顶点的度数为偶数． 2．解：（1）图G1是欧拉图． 因为图G1中每个结点的度数都是偶数．

图G2是汉密尔顿图．

因为图G2存在一条汉密尔顿回路（不惟一）： a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a

问题：请大家想一想，为什么图G1不是汉密尔顿图，图G2不是欧拉图。

（2）图G1的欧拉回路为：（不惟一）：

v1(v1, v2) v2 (v2, v3) v3 (v3, v4) v4 (v4, v5)v5 (v5, v2) v2 (v2, v6)v6 (v6, v4) v4 (v4, v1)v1 3．解：图G是平面图．

因为只要把结点v2与v6的连线(v2, v6)拽 到结点v1的外面，把把结点v3与v6的连线 (v3, v6)拽到结点v4, v5的外面，就得到一个平 面图，如图九所示．

5

k条边才能2v1 ? v6 ? ? v5

v? 2

? v3

? v4 图九

4．解：错误．

不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”

四、计算题

1．解：（1）图G是有向图： （2）邻接矩阵如下：

a2 ? a?3 ??010(D)??0A??10a4 ? ?a

5 ?a ?001

??01（3）图G是单侧连通图，也是弱连通图． 2．解：（1）图G如图十

v?1

v2 ? ? v5

? ?

v 3

v4 （2）邻接矩阵为 图十

??01100?10110? ????11011?

?01101????00110??（3）deg(v1)=2

deg(v2)=3 deg(v3)=4 deg(v4)=3

v?1 deg(v5)=2

v2 ? ? v5

（4）补图如图十一 v?

?3

v

4 图十一 3．解：（1）G的图形如图十二

（2）邻接矩阵： 图十二

6 000?010?000??,

001??000??

?00100??00110????11011? ??01101????00110??（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2

（4）补图如图十三：

图十三 4．解：（1）G的图形表示如图十四：

图十四 （2）邻接矩阵：

?011?100??100??011??11101?11??11?

?01?10??（3）粗线表示最小的生成树，如图十五

如图十五 最小的生成树的权为1+1+2+3=7：

7

5．解：（1）最优二叉树如图十六所示： 方法（Huffman）：从2,3,5,7,11,13,17 ,19,23,29,31中选2,3为最低层结点，并 从权数中删去，再添上他们的和数，即 5,5,7,11,13,17,19,23,29,31；

65 ? 160

? ? 95

42 ? ? 34 ? ? 53

31

再从5,5,7,11,13,17,19,23,29,31中选 ? 17 ? ? ? 24 ? ?

17 23 29 19 5,5为倒数第2层结点，并从上述数列中

? 10 ? ? ? 7 删去，再添上他们的和数，即7,10,11,13, 11 13 5 ? ? 17,19,23,29,31； 5 ? ? 然后，从7,10,11,13,17,19,23,29,31中 2 3

选7,10和11,13为倒数第3层结点，并从 如图十六 上述数列中删去，再添上他们的和数，即 17,17,24,19,23,29,31； ??

（2）权值为：2?6+3?6+5?5+7?4+11?4+13?4+17?3+19?3+23?3+29?3+31?2 =12+18+25+28+44+52+51+57+69+87+62=505 6．解：最优二叉树如图十七

3 ? ? 1

7 ? ? ? 4 2 12 ? ? 5 ? 3

?

2

如图十七

它的权为：1?3+2?3+2?2+3?2+4?2=27

五、证明题

1．证明：用反证法．设G中的两个奇数度结点分别为u和v．假设u和v不连通，即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与定理3.1.2的推论矛盾．因而u和v一定是连通的．

2．证明：设G??V,E?，G??V,E??．则E?是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点u?V，u在G和G中的度数之和等于u在

Kn中的度数．由于n是大于等于2的奇数，从而Kn的每个结点都是偶数度的（n?1 (?2)度），于是若u?V在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．

3．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶

8

数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．

k故最少要加条边到图G才能使其成为欧拉图．

2

9

本文来源：https://www.bwwdw.com/article/16td.html