2022年2022年离散数学图论部分经典试题及答案 .pdf

《2022年2022年离散数学图论部分经典试题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学图论部分经典试题及答案 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 离散数学图论部分综合练习一、单项选择题1设图 G 的邻接矩阵为0101010010000011100100110则 G 的边数为 ( )A6 B5 C4 D3 2已知图 G 的邻接矩阵为，则 G 有（）A5 点，8 边B6 点，7 边C6 点，8 边D5 点，7 边3设图 G，则下列结论成立的是( )Adeg(V)=2 EBdeg(V)= ECEvVv2)deg(DEvVv)deg(4图 G 如图一所示，以下说法正确的是( ) A( a, d)是割边B( a, d)是边割集C( d, e)是边割集D( a, d) ,(a, c)是边割集5如图二所示，以下说法正确的是( )Ae 是割点Ba,

2、 e 是点割集C b, e是点割集Dd是点割集6如图三所示，以下说法正确的是( ) A( a, e)是割边B( a, e) 是边割集C( a, e) ,(b, c) 是边割集D(d, e) 是边割集cabedf图一图二名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 2 图三7设有向图（ a）、（ b）、（ c）与（ d）如图四所示，则下列结论成立的是 ( )图四A（a）是强连通的B（b）是强连通的C（c）是强连通的D（d）是强连

3、通的应该填写： D 8设完全图 Kn有 n 个结点 (n2)，m 条边，当（）时，Kn中存在欧拉回路Am 为奇数Bn 为偶数Cn 为奇数Dm 为偶数9设 G 是连通平面图，有v个结点， e 条边， r 个面，则 r= ( )Aev2 Bve2 Cev2 Dev2 10无向图 G 存在欧拉通路，当且仅当 ( )AG 中所有结点的度数全为偶数BG 中至多有两个奇数度结点CG 连通且所有结点的度数全为偶数DG 连通且至多有两个奇数度结点11设 G 是有 n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定 G 的一棵生成树A1mnBmnC1mnD1nm12无向简单图 G 是棵树，当且仅当

4、 ( )AG 连通且边数比结点数少1 BG 连通且结点数比边数少1 CG 的边数比结点数少1 DG 中没有回路二、填空题1已知图 G 中有 1 个 1 度结点， 2 个 2 度结点， 3 个 3 度结点， 4 个 4 度结点，则 G 的边数是2设给定图 G(如图四所示 )，则图 G 的点割cabedf图四名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 3 集是3若图 G=中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集

5、S，在 G 中删除 S 中的所有结点得到的连通分支数为W，则 S中结点数|S|与 W 满足的关系式为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 中删去条边后使之变成树

6、11已知一棵无向树T 中有 8 个结点， 4 度，3 度，2 度的分支点各一个， T的树叶数为12设 G是有 6 个结点， 8 条边的连通图，则从G 中删去条边，可以确定图G 的一棵生成树13给定一个序列集合 000，001，01，10，0 ，若去掉其中的元素，则该序列集合构成前缀码三、判断说明题1如图六所示的图G 存在一条欧拉回路2给定两个图 G1，G2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由（2）若是欧拉图，请写出一条欧拉回路v1v2v3v5v4dbacefghn图六名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

7、 - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 4 图七3判别图 G(如图八所示 )是不是平面图，并说明理由4设G是一个有 6个结点 14条边的连通图，则 G 为平面图四、计算题1设图 GV，E ，其中 Va1, a2, a3, a4, a5, Ea1, 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)，

8、(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), (

9、c, e), (c, d), (d, e) ，对应边的权值依次为2、1、2、3、6、1、4 及 5，试（1）画出 G 的图形；（2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值5.用 Dijkstra 算法求右图中 A 点到其它各点的最短路径。6设有一组权为 2,3,5,7,11,13,17,19,23,29,31, 试（1）画出相应的最优二元树；（2）计算它们的权值7给出右边所示二元有序树的三种遍历结果v1 v2 v3 v4 v5 v6 v5 v1 v2 v4 v6 v3 图八a b d c e g f i h 名师资料总结 - - -精品资料欢迎下载 - - - - - -

