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

《离散数学图论部分综合练习.doc》由会员分享，可在线阅读，更多相关《离散数学图论部分综合练习.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. .离散数学图论局部综合练习ooooocabedof图一1设图G，那么以下结论成立的是 ( )Adeg(V)=2E Bdeg(V)=EC D2图G如图一所示，以下说法正确的选项是 ( ) A(a, d)是割边B(a, d)是边割集 图二C(d, e)是边割集D(a, d) ,(a, c)是边割集3如图二所示，以下说法正确的选项是 ( )Ae是割点 Ba,e是点割集Cb, e是点割集 Dd是点割集4如图三所示，以下说法正确的选项是 ( ) A(a, e)是割边 B(a, e)是边割集C(a, e) ,(b, c)是边割集 D(d, e)是边割集图三5设有向图a、b、c与d如图四所示，那么以下结

2、论成立的是 ( )图四 Aa是强连通的 Bb是强连通的Cc是强连通的 Dd是强连通的6设完全图K有n个结点(n2)，m条边，当 时，K中存在欧拉回路Am为奇数 Bn为偶数 Cn为奇数 Dm为偶数7设G是连通平面图，有v个结点，e条边，r个面，那么r= ( )Aev2 Bve2 Cev2 Dev28无向图G存在欧拉通路，当且仅当( )AG中所有结点的度数全为偶数 BG中至多有两个奇数度结点CG连通且所有结点的度数全为偶数DG连通且至多有两个奇数度结点9设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树ABCD10无向简单图G是棵树，当且仅当( )AG连通且边数比结点

3、数少1 BG连通且结点数比边数少1CG的边数比结点数少1 DG中没有回路二、填空题1图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，那么G的边数是ooooocabedof图四2设给定图G(如图四所示)，那么图G的点割集是3假设图G=中具有一条汉密尔顿回路，那么对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，那么S中结点数|S|与W满足的关系式为4无向图G存在欧拉回路，当且仅当G连通且5设有向图D为欧拉图，那么图D中每个结点的入度6设完全图K有n个结点(n2)，m条边，当时，K中存在欧拉回路7设G是连通平面图，v, e, r分别表示G的结点数，边数和面

4、数，那么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存在一条欧拉回路v1v2v3v5v4dbacefghn图六2给定两个图G1，G2如图七所示：1试判断它们是

5、否为欧拉图、汉密尔顿图？并说明理由2假设是欧拉图，请写出一条欧拉回路v1v2v3v4v5v6ooooov5v1v2v4v6ov3图八图七3判别图G(如图八所示)是不是平面图，并说明理由4设G是一个有6个结点14条边的连通图，那么G为平面图四、计算题1设图G=，其中V=a1,a2,a3,a4,a5,E=，1试给出G的图形表示；2判断图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求出每个结点的度数；3画出图G的补

6、图的图形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图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权最小的生成树及其权值5设有一组权为2,3,5,7,11,13,17,19,23,29,31,试1画出相应的最优二叉树；2计算

7、它们的权值6画一棵带权为1,2,2,3,4的最优二叉树,计算它的权五、证明题1假设无向图G中只有两个奇数度结点，那么这两个结点一定是连通的2设G是一个n阶无向简单图，n是大于等于2的奇数证明图G与它的补图中的奇数度顶点个数相等3设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使其成为欧拉图参考解答一、单项选择题1C2C 3A 4D 5D 6C7A8D9A10A二、填空题1152f，c，e3W|S|4所有结点的度数全为偶数5等于出度6n为奇数7v-e+r =2839e=v-1104115123130三、判断说明题 1解：正确 因为图G为连通的，且其中每个顶点的度数为偶数 2解：1图G

8、1是欧拉图 因为图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的欧拉回路为：不惟一：ooooov5v1v2v4v6ov3图九v1(v1, v2)v2 (v2, v3)v3 (v3, v4) v4 (v4, v5)v5 (v5, v2)v2 (v2, v6)v6 (v6, v4)v4 (v4, v1)v13解：图G是平面图因为只要把结点v2与v6的连线(v2, v6)拽到结点

9、v1的外面，把把结点v3与v6的连线(v3, v6)拽到结点v4, v5的外面，就得到一个平面图，如图九所示4解：错误 不满足“设G是一个有v个结点e条边的连通简单平面图，假设v3，那么e3v-6四、计算题1oooooa1a2a3a4a5解：1图G是有向图： 2图G是单侧连通图，也是弱连通图 2v1v2v3v4v5ooooo解：1图G如图十3deg(v1)=2deg(v2)=3v1v2v3v4v5ooooodeg(v3)=4deg(v4)=3deg(v5)=2 4补图如图十一图十一3解：1G的图形如图十二图十二2v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 3补图如图十三：图

10、十三4解：1G的图形表示如图十四： 图十四2粗线表示最小的生成树，如图十五如图十五最小的生成树的权为1+1+2+3=7： 5解：1最优二叉树如图十六所示：ooooooooo3271355111734oo1602910ooo231942oo17o24o5331ooo9565方法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、11,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权值为：26+36+55+74+114+134+173+193+233+293+312 =12+18+25+28+44+52+51+57+69+87+62=5056ooooooooo1223347512解：最优二叉树如图十七 如图十七它的权为：13+23+22+32+42=27五、证明题1证明：用反证法设G中的两个奇数度结点分别为u和v假设u和v不连通，即它们之间

12、无任何通路，那么G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点这与定理7.1.2的推论矛盾因而u和v一定是连通的2证明：设，那么是由n阶无向完全图的边删去E所得到的所以对于任意结点，u在G和中的度数之和等于u在中的度数由于n是大于等于2的奇数，从而的每个结点都是偶数度的度，于是假设在G中是奇数度结点，那么它在中也是奇数度结点故图G与它的补图中的奇数度结点个数相等 3证明：由定理7.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数又根据定理7.4.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图故最少要加条边到图G才能使其成为欧拉图. .word.