五、证明题
1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的． 2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图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的连线
5
k条边才能2v1 ? v6 ? ? v5
v? 2
? v3
? v4 图九
(v3, v6)拽到结点v4, v5的外面，就得到一个平 面图，如图九所示．
4．解：错误．
不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”
四、计算题
1．解：（1）图G是有向图： （2）邻接矩阵如下：
a3 a2 ?01000?? ? ???0A(D)??1??0??0? a4 ?a
5 ?a 1
0010?0000?,
?0001?1000??（3）图G是单侧连通图，也是弱连通图． 2．解：（1）图G如图十 v1 ?
v2 ? ? v5
? ?
v4 v3
（2）邻接矩阵为 图十
?01100??10110??? ?11011?
??01101????00110??（3）deg(v1)=2
deg(v2)=3 deg(v3)=4 deg(v4)=3
deg(v5)=2
（4）补图如图十一
v1 ? v2 ? ? v3
? v4
v? 5
图十一 3．解：（1）G的图形如图十二
6
（2）邻接矩阵： 图十二
?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）粗线表示最小的生成树，如图十五
7
如图十五 最小的生成树的权为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；
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
7．解：ａ）前根：ａ，ｂ，ｄ，ｇ，ｅ，ｈ，ｉ，ｃ，ｆ
ｂ）中根：ｇ，ｄ，ｂ，ｈ，ｅ，ｉ，ａ，ｃ，ｆ ｃ）后根：ｇ，ｄ，ｈ，ｉ，ｅ，ｂ，ｆ，ｃ，ａ
五、证明题
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的边
8
删去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是偶数．
又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．
k故最少要加条边到图G才能使其成为欧拉图．
2
9
相关推荐：
loading