10、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 5 五、证明题1若无向图 G 中只有两个奇数度结点，则这两个结点一定是连通的2设 G 是一个 n 阶无向简单图， n 是大于等于 2 的奇数证明图 G 与它的补图G中的奇数度顶点个数相等3设连通图 G 有 k 个奇数度的结点， 证明在图 G 中至少要添加2k条边才能使其成为欧拉图参考解答一、单项选择题1B 2D 3C 4C 5A 6D 7D 8C 9A 10D 11A 12A 二、填空题115 2 f ，c，e 3W |S| 4所有结点的度数全

11、为偶数5等于出度6n 为奇数7v-e+r =2 83 9e=v- 1 104 115123 130 三、判断说明题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 (

12、v4, v5)v5 (v5, v2) v2 (v2, v6)v6 (v6, v4) v4 (v4, v1)v13解：图G是平面图因为只要把结点 v2与 v6的连线(v2, v6)拽到结点 v1的外面，把把结点v3与 v6的连线v5 v1 v2 v4 v6 v3 图九名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - 6 (v3, v6)拽到结点 v4, v5的外面，就得到一个平面图，如图九所示4解：错误不满足“设 G 是一个有 v

13、个结点 e条边的连通简单平面图，若v3，则 e3v-6”四、计算题1解：（1）图 G 是有向图：（2）邻接矩阵如下：,0001010000000010100000010)(DA（3）图 G 是单侧连通图，也是弱连通图2解：（1）图 G 如图十（2）邻接矩阵为图十0110010110110110110100110（3）deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 （4）补图如图十一图十一3解：（1）G 的图形如图十二a1 a2 a3 a4 a5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 名师资料总结 - - -精品资料欢迎下

14、载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - 7 （2）邻接矩阵：图十二0110010110110110110000100（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 （4）补图如图十三：图十三4解： （1）G 的图形表示如图十四：图十四（2）邻接矩阵：0111110110110011100110110（3）粗线表示最小的生成树，如图十五名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

15、 - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 8 如图十五最小的生成树的权为1+1+2+3=7：5. 解：注意算法执行过程的数据要完整的表示。6解：（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 ；再从 5,5,7,11,13,17,19,23,29,31 中选5,5 为倒数第 2 层结点，并从上述数列中删去，再添上他们的和数，即7,10,11

16、,13, 17,19,23,29,31 ；然后，从 7,10,11,13,17,19,23,29,31中选 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=5057解： ）前根：，）中根：，）后根：，五、证明题1证明： 用反证法设 G 中的两个奇数度结点分别为u 和 v假设 u 和 v不连通，即它们之间无任何通路，则G 至

17、少有两个连通分支G1，G2，且 u 和 v分别属于 G1和 G2，于是 G1和 G2各含有一个奇数度结点这与定理3.1.2 的推论矛盾因而 u 和 v 一定是连通的2证明 ：设,GV E，,GV E则 E 是由 n 阶无向完全图nK的边3 2 7 13 5 5 11 17 34 160 29 10 23 19 42 17 24 53 31 95 65 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 9 删去 E 所得到的所以对于

18、任意结点uV ，u 在 G 和G中的度数之和等于 u 在nK中的度数由于 n 是大于等于 2 的奇数，从而nK的每个结点都是偶数度的（1 (2)n度），于是若 uV 在 G 中是奇数度结点，则它在G中也是奇数度结点故图 G 与它的补图G中的奇数度结点个数相等3证明：由定理 3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数又根据定理 4.1.1的推论，图 G 是欧拉图的充分必要条件是图G 不含奇数度结点因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图故最少要加2k条边到图 G 才能使其成为欧拉图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -