推荐下载离散数学图论部分经典试题及答案.docx
- 文档编号:16059672
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:14
- 大小:80.78KB
推荐下载离散数学图论部分经典试题及答案.docx
《推荐下载离散数学图论部分经典试题及答案.docx》由会员分享,可在线阅读,更多相关《推荐下载离散数学图论部分经典试题及答案.docx(14页珍藏版)》请在冰点文库上搜索。
推荐下载离散数学图论部分经典试题及答案
(完整word版)离散数学图论部分经典试题及答案
编辑整理:
尊敬的读者朋友们:
这里是精品文档编辑中心,本文档内容是由我和我的同事精心编辑整理后发布的,发布之前我们对文中内容进行仔细校对,但是难免会有疏漏的地方,但是任然希望((完整word版)离散数学图论部分经典试题及答案)的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈,这将是我们进步的源泉,前进的动力。
本文可编辑可修改,如果觉得对您有帮助请收藏以便随时查阅,最后祝您生活愉快业绩进步,以下为(完整word版)离散数学图论部分经典试题及答案的全部内容。
离散数学图论部分综合练习
一、单项选择题
1.设图G的邻接矩阵为
则G的边数为().
A.6B.5C.4D.3
2.已知图G的邻接矩阵为
,
则G有().
A.5点,8边B.6点,7边
C.6点,8边D.5点,7边
3.设图G=〈V,E〉,则下列结论成立的是().
A.deg(V)=2½E½B.deg(V)=½E½
C.
D.
4.图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.如图三所示,以下说法正确的是().
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.设完全图K
有n个结点(n≥2),m条边,当()时,K
中存在欧拉回路.
A.m为奇数B.n为偶数C.n为奇数D.m为偶数
9.设G是连通平面图,有v个结点,e条边,r个面,则r=().
A.e-v+2B.v+e-2C.e-v-2D.e+v+2
10.无向图G存在欧拉通路,当且仅当().
A.G中所有结点的度数全为偶数
B.G中至多有两个奇数度结点
C.G连通且所有结点的度数全为偶数
D.G连通且至多有两个奇数度结点
11.设G是有n个结点,m条边的连通图,必须删去G的()条边,才能确定G的一棵生成树.
A.
B.
C.
D.
12.无向简单图G是棵树,当且仅当().
A.G连通且边数比结点数少1B.G连通且结点数比边数少1
C.G的边数比结点数少1D.G中没有回路.
二、填空题
1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是.
2.设给定图G(如图四所示),则图G的点割
集是.
3.若图G=〈V,E>中具有一条汉密尔顿回路,
则对于结点集V的每个非空子集S,在G中删除S
中的所有结点得到的连通分支数为W,则S中结点
数|S|与W满足的关系式为.
4.无向图G存在欧拉回路,当且仅当G连通
且.
5.设有向图D为欧拉图,则图D中每个结点的入度 .
应该填写:
等于出度
6.设完全图K
有n个结点(n³2),m条边,当时,K
中存在欧拉回路.
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=〈V,E〉是有6个结点,8条边的连通图,则从G中删去条边,可以确定图G的一棵生成树.
13.给定一个序列集合{000,001,01,10,0},若去掉其中的元素,则该序列集合构成前缀码.
三、判断说明题
1.如图六所示的图G存在一条欧拉回路.
2.给定两个图G1,G2(如图七所示):
(1)试判断它们是否为欧拉图、汉密尔顿图?
并说明理由.
(2)若是欧拉图,请写出一条欧拉回路.
图七
3.判别图G(如图八所示)是不是平面图,
并说明理由.
4.设G是一个有6个结点14条边的连
通图,则G为平面图.
四、计算题
1.设图G=〈V,E〉,其中V={a1,a2,a3,a4,a5},
E={
(1)试给出G的图形表示;
(2)求G的邻接矩阵;
(3)判断图G是强连通图、单侧连通图还是弱连通图?
2.设图G=〈V,E〉,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= (1)给出G的图形表示; (2)写出其邻接矩阵; (3)求出每个结点的度数;(4)画出其补图的图形. 4.图G= (1)画出G的图形; (2)写出G的邻接矩阵; (3)求出G权最小的生成树及其权值. 5。 用Dijkstra算法求右图中A点到其它各点的最短路径。 6.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试 (1)画出相应的最优二元树; (2)计算它们的权值. 7.给出右边所示二元有序树的 三种遍历结果. 五、证明题 1.若无向图G中只有两个奇数度结点,则这两个结点一定是连通的. 2.设G是一个n阶无向简单图,n是大于等于2的奇数.证明图G与它的补图 中的奇数度顶点个数相等. 3.设连通图G有k个奇数度的结点,证明在图G中至少要添加 条边才能使其成为欧拉图. 参考解答 一、单项选择题 1.B2.D3.C4.C5.A6.D7.D8.C 9.A10.D11.A12.A 二、填空题 1.152.{f},{c,e}3.W£|S| 4.所有结点的度数全为偶数5.等于出度 6.n为奇数7.v—e+r=28.3 9.e=v-110.411.5 12.313.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的外面,就得到一个平 面图,如图九所示. 4.解: 错误. 不满足“设G是一个有v个结点e条边的连通简单平面图,若v≥3,则e≤3v-6.” 四、计算题 1.解: (1)图G是有向图: (2)邻接矩阵如下: (3)图G是单侧连通图,也是弱连通图. 2.解: (1)图G如图十 (2)邻接矩阵为图十 (3)deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 (4)补图如图十一 图十一 3.解: (1)G的图形如图十二 (2)邻接矩阵: 图十二 (3)v1,v2,v3,v4,v5结点的度数依次为1,2,4,3,2 (4)补图如图十三: 图十三 4.解: (1)G的图形表示如图十四: 图十四 (2)邻接矩阵: (3)粗线表示最小的生成树,如图十五 如图十五 最小的生成树的权为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,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=505 7.解: a)前根: a,b,d,g,e,h,i,c,f b)中根: g,d,b,h,e,i,a,c,f c)后根: g,d,h,i,e,b,f,c,a 五、证明题 1.证明: 用反证法.设G中的两个奇数度结点分别为u和v.假设u和v不连通,即它们之间无任何通路,则G至少有两个连通分支G1,G2,且u和v分别属于G1和G2,于是G1和G2各含有一个奇数度结点.这与定理3.1.2的推论矛盾.因而u和v一定是连通的. 2.证明: 设 , .则 是由n阶无向完全图 的边删去E所得到的.所以对于任意结点 ,u在G和 中的度数之和等于u在 中的度数.由于n是大于等于2的奇数,从而 的每个结点都是偶数度的( 度),于是若 在G中是奇数度结点,则它在 中也是奇数度结点.故图G与它的补图 中的奇数度结点个数相等. 3.证明: 由定理3.1。 2,任何图中度数为奇数的结点必是偶数,可知k是偶数. 又根据定理4.1.1的推论,图G是欧拉图的充分必要条件是图G不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图. 故最少要加 条边到图G才能使其成为欧拉图.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 推荐 下载 离散数学 部分 经典 试题 答案