四川大学离散数学(冯伟森版)课后习题答案习题参考解答(图论部分)

发布时间 : 星期五 文章四川大学离散数学(冯伟森版)课后习题答案习题参考解答(图论部分)更新完毕开始阅读

去找 http://www.7zhao.net SETP3: 转换为二叉树。

具体过程略■

21. 证明:正则二叉树必有奇数个结点,且树叶数t与结点数n之间有:t=(n-1)/2。

证明:因为正则二叉树的边数m与分支点数i的关系为:m=2i,又因为是树,因此结点数n满足:n=m-1=2i-1,必为奇数。叶结点数t和枝点数之和为n,即:t+i=n,因此t=(n-1)/2■

22. 遍历一棵树是指访问这个树的每个结点一次且仅一次。遍历二叉树有如下三种方式: (1)前序遍历:访问根, 遍历左子树,然后遍历右子树。 (2)中序遍历: 遍历左子树,访问根,然后遍历左子树。 (3)后序遍历: 遍历左子树, 遍历右子树,然后访问根。 根据三种不同遍历形式,分别写出图11.15中各结点被访问的顺序。

图11.15

解:

(1) 前序遍历结果:abdfjglmcehi (2) 中序遍历结果:jfdlgmbachei (3) 后序遍历结果:jflmgdbhieca■

23. 设英文字母b,d,g,o,y,e出现的频率分别是0.014,0.038,0.02,0.08,0.131,构造一个与它们对应的前缀码,并写出符号串dogbybed对应的编码。

解:构造最优树如下:

17

去找 http://www.7zhao.net 0.014,0.038,0.02,0.08,0.02,0.131 0.014,0.02, 0.02,0.038,0.08,0.131 ====== 0.034 0.02,0.038,0.08,0.131 ======== 0.052 0.038,0.08,0.131 ======== 0.09 0.08,0.131 ======== 0.283 0.131 ========= 0.414 0 0 1 1 1 0 0 1 0.08 (o) 0.038 (d) 0.131 (e) 0 1 0.02 (y) 0.014 (b) 0.02 (g) 因此获得相应的前缀码:b=00000,g=00001,y=0001,d=001,o=01,e=1 所以dogbybed的编码为:0010100001000000001000001001■ 完成题目 [1,2,3,4,5,6,7,8,10,11,12,14,15,16,17,18,19,20,21,22,23] 勘误: 1.23题,[频率分别是0.014,0.038,0.02,0.08,0.131]改为[频率分别是0.014,0.038,0.02,0.08,0.02,0.131]p223 2.7题,[ 设G为n(n≥3)阶简单图,证明G或中必含圈]改为[设G为n(n≥5)阶简单图,证明G或中必含圈]p223

第十三题未证明

18

去找 http://www.7zhao.net

习题十二

1.证明下面3个图都是平面图。

证明:因为所给图都可以平面图的方式画出来,如下:

■ 2.下面3个图都是平面图,先给图中各边标定顺序,然后求出图中各面的边界和面度。 解:略■ 3. 设G是阶数不小于11的图。证明:G或中至少有一个是非平面图。 证明:假设G和都是平面图,因为,所以至少有一个图的边数,设,有因为是平面图,所以有,求解得n≤10.与题设G是阶数不小于11的图矛盾,因此G或中至少有一个是非平面图■ 4. 证明:具有6个结点、12条边的简单连通平面图,它的面的度数都是3。 证明:因为是简单连通平面图,因此根据欧拉公式有 6-12+f=2,所以有8个面。根据面度和与边的关系有,Σd(fi)=2m=24;因为要在平面上围成一个面,至少需要3边,所以8个面,Σd(fi)≥24。因此,不存在面度大于3的面,所有面的度数都是3■

5. 证明:少于30条边的简单平面图至少有一个顶点的度不大于4。

19

去找 http://www.7zhao.net 证明:假设图G(n,m)的每个结点的点度都大于等于5,根据握手定理及平面图的判定定理有: 5n≤2m<60 (1) 握手定理 m≤3n-6 (2) 根据(1)得到:n<12 结合(1)(2)得到:5n/2≤3n-6,所以n≥12,矛盾。因此假设不成立,题设结论成立■

6. 设G是具有k(k≥2)个连通分支的平面图,则 n–m+f=k+1。 证明:针对每个连通分支而言,满足欧拉公式及:ni-mi+fi = 2,因此Σni – Σmi + Σfi = 2k.因为对G图而言只有一个外部面,但在针对每个连通分支引用欧拉欧式的时候都计算了一次外部面,因此外部面多计数k-1次,所以总面数比求和公式少k-1个面,因此有Σni – Σmi + Σfi-(k-1) = 2k-(k-1) 得 n–m+f=k+1■ 7. 证明:对K3.3的任何一边e,K3,3-e是平面图。同样,对K5的任何边e,K5-e也是平面图。 证明:因为K3,3-e,K5-e 可以画成平面图的形式,如下: ■ 8. 当m和n取什么值时Km,n是平面图?证明你的结论。 解:当m≤2,n≥1, 或n≤2,m≥1时,Km,n是平面图。因为: 当m≤2,n≥1时,如果m = 1 , 那么此图是一颗树,因此是平面图 如果m=2,那么可以将此图案如下方式图示: 20

联系合同范文客服:xxxxx#qq.com(#替换为@)