离散数学第四版课后答案(第9章)

1、第 9 章 习题解答9.1 有5片树叶.分析 设 T有 x 个 1度顶点(即树叶).则 T的顶点数的边数由握手定理得方程.n 3 2 x 5 x,T2m 2(4 x) m n 1 4 x.nd(v ) 3 3 2 2 1 x x.ii1由方程解出x 5.所求无向树T的度数列为1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图 9.6给出的 4棵都具有上述度数列,且它们是非同构的.9.2 T中有5个3度顶点.分析 设T中有 个3度顶点,则T中的顶点数边n 7 x,x数,由握手定理得方程.nm n 1 6 x2m 2x d(v ) 3x 7ii1由方程解出 x=5.所

2、求无向树 T的度数列为 1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图 9.6给出的 4棵都具有上述度数列,且它们是非同构的.9.2 T中有5个3度顶点.要析 设T中有x个3度顶点,则T中的顶点数,边n 7 x数,由握手定理得方程.m n 1 6 x1.n2m 2x d(v ) 3x 7ii1由此解出 ,即 T 中有 5 个 3 度顶.T 的度数列为x 51,1,1,1,1,1,1,3,3,3,3,3.由于 T中只有树叶和 3度顶点,因而 3度顶点可依次相邻,见图 9.7所示. 还有一棵与它非同构的树,请读者自己画出.9.3 加 条新边才能使所得图为无向树.k

3、 1分析 设具有 个连通分支的森林为 G,则 G有 个连通kk分支全为树,加新边不能在 内部加,否则T ,T ,T ,Ti 1,2, ,k.T12Kii必产生回路.因而必须在不同的小树之间加新边 . 每加一条新边后,所得到的森林就减少一个连通分支 . 恰好加 条k 1新边,就使得图连通且无回路 ,因而是树.在加边过程中 ,只需注意,不在同一人连通分支中加边 . 下面给出一种加边方法,取 为 中顶点,加新边,则所得图为树,vT(v ,v )i 1,2,k 1iiii1见图9.8 给出的一个特例.图中虚线边为新加的边.9.4 不一定.分析 n阶无向树T具有 条边,这是无向树 T的必要条n 1件,但

4、不是充公条件.例如, 阶圈(即 个顶点的初级回路)n 1和一个孤立点组成无向简单图具有条边, 但它显然不是n 1树.29.5 非同构的无向树共有 2棵,如图 9.9所示.分析 由度数列 1,1,1,1,2,2,4 4度顶点必须与 2度顶点相邻，它与 1个2度顶点相邻，还是与两个 2 度顶点都相邻，所得树是非同构的，再没有其他情况 .因而是两棵非同构的树.9.6 有两棵非同构的生成树,见图9.10所示.分析 图 9.10 是 5阶图(5个顶点的图),5阶非同构的无向树只有 3棵,理由如下.5阶无向树中,顶点数 ,边数 ,各顶点度数之和为 8,度n 5m 4数分配方案有 3种,分别为1,1,1,1

5、,4;1,1,1,2,3;1,1,2,2.2.每种方案只有一棵非同构的树.图9.10所示的5阶图的非同构的生成树的度数列不能超出以上 3种,也就是说,它至多有3棵非同构的生成树, 但由于图中无 4度顶点,所示,不可能有度数列为的生成树 ,于是该图最多有两棵非同构的3生成树. 但在图 9.10 中已经找出了两个非同构的生成树 ,其中(1)的度数列为,(2) 的度数列为,因而该图准确地有两棵非同构的生成树.9.7 基本回路为:C cbad ,C ead ,C gfa ,C hfab .cegh基本回路系统为C ,C ,C ,C .gceh基本割集为:b,c,hSa,e,c, g,hSabS d,e

6、,cS f , g,hdf基本回路系统为.S ,S ,S ,S dabf分析 1注意基本回路用边的序列表示 ,而基本割集用边的集合表示.2 基本回路中,只含一条弦,其余的边全为树枝,其求法是这样的: 设弦 ,则 在生成树 T中,且在 T中,e (v ,v )v ,vijij之间存在唯一的路径 与组成的回路为 G 中对v ,vie (v ,v )ji, jij应弦 的基本回路.e3 基本割集中,只含一条树枝,其余的边都是弦,其求法是这样的:设树枝 ,则 为T中桥,于是 (将 从Te (v ,v )eT eeij中支掉),产生两棵小树 和 ,则TT12S e | e 在G中且 e 的两端点分别在T

