离散数学(图论部分)1-4章习题课(2)

构。

由归纳原理，命题得证。 15. 证明：n阶图连通当且仅当r(B)=n?1 证：必要性：课件定理[3-2-3]的证明。

充分性：设此时G的连通分支数为k，则经行列互换，关联矩阵B可写成一个对角分块阵：

?B1?0B?????00B20.........0?0???，r(B)=r(B1)+ r(B2)+ … r(Bk) ?Bk?

设 第i个连通子图的阶为ni, i=1..k。由必要性：r(Bi)=ni?1。 故 r(B)??(ni?1)??ni?k?n?k

i?1i?1kk由条件 r(B)=n?1，故 k=1。 即图是连通的。

V1

16. 求下图生成树的数目：

|BBkT|=24

17. 试画出12硬币3次求伪的判断树。 解：略。

V5

V2

V3

V4

解：构造关联矩阵B划出Bk，应用Binet-Cauchy定理得到生成树的数目

18. 证明：对2元正则树，m=2n0?2，其中m为边数，n0为树叶数。 证：树有 m=n?1

二元树有 n0 = n2+1

二元正则树有顶点数 n = n0+n2 故： n = n0+n2 = n0+(n0?1)= 2n0?1

m=n?1=2n0?2

19. 有字符串 “state seat act tea cat set a cat” ，求其最短二进制编码。 解：统计字频，建立huffman树，构造相应的huffman编码。过程见课件举例。

20. 旅行商问题：用分支定界法、最近邻法、最近插入法、最远插入法求解：

??4233522945????26384930????342742???

?3541????31???????? 解：精确解=194 最近邻法解=205 最近插入法解=203 最远插入法解=229

21. 求下图各点到v8的最短路径（提示：利用Dijkstra算法）

解：将原图有向边反向得到新图，利用Dijkstra算法求新图中V8到各点的最

短路径。

22. 求PERT图中各点的缓冲时间。 解：略。见课件举例。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学(图论部分)1-4章习题课(2)在线全文阅读。