电大离散数学图论部分期末复习辅导(3)

离散数学期末复习辅导（二）

四、计算题

1．设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) 画出其补图的图形． 解 （1）G的图形为：

（2）图G的邻接矩阵为：

?0??0A??1??0?0?0100??0110?1011??1101?0110??

（3）图G的每个结点的度数为：

deg(v1)?1，deg(v2)?2，deg(v3)?4，deg(v4)?3，deg(v5)?2．

（4）由关于补图的定义3.1.9可知，先在图G补充边画出完全图（见下面左图），然后去掉原图的边，可得图G补图（见下面右图）：

注意：补图中，如果没有标出结点v3，则是错的．

11

离散数学期末复习辅导（二）

2．图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权最小的生成树及其权值． 解 （1）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．

12

离散数学期末复习辅导（二）

注意：在用避圈法求最小的生成树的关键是：“取图中权数最小的边，且与前面取到的边不构成圈”，很多学生只注意到取权数最小的边了，而忽略了“不构成圈”的要求。 如果题目给出如解(1) 中所示赋权图，要求用Kruskal算法（避圈法）求出该赋权图的最小生成树，大家应该会吧．

3．已知带权图G如右图所示． (1) 求图G的最小生成树； (2)计算该生成树的权值．

解 （1）图G有6个结点，其生成树有5条边，用Kruskal算法求其权最小的生成树T： 第1步，取具最小权1的边；

第2步，取剩余边中具最小权2的边；

第3步，取剩余边中不与前2条边构成回路的具最小权3的边； 第4步，取剩余边中不与前3条边构成回路的具最小权5的边； 第5步，取剩余边中不与前4条边构成回路的具最小权7的边．

所求最小生成树T如右图． （2）该最小生成树的权为

W(T)?1?2?3?5?7?18．

13

离散数学期末复习辅导（二）

4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权． 解 （Huffman算法）：

首先组合2+3，求带权5, 5, 7, 17, 31的最优二叉树； 再组合5+5，求带权7, 10, 17, 31的最优二叉树； 然后组合7+10，求带权17, 17, 31的最优二叉树； 继续组合17+17，求带权31, 34的最优二叉树； 最后组合31+34，得65，这是树根所带的权。

可从树根开始往下画，即得所求最优二叉树T如下图：

所求最优二叉树T的权为：

w(T)?(2?3)?5?5?4?7?3?17?2?31?1?131

讲评：作业中最优二叉树往往都能画对了，但计算总权值时可能会把有些权的层数计算错了，导致总权值计算错误，大家一定要细心。 注意：这4个计算题的解题方法大家一定要掌握。

补充：教材第101页

例3 给定如图3.3.3所示有向图，其邻接矩阵以及邻接矩阵的乘积如下：

14

离散数学期末复习辅导（二）

?0?1?A??0??0??0?0?2?3A??0??0??01000??10?020100???21000?，A??10??0001??00?0010???002000??20?040200???42000?，A??20??0001??00?0010???00100?000??100?

?010?001??200?000??200?

?010?001??从上面的矩阵中可以得到一些结论，如：

（1）从A2中第1行第3列的为1可知，结点v1与v3之间有一条长度为2的路； （2）从A3中第1行第2列的为2可知，v1与v2之间有2条长度为3的路； （3）从A4中第2行第2列的为4可知，在结点v2有4条长度为4的回路． 如果改成问题： 试求：

（1）图G中结点v1与v3之间长度为2的路径条数； 1条 （2）图G中v1与v2之间长度为3的路径条数； 2条 （3）图G中经过v2的长度为4的回路条数． 4条

15

离散数学期末复习辅导（二）

五、证明题

证明题同学一般都做不好，原因是对证明题方法没有掌握，也是对一些概念不清楚所造成的。因此，希望大家认真学习教材和老师讲课中的证明方法，并通过作业逐步掌握做证明题的方法。

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必为偶数．要使这k个奇数度结点变成偶数度结点，从而使

k图G变成欧拉图，可在每两个奇数度结点间添加一条边．故在图G中至少要添加2条

k条边才能使其成为2边才能使其成为欧拉图．

16