好文档 - 专业文书写作范文服务资料分享网站

离散数学第二版(6-7章)

天下 分享 时间: 加入收藏 我要投稿 点赞

证明:图7-48中村子一个子图与阶数为6的库拉斯基图同构。将图7-48变形得到:

1236457

其中的由{v1,v2,v3,v4,v5,v6}构成的子图与阶数为6的库拉斯基图同构。故该图是非平面图。

5. 图7-49给出一个多边形的图,试构成该图的对偶。 解:对偶图如下:

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

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

23895143425365781923242931343741111317171075523

12.找出图7-71给出的有向序森林所对应的二元有向有序树,并求其前缀编码。 解:

4kw8f1vjbc565jb3urou8mpoj7ocb000zo7
领取福利

微信扫码领取福利

微信扫码分享