第10章习题答案

第10章 图

58.设G=是连通图且e∈E,试证明:e是G的割边?e包含在G的每棵生成树中。 证明 ?设e包含在G的每棵生成树中,但e不是G的割边。在图G中删去e得图G?,G? 仍是连通图。对G来说必有一棵生成树T,T中不包含边e,与假设矛盾。

?设边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

联系客服:779662525#qq.com(#替换为@)