第10章 图
58.设G＝
?设边e不是G的割边，删去e，G就分成两个互不连通的子图G1和G2。对于G的任一一棵生成树T，由于T是连通图，故连结G1和G2之间的唯一边e必在T中。
59.如何由有向图G的邻接矩阵A判定G是否是根树，若是根树，如何定出它的树根和树叶。 解 一个有向图G为根树，它的邻接矩阵A必须满足：1）所有主对角元素为0；2）矩阵中有一列元素全为0，所有其它列中都恰有一个1。
如果一个邻接矩阵对应的有向图是根树，那么全0列对应的结点为根。而全0行对应的结点为树叶。 60.设T为任意一棵正则二叉树，m为边数，t为树叶数，试证明m＝2t－2，其中t≥2。 证明 设T中结点数为n，分支结点数为i，根据正则二叉树的定义得下面等式成立：
n＝i＋t (1) m＝2i (2) m＝n－1 (3)
由以上三式整理得m＝2t－2。
61.证明一棵完全二叉树必有奇数个结点。
证明 设完全二叉树T有n个结点，m条边。依定义，T中每个分支点都关联两条边，所以m必为偶数。
又由T是树，有n＝m＋1，故n为奇数。 因此，完全二叉树必有奇数个结点。
62.画出所有不同构的高为2的二叉树，其中有多少棵正则二叉树？有多少棵满二叉树？
解 高为2的所有不同构的二叉树有7棵，如图所示。其中有2棵正则二叉树，如图(5)和(7)；1棵满二叉树如图(7)。
63.求带权2、3、5、7、8的最优二叉树及其权，并求该二叉树对应的2元前缀码。 解 (1)构造最优二叉树的全部过程如图所示。树的权为(2＋3)×3＋(5＋7＋8)×2＝55。 (2)该二叉树对应的2元前缀码为{000，001，01，10，11}。
17
第10章 图
64.(1)求带权为1、1、2、3、3、4、5、6、7的最优三叉树。 (2)求带权为1、1、2、3、3、4、5、6、7、8的最优三叉树。 解 求最优r叉树的Huffman算法：r为分支数，t为树叶数，(1)若
t?1为整数，求最优r叉树的算r?1法与求最优2叉树的算法类似，只是每次取r个最小的权。(2)若r-1除t-1余数s不为0，1≤s＜r-1，将s+1个较小的权对应的树叶为兄弟放在最长的通路上，然后的算法同(1)。
(1)所求树的树叶数t＝9，分支数r＝3。得3叉树如图所示。
(2) 所求树的树叶数t＝10，分支数r＝3。叉树如图所示。
65.在下面给出的3个符号串集合中，哪些是前缀码？哪些不是前缀码？若是前缀码，构造二叉树，其树叶代表二进制编码。若不是前缀码，则说明理由。
18
t?19＝，于是r-1除t-1余数为1，由Huffman算法得3r?12t?1＝4，说明所求3叉树为正则3叉树。由Huffman算法r?1第10章 图
(1){0，10，110，1111}。 (2){1，01，001，000}。 (3){1，11，101，001，0011}。
解 (1)和(2)中的各字符串互不为前缀，因而(1)和(2) 是前缀码。而(3)中，1既是11的前缀，又是101的前缀，因而(3)不是前缀码。由(1)和(2)构造的二叉树如图所示。
66.给出定理10.56的证明。
证明 若G??V1,V2,E?为二部图，则V1和V2中的结点可分别着颜色C1和C2，由于G中至少有一条边，所以V1和V2中的结点不可能着同一种颜色，故?(G)＝2。
反之，若?(G)＝2，不妨设G中的结点分别着颜色C1和C2，令V1为G中着颜色C1的所有结点组成的集合，和V2为G中着颜色C2的所有结点组成的集合，V1和V2中都不存在相邻的结点。故G为二部图。
67.求图10-53所示各图的点色数。
解 （1）和（2）的着色数分别为3和5。
68.设G为图10-54所示平面图G的对偶图，画出G，通过求?(G)求对应地图的?*(G)。
*
*
*
解 ?*(G)＝?(G)＝2。
*
69.给出完全图K4和K5的边色数。 解 ?*(K4)＝3，?*(K5)＝5。
19
第10章 图
70.给出K3,3的边色数。 解 ?*(K3,3)＝3。
71.将无向完全图K6的边随意地涂上红色或绿色，证明：无论如何涂法，总存在红色的K3或绿色的K3。
证明 设K6的结点为v1，v2，?，v6。给K6的边随意用红、绿色涂上。由抽屉原理可知，由v1引出的5条边中存在3条涂同种颜色的边。不妨设存在着3条红色的边，又不妨设这3条边的另一端点分别是
v2、v3、v4（否则可重新给结点编号）。红色边用粗实线表示，绿色边用细实线表示。由v1引出的另外两
条边的颜色可红可绿。
若v2、v3、v4构成的K3中的边再有一条红色边，比如[v2，v4]着的是红色，则v1、v2、v4构成的三角形为红色的K3，如图（1）。若v2、v3、v4构成的K3中的边全是绿色的边，则存在绿色边的K3，如图（2）。
v2v3（1）v1v1v4v2v4v3（2）72.求图10-55所示图中结点b到其余各结点的最短路径及其长度。 解
G的邻接矩阵为
求解的全过程如表所示 k 0 1 2 3 4 5 6 D
?071?????0?82??30?4?A＝??2?01??????0????104?????2?????????3????????2?07???0??b 0 0 a 7 4/c 4/c 4 c 1 1/b 1 d ∞ ∞ 12/a 12/a 12/a 12/a 12/a 12 e ∞ 5/c 5/c 5/c 5/c 5 20
f ∞ 4/c 4/c 4/c 4 g ∞ ∞ ∞ 7/e 11/f 11/f 11 S b b，c b，c，a b，c，a，f b，c，a，f，e b，c，a，f，e，g b，c，a，f，e，g，d