离散数学形成性考核作业

4．解：错误．

不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”

四、计算题

1．解：（1）图G是有向图： （2）邻接矩阵如下：

a2 ? a?3 ??010(D)??0A??10a4 ? ?a

5 ?a ?001

??01（3）图G是单侧连通图，也是弱连通图． 2．解：（1）图G如图十

v?1

v2 ? ? v5

? ?

v 3

v4 （2）邻接矩阵为 图十

??01100?10110? ????11011?

?01101????00110??（3）deg(v1)=2

deg(v2)=3 deg(v3)=4 deg(v4)=3

v?1 deg(v5)=2

v2 ? ? v5

（4）补图如图十一 v?

?3

v

4 图十一 3．解：（1）G的图形如图十二

（2）邻接矩阵： 图十二

6 000?010?000??,

001??000??

?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）粗线表示最小的生成树，如图十五

如图十五 最小的生成树的权为1+1+2+3=7：

7

5．解：（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 6．解：最优二叉树如图十七

3 ? ? 1

7 ? ? ? 4 2 12 ? ? 5 ? 3

?

2

如图十七

它的权为：1?3+2?3+2?2+3?2+4?2=27

五、证明题

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的边删去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是偶

8

数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．

k故最少要加条边到图G才能使其成为欧拉图．

2

9