实用标准方案
4．设G=
定理4.2.2 设G=
5．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去
条边后使之变成树．（……边后，可以确定图G的一棵生成树）
由握手定理（定理3.1.1）知道图G有18?2=9 条边，又由定理5.1.1中给出的图T为树的等价定义之一是“图T连通且e=v-1”，可以知道： 应该填写：4．
6．设正则5叉树的树叶数为17，则分支数为i = ． 定理5.2.1 设有正则m叉树，其树叶数为t，分枝数为i，则(m-1)i=t-1． 其中m=5， t=17，由(5-1)i=17-1，得i =4．
应该填写：4
三、判断说明题
1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路． 分析：先复习欧拉图的判别定理：
定理4.1.1的推论：一个无向图具有一条欧拉回路，当且仅当该图是连通的，并且它的结点度数都是偶数． 解：不正确．
因为题中的图G没有“连通”的条件．
2．如下图所示的图G存在一条欧拉回路．
解：不正确．
因为图G中结点b和c的度数是奇数．
注：这是一个汉密尔顿图，但不是欧拉图，它可以作为单向选择题7解答之后提出的问题的一个解答．
3．设G是一个有7个结点16条边的连通图，则G为平面图．
精彩文档
实用标准方案
分析：定理4.3.3 设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．
利用该定理判断本题． 解：不正确．
因为题中的连通简单平面图有v=7个结点，e=16条边，那么16?3?7-6=15，由定理4.3.3知道，图G不是平面图．
4．设G是一个连通平面图，且有6个结点11条边，则G有7个面．
分析：可以用平面图中的欧拉公式：v-e+r =2来判断，其中v为结点数，e为边数，r为面数．
解：正确．
因为连通平面图G有v=6个结点，e=11条边，那么由欧拉公式计算得：r =2+ 11- 6 = 7个面．
四、计算题
1．设G=
(1) 给出G的图形表示； (2) 写出其邻接矩阵； (3) 求出每个结点的度数； (4) 画出其补图的图形． 解：(1) 因为V={ v1，v2，v3，v4，v5}，
v1 ?
v2 ? ? v3
? v4
? v5
E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)， (v4,v5) }，所以G的图形表示为：
(2) 分析：本题给定的简单图是无向图， 因此邻接矩阵为对称的．即当结点vi与vj相 邻时，结点vj与vi也相邻，所以连接结点vi 与vj的一条边在邻接矩阵的第i行第j列处和 第j行第i列处各写一个1；当结点vi与vj没
有边连接时，邻接矩阵的第i行第j列处和第j行第i列处各写一个0．
?00100??00110???邻接矩阵： ?11011?
??01101????00110??(3) 由G的图形可知，v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2
精彩文档
实用标准方案
(4) 由关于补图的定义3.1.9可知，先画出完全图（见图1），然后去掉原图，可得补图（见图2）如下：
v1
?
图1 图2 注意：补图中，如果没有标出结点v3，则是错的．
2．图G=
v2
? ? v3
? v4
? v5
v2 ?
? v3
? v4
v1 ? ? v5
e), (c, e), (c, d), (d, e) }，对应边的权值依次为2、1、2、3、6、1、4及5，试
（1）画出G的图形； （2）写出G的邻接矩阵； （3）求出G权最小的生成树及其权值．
解 （1）因为V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，所以G的图形表示为：
（2）由图得图G的邻接矩阵为：
?0??1A??1??0?1?1101??0011?0011?
?1101?1110??（3）图G有5个结点，其生成树有4条边，用Kruskal算法（避圈法）求其权最小的生成树T：
精彩文档
实用标准方案
第1步，取具最小权1的边(a, c)；
第2步，取剩余边中具最小权1的边(c, e)；
第3步，取剩余边中不与前2条边构成回路的具最小权2的边(a, b)； 第4步，取剩余边中不与前3条边构成回路的具最小权3的边(b, d)． 所求最小生成树T如右下图，其权为W(T)?1?1?2?3?7．
注意：在用避圈法求最小的生成树的关键是：“取图中权数最小的边，且与前面取到的边不构成圈”，很多学生只注意到取权数最小的边了，而忽略了“不构成圈”的要求．
如果结点数少一个，边数也少些，大家应该会做了吧．
3．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．
解：方法（Huffman）：从2, 3, 5, 7, 17, 31中选2, 3为最低层结点，并从权数中删去，再添上他们的和数，即5, 5, 7, 17, 31；
再从5, 5, 7, 17, 31中选5, 5为倒数第2层结点，并从 上述数列中删去，再添上他们的和数，即7, 10, 17, 31； 然后，从7, 10, 17, 31中选7, 10为倒数第3层结点， 并从上述数列中删去，再添上他们的和数，即17, 17, 31； ……
最优二叉树如右图所示．
最优二叉树权值为：2?5+3?5+5?4+7?3+17?2+31?1 =10+15+20+21+34+31=131
讲评：作业中最优二叉树往往都能画对了，但计算总权值时
可能会把有些权的层数计算错了，导致总权值计算错误，大家一定要细心． 注意：这3个计算题大家一定要掌握．
65 ? ? 34 ? 31
? 17 ? 17
? 10 ? 7 5 ? ?
5
? ? 2 3
精彩文档
实用标准方案
五、证明题
证明题同学一般都做不好，原因是对证明题方法没有掌握，也是对一些概念不清楚所造成的．因此，希望大家认真学习教材和老师讲课中的证明方法，并通过作业逐步掌握做证明题的方法．
1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．
证明：设G??V,E?，G??V,E??．则E?是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点u?V，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于3的奇数，从而Kn的每个结点都是偶数度的（n?1 (?2)度），于是若u?V在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．
2．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．
证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数． 又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．
故最少要加
k条边才能2k条边到图G才能使其成为欧拉图． 2精彩文档