(完整word版)离散数学图论部分经典试题及答案.pdf
( 4.5 )《(完整word版)离散数学图论部分经典试题及答案.pdf》由会员分享，可在线阅读，更多相关《(完整word版)离散数学图论部分经典试题及答案.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,e 是点割集C b,e是点割集Dd
2、是点割集6如图三所示，以下说法正确的是()A(a,e)是割边B(a,e)是边割集C(a,e),(b,c)是边割集D(d,e)是边割集cabedf图一图二2 图三7设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是()图四A（a）是强连通的B（b）是强连通的C（c）是强连通的D（d）是强连通的应该填写：D 8设完全图 Kn有 n 个结点(n2)，m 条边，当（）时，Kn中存在欧拉回路Am 为奇数Bn 为偶数Cn 为奇数Dm 为偶数9设 G 是连通平面图，有v个结点，e 条边，r 个面，则 r=()Aev2 Bve2 Cev2 Dev2 10无向图 G 存在欧拉通路，当且仅当()
3、AG 中所有结点的度数全为偶数BG 中至多有两个奇数度结点CG 连通且所有结点的度数全为偶数DG 连通且至多有两个奇数度结点11设 G 是有 n 个结点，m 条边的连通图，必须删去G 的()条边，才能确定 G 的一棵生成树A1mnBmnC1mnD1nm12无向简单图 G 是棵树，当且仅当()AG 连通且边数比结点数少1 BG 连通且结点数比边数少1 CG 的边数比结点数少1 DG 中没有回路二、填空题1已知图 G 中有 1 个 1 度结点，2 个 2 度结点，3 个 3 度结点，4 个 4 度结点，则 G 的边数是2设给定图 G(如图四所示)，则图 G 的点割cabedf图四文档编码:CK4N
4、9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1
5、J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9
6、Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK
7、4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4
8、K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10
9、U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:
10、CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P73 集是3若图 G=中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集 S，在 G 中删除 S 中的所有结点得到的连通分支数为W，则 S中结点数|S|与 W 满足的关系式为4无向图 G 存在欧拉回路，当且仅当G 连通且5设有向图 D 为欧拉图，则图 D 中每个结点的入度应该填
11、写：等于出度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，0
12、01，01，10，0，若去掉其中的元素，则该序列集合构成前缀码三、判断说明题1如图六所示的图G 存在一条欧拉回路2给定两个图 G1，G2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由（2）若是欧拉图，请写出一条欧拉回路v1v2v3v5v4dbacefghn图六文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q
13、6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4
14、N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K
15、1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U
16、9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:C
17、K4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS
18、4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP1
19、0U9Q6B7P74 图七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)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)，试（1）画出 G 的图形表示；（2）写出其邻接矩阵；（2）求出每
20、个结点的度数；（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.用 Dijkst
21、ra 算法求右图中 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 文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2
22、 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3
23、ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文
24、档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3
25、Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L3 ZP10U9Q6B7P7文档编码:CK4N9E7Q3Y2 HS4K1J7E6L
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 完整 word 离散数学 部分 经典 试题 答案
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内