构。
由归纳原理，命题得证。 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图中各点的缓冲时间。 解：略。见课件举例。