离散数学第二版答案（6-7章）

解：对偶图如下：

7.8第204页

1.画出所有不同构的一、二、三、四、五、六阶树。 解：一阶： 二阶： 三阶： 四阶(2)： 五阶(3)：

六阶(6)： 2.如何由无向图G的邻接矩阵确定G不是树？

解：根据“G不含回路而且有n-1条边则G是树”可以得出图G是一

棵树的判定条件如下：(1)无线图G的邻接矩阵A的n次幂An中，对角线上全是0（说明不存在回路）。（2）邻接矩阵中1的个数的总数为2(n-1),说明边的个数为n-1。邻接矩阵同时满足上面两个条件可以判断图G是树，如果不同时满足，则判断不是树。

3.设v和v?是树T的两个不同的结点，从v至v?的基本路径是T中最长的基本路径。证明：dT(v)?dT(v?)?1 证明：反证法

假设v或v?有一个结点的度数大于1，不妨设dT(v)?1,则必然存在一个。v??与v相连，由树的定义知v??不在v至v?的路径中（否则构成了环）设v至v?的路径长度为l，则v?到v??的距离为l?1?l，这与v至v?的基本路径是T中最长的基本路径矛盾。故dT(v)?dT(v?)?1。 4.。 解：a) b)

7. 证明：任何二叉树有基数个结点。

证明：在二叉树中，任何结点的出度不是0，就是2；假设出度为2的结点有x个，则该二叉树的出度之和为2x；设二叉树共有n个结

点，这些结点中除了根结点的入度为0，其余结点的入度都为1，因此，所有结点的入度之和为n-1。由图的性质，可知二叉树的出度之和与入度之和相等。即n-1=2x， n=2x+1，因此，无论x如何取值，二叉树的结点总数n都是基数。得证。

9. 证明：n阶二叉树的叶子结点数目为(n+1)/2，其高度h满足log2(n+1)-1≤h≤ (n-1)/2

证明：（1）在二叉树中，出度为0的结点是叶子结点，出度为2的结点是分支结点，设分支结点个数为x，由上题证明过程可知，n=2x+1, x=(n-1)/2。因此，叶子结点的个数为n-x=(n+1)/2。

（2）n阶二叉树的叶子结点有(n+1)/2个，分支结点有(n-1)/2个。利用(n-1)/2个结点构造一棵一元或二元树，设树高为m，则h=m+1。 考察(n-1)/2个结点构造的一棵一元或二元树，树高最大的情况是一元树，高度为(n-1)/2-1，因此，h最大值是(n-1)/2-1+1=(n-1)/2。 树高最小的情况是构造了一棵满二叉树，满二叉树的高度x和结点个数(n-1)/2满足关系2x+1-1=(n-1)/2，解得x=log(n+1)-2，因此h最小值是log(n+1)-1。因此，log2(n+1)-1≤h≤ (n-1)/2。 10.如何由有向图G的邻接矩阵确定G是不是有向树？

解：根据有向树的判定定义：仅一个结点的入度为0，其余结点的入度均为1的连通有向图。如果G是有向树，则其邻接矩阵满足：（1）有且仅有一列全为0。（2）其余的列有且只有一个1。否则有向图不是有向树。

11. 找出叶的权分别为2，3，5，7，11，13，17，19，23，29，31，

37和41的最优叶加权二叉树，并求其叶加权路径长度。

解：对于2,3,5,7,11,13,17,19,23,29,31,37,41，先组合两个最小的权2+3=5，得5,5,7,11,13,17,19,23,29,31,37,41；在所得到的序列中再组合5+5=10，得10,7,11,13,17,19,23,29,31,37,41；再组合10+7=17，得17,11,13,17,19,23,29,31,37,41；继续下去。。。。，过程如下：

2 3 5 7 11 13 17 19 23 29 31 37 41

5 5 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 11 13 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 34 42 53 31 37 41 42 53 65 37 41 42 53 65 78 95 65 78 95 143 238

所得到的最优二叉树如下图：