7、 和T 中e12为树枝 对应的基本割集. 显然中另外的边全是See S ,Seee弦. 注意,两棵小树 和 ,中很可能有平凡的树 (一个顶TT12点).4得两棵小树如图 9.11中(1) 所示. G中一个端点在T a中,另一个端点在 中的边为 (树枝),它们全是弦,TTae,c, g,hi2于是S a,e,c, g,ha得两棵小树如图 9.11中(2) 所示, 其中有一棵为T b平凡树. G中一个端点在 中,另一个端点在 中的边数除树TT12枝 外,还有弦 所以,c,h, b,c,hbSb产生的两棵小树如图 9.11中(3) 所示 . G中一个T d端点在 中,另中一个端点在 中的边,除树枝

8、外,还有两条TTd12弦 ,所示,c,eS d,c,ed产生的两棵小树如图 9.11 中(4) 所示. 由它产生T f的基本割集为S f , g,hf9.8 按 Kruskal求最小生成树的算法,求出的图 9.3(1)的最小生成树 T为图9.12中(1) 所示, 其W(T) 7.(2) 的最小生成树 T为图 9.12中(2)所示,其W(T) .9.9为前缀码.B ,B ,B214分析 在中任何符号串都不是另外符号串的前串 ,B ,B ,B214因而它们都是前缀码.而在 中,1是11,101的前缀,因而BB33不是前缀码. 在 中, 是a,等的前缀,因而 也不是前缀Baa ,acB55码.59.

9、10 由图9.4 (1) 给出的2元前缀码.B 00,0100 ,01010 ,0111由(2) 给出的3元前缀码为.B 00,01,0200 ,0201,0202 ,0222.2分析 是2元树产生的2元前缀码(因为码中的符号串B1由两个符号0,1组成),类似地, 是由3元树产生的3元前缀B2码(因为码中符号串由 3个符号 0,1,2组成).一般地,由 元r树产生 元前缀码.r9.11 (1) 算式的表达式为.(a (b * c)* d e) ( f g) (h *i)* j由于 ,.(a b *c)* d e) ( f g) h *i* j(2) 算式的波兰符号法表达式为 * a * fg

10、*hij.(3) 算式的逆波兰符号法表达式为 * d * e fg * jI * .9.12 答案 A:; B; C:; D:.分析 对于每种情况都先求出非同构的无向树 ,然后求出每棵非同构的无向树派生出来的所有非同构的根树 .图9.13 中,(1),(2),(3),(4)分别画出了2阶,3阶,4阶,5阶所有非同构的无向树,分别为 1棵,1棵,2棵和 3棵无向树.2阶无向树只有1棵,它有两个1度顶点,见图9.13中(1)所示,以1 个顶点为树根,1 个顶点为树叶,得到 1 棵根树.3 阶非同的无向树也只有 1 棵,见图 9.13 中(2)所示.它有两个 1 度顶点,1 个 2 度顶点,以 1

11、度顶点为根的根树与以2度顶点为根的树显然是非同构的根树,所以2个阶非同构的根树有两棵.4阶非同构的无向树有两棵,见图9.13中(3)所示. 第一棵树有3片树叶,1个3 度顶点, 以树叶为根的根树与以 3度顶点为根的树非同构 .所以,由第一棵树能生成两个非同构的根树, 见图 9.14 中(1)所示. 第二棵树有两片树叶,两个2 度顶点,由对称性,以树叶为根的根树与 2 度顶点为根的根树非同构,见图9.14中(2) 所示. 所以,4阶非同构的根树有4 棵.75阶非同构的无向树有 3棵,见图9.13中(4)所示. 由第一棵能派生两棵非同构的根树, 由第二棵能派生 4棵非同构的根树,由第三棵能派生3棵

12、非同构的根树,所以,5阶非同构的根树共有 9棵,请读者将它们都画出来.9.13 答案 A:;B:;C:;D:;E:;F:;G: ;H:.分析 将所有频率都乘 100,所得结果按从小到大顺序排列:w 5,w 5,w 10,w 10,w 15,w 20,w 35.gfedcba以以上各 数 为 权 ,用算法求一棵最优9.15所示.Huffman树 ,见 图对照各个权可知各字母的前缀码如下:a10， b01， c111， d110，e001， f0001，g0000.于是，a,b的码长为的码长为的码长为 4.2,c,d,e3, f , gW(T)=255(各分支点的权之和),W(T)是传输 100 按给定8频率出现的字母所用的二进制数字,因则传输10个按上述频4率出现的字母要用个二进制数字.2.55 4 最后还应指出一点,在画最优树叶, 由于顶点位置的不同,所得缀码可能不同 ,即有些字母的码子在不同