30离散数学第9章树

第9章 习题解答9.1 有5片树叶.分析 设T 有x 个1度顶点(即树叶).则T 的顶点数Tx x n ,523+=++=的边数.41x n m +=-=由握手定理得方程.∑=+=⋅+⨯+⨯==+=ni ix x vd x m 1.1312233)()4(22由方程解出.5=x所求无向树T 的度数列为1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4棵都具有上述度数列,且它们是非同构的.9.2 T 中有5个3度顶点.分析 设T 中有x 个3度顶点,则T 中的顶点数,7x n +=边数x n m +=-=61,由握手定理得方程.∑=+==+=ni ix v d x m 173)(2122由方程解出x=5.所求无向树T 的度数列为1,1,1,1,1,2,2,3,3,3.由这个度数列可以画多棵非同构的无向树,图9.6给出的4棵都具有上述度数列,且它们是非同构的.9.2 T 中有5个3度顶点.要析 设T 中有x 个3度顶点,则T 中的顶点数x n +=7,边数x n m +=-=61,由握手定理得方程.∑=+==+=ni ix v d x m 173)(2122.由此解出5=x ,即T 中有5个3度顶.T 的度数列为1,1,1,1,1,1,1,3,3,3,3,3.由于T 中只有树叶和3度顶点,因而3度顶点可依次相邻,见图9.7所示. 还有一棵与它非同构的树,请读者自己画出.9.3 加1-k 条新边才能使所得图为无向树.分析 设具有k 个连通分支的森林为G,则G 有k 个连通分支i K T T TT ,,,21全为树,.,,2,1k i =加新边不能在i T 内部加,否则必产生回路.因而必须在不同的小树之间加新边. 每加一条新边后,所得到的森林就减少一个连通分支. 恰好加1-k 条新边,就使得图连通且无回路,因而是树.在加边过程中,只需注意,不在同一人连通分支中加边. 下面给出一种加边方法,取iv 为iT 中顶点,加新边1,,2,1),(1-=+k i vv i i,则所得图为树,见图9.8 给出的一个特例.图中虚线边为新加的边.9.4 不一定.分析 n 阶无向树T 具有1-n 条边,这是无向树T 的必要条件,但不是充公条件.例如, 阶圈(即1-n 个顶点的初级回路)和一个孤立点组成无向简单图具有1-n 条边, 但它显然不是树.9.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阶无向树中,顶点数5=n,边数4=m,各顶点度数之和为8,度数分配方案有3种,分别为①1,1,1,1,4;②1,1,1,2,3;③1,1,2,2.2.每种方案只有一棵非同构的树.图9.10所示的5阶图的非同构的生成树的度数列不能超出以上3种,也就是说,它至多有3棵非同构的生成树, 但由于图中无4度顶点,所示,不可能有度数列为①的生成树,于是该图最多有两棵非同构的生成树. 但在图9.10 中已经找出了两个非同构的生成树,其中(1)的度数列为③,(2) 的度数列为②,因而该图准确地有两棵非同构的生成树.9.7 基本回路为: .,,,hfab C gfa C ead C cbad C h g e c====基本回路系统为}.,,,{h g e cC C C C基本割集为:},,{},,{},,,{},,,,,{h g f Sc ed S h c b S h g ce a S fd b a ====基本回路系统为},,,{f d b aS S S S.分析 1°注意基本回路用边的序列表示,而基本割集用边的集合表示.2° 基本回路中,只含一条弦,其余的边全为树枝,其求法是这样的: 设弦),(j iv ve =,则jiv v,在生成树T 中,且在T 中,ji v v ,之间存在唯一的路径ji ,Γ与),(j iv ve =组成的回路为G 中对应弦e 的基本回路.3° 基本割集中,只含一条树枝,其余的边都是弦,其求法是这样的:设树枝),(j iv ve =,则e 为T 中桥,于是eT-(将e 从T中支掉),产生两棵小树1T 和2T ,则}|{21'''中和的两端点分别在中且在T T e G e e S e =e S 为树枝e 对应的基本割集. 显然ee S S e ,∈中另外的边全是弦. 注意,两棵小树1T 和2T ,中很可能有平凡的树(一个顶点).aT -得两棵小树如图9.11中(1) 所示. G 中一个端点在i T 中,另一个端点在2T 中的边为a(树枝), h g c e ,,,,它们全是弦,于是},,,,{h g c e a Sa=bT - 得两棵小树如图9.11中(2) 所示, 其中有一棵为平凡树. G 中一个端点在1T 中,另一个端点在2T 中的边数除树枝b 外,还有弦,,h c 所以, },,{h c b Sb=dT -产生的两棵小树如图9.11中(3) 所示 . G 中一个端点在1T 中,另中一个端点在2T 中的边,除树枝d 外,还有两条弦e c ,,所示, },,{e c d Sd=fT -产生的两棵小树如图9.11中(4) 所示. 由它产生的基本割集为},,{h g f Sf=9.8 按Kruskal 求最小生成树的算法,求出的图9.3(1)的最小生成树T 为图9.12中(1) 所示, 其7)(=T W .(2) 的最小生成树T 为图9.12中(2)所示,其.11)(=T W9.9 421,,B B B为前缀码.分析 在421,,B B B中任何符号串都不是另外符号串的前串,因而它们都是前缀码.而在3B 中, 1是11,101的前缀,因而3B不是前缀码. 在5B 中,,a 是ac aa ,等的前缀,因而5B 也不是前缀码.9.10 由图9.4 (1) 给出的2元前缀码.}11,011,01010,0100,00{1=B由(2) 给出的3元前缀码为.}.2,1,022,0202,0201,0200,01,00{2=B分析 1B 是2元树产生的2元前缀码(因为码中的符号串由两个符号0,1组成),类似地,2B 是由3元树产生的3元前缀码(因为码中符号串由3个符号0,1,2组成).一般地,由r 元树产生r 元前缀码.9.11 (1) 算式的表达式为ji h g f e d c b a *)*()()*)*((((++÷-+.由于使其成为因而可以省去一些括号优先于,,,*,-+÷ji h g f e d c b a **)()*)*((++÷-+.(2) 算式的波兰符号法表达式为.****hij fg bcde a ++-÷+(3) 算式的逆波兰符号法表达式为.****+÷+-+jI hi fg e d abc9.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度顶点为根的根树与以2度顶点为根的树显然是非同构的根树,所以2个阶非同构的根树有两棵.4阶非同构的无向树有两棵,见图9.13中(3)所示. 第一棵树有3片树叶,1个3度顶点, 以树叶为根的根树与以3度顶点为根的树非同构.所以,由第一棵树能生成两个非同构的根树, 见图9.14 中(1)所示. 第二棵树有两片树叶,两个2度顶点,由对称性,以树叶为根的根树与2度顶点为根的根树非同构,见图9.14中(2) 所示. 所以,4阶非同构的根树有4棵.5阶非同构的无向树有3棵,见图9.13中(4)所示. 由第一棵能派生两棵非同构的根树, 由第二棵能派生4棵非同构的根树,由第三棵能派生3棵非同构的根树,所以,5阶非同构的根树共有9棵,请读者将它们都画出来.9.13 答案 A:②; B:②; C:③; D:③; E:③;F:④; G: ④; H:③.分析 将所有频率都乘100,所得结果按从小到大顺序排列:.35,20,15,10,10,5,5=======a b c d e f g w w w w w w w以以上各数为权,用Huffman 算法求一棵最优树,见图9.15所示.对照各个权可知各字母的前缀码如下:a ——10，b ——01，c ——111，d ——110，e ——001，f ——0001，g ——0000.于是，a,b 的码长为e d c ,,,2的码长为g f ,,3的码长为4. W(T)=255(各分支点的权之和),W(T)是传输100按给定频率出现的字母所用的二进制数字,因则传输104个按上述频率出现的字母要用25500⨯个二进制数字..24=1055最后还应指出一点,在画最优树叶, 由于顶点位置的不同,所得缀码可能不同,即有些字母的码子在不同的最优树中可能不同,但一般说来码长不改变.特别是,不同的最优树,它们的权是固定不变的.9.14 答案 A:②; B:④分析用2元有序正则树表示算式,树叶表示参加运算的数,分支点上放运算符,并将被减数(被除数)放在左子树上,所得2元树如图9.16所示.用前序行遍法访问此树,得波兰符号表示法为abc-++de-*.**ghf用后序行遍法访问此树,得逆波兰符号表示法为dec*fghab--++**。

《离散数学》第九章树讲稿9.1 无向树及生成树一、本节主要内容无向树、森林树枝、弦、余树生成树基本回路与基本回路系统基本割集与基本割集系统最小生成树无向树二、教学内容无向树(树): 连通而无回路的无向图，用T表示.平凡树: 平凡图森林: 每个连通分支都是树的非连通的无向图树叶: 树中度数为1的顶点分支点: 树中度数≥2的顶点右图为一棵12阶树.声明:本章中所讨论的回路均指简单回路或初级回路无向树的性质定理9.1 设G=是n阶m条边的无向图，则下面各命题是等价的：（1）G是树(连通无回路);（2）G中任意两个顶点之间存在惟一的路径;（3）G中无回路且m=n-1;（4）G是连通的且m=n-1;（5）G是连通的且G中任何边均为桥;（6）G中没有回路, 但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.无向树的性质(续)例题例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求树叶数, 并画出满足要求的非同构的无向树.解用树的性质m=n-1和握手定理.设有x片树叶，于是n=1+2+x=3+x,2m=2(n-1)=2?(2+x)=1?3+2?2+x解出x=3，故T有3片树叶.T的度数列为1, 1, 1, 2, 2, 3有2棵非同构的无向树, 如图所示例题例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T的阶数n, 并画出满足要求的所有非同构的无向树.解设T的阶数为n, 则边数为n-1, 4度顶点的个数为n-7. 由握手定理得2m=2(n-1)=5?1+2?1+3?1+4(n-7)解出n=8, 4度顶点为1个.T的度数列为1,1,1,1,1,2,3,4有3棵非同构的无向树生成树生成树的存在性定理任何无向连通图都有生成树.证用破圈法. 若图中无圈, 则图本身就是自己的生成树.否则删去圈上的任一条边, 这不破坏连通性, 重复进行直到无圈为止,剩下的图是一棵生成树.推论1 设n阶无向连通图有m条边, 则m≥n-1.推论2 设n阶无向连通图有m条边, 则它的生成树的余树有m-n+1条边.基本回路与基本回路系统定义设T是n阶m条边的无向连通图G的一棵生成树，设e1', e2', … , e'm-n+1为T的弦. 设Cr为T添加弦er' 产生的G中惟一的圈(由er'和树枝组成), 称Cr为对应弦er'的基本回路或基本圈, r=1, 2, …, m-n+1. 称{C1,C2, …, Cm-n+1}为对应T的基本回路系统.求基本回路的算法: 设弦e=(u,v), 先求T中u到v的路径Γuv, 再并上弦e, 即得对应e的基本回路.基本割集与基本割集系统定义设T是n阶连通图G的一棵生成树, e1', e2', …,e'n-1为T的树枝，Si是G的只含树枝ei', 其他边都是弦的割集, 称Si为对应生成树T由树枝ei'生成的基本割集, i=1, 2, …, n-1. 称{S1, S2, …, Sn-1}为对应T的基本割集系统.求基本割集的算法: 设e '为生成树T 的树枝, T -e '由两棵子树T1与T2组成, 令Se '={e | e ∈E(G)且e 的两个端点分别属于T1与T2}则Se '为e '对应的基本割集.实例例图中红边为一棵生成树,求对应它的基本回路系统与基本割集系统解弦e,f,g 对应的基本回路分别为Ce=e b c, Cf=f a b c, Cg=g a b c d,C 基={Ce, Cf, Cg}.树枝a,b,c,d 对应的基本割集分别为Sa={a, f, g}, Sb={b, e, f, g}, Sc={c, e, f g}, Sd={d, g},S 基={Sa, Sb, Sc, Sd}.无向图与最小生成树对无向图或有向图的每一条边e 附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作带权图, 记作G=.设G '是G 的子图, G '所有边的权的和称作G '的权, 记作W(G ').最小生成树: 带权图权最小的生成树求最小生成树的算法——避圈法 (Kruskal)设G=, 将非环边按权从小到大排序：e1, e2, …, em.(1) 取e1在T 中(2) 检查e2, 若e2与e1不构成回路, 则将e2加入T 中, 否则弃去e2.(3) 检查e3,…, 重复进行直至得到生成树为止.实例例求图的一棵最小生成树9.2根树及其应用一、本节主要内容有向树根树、树根、树叶、内点、分支点家族树、根子树、有序树r元树（r元有序树）r元正则树（r元有序正则树）r元完全正则树（r元有序完全正则树）最优2元树与Huffman算法前缀吗与最佳前缀吗中序行遍法、前序行遍法、后续行遍法波兰符号法与逆波兰符号法二、教学内容有向树与根树的定义有向树: 基图为无向树的有向图根树: 有一个顶点入度为0, 其余的入度均为1的非平凡的有向树树根: 有向树中入度为0的顶点树叶: 有向树中入度为1, 出度为0的顶点内点: 有向树中入度为1, 出度大于0的顶点分支点: 树根与内点的总称顶点v的层数: 从树根到v的通路长度树高: 有向树中顶点的最大层数根树(续)根树的画法:树根放上方,省去所有有向边上的箭头如右图所示a是树根b,e,f,h,i是树叶c,d,g是内点a,c,d,g是分支点a为0层;1层有b,c; 2层有d,e,f;3层有g,h; 4层有i.树高为4家族树定义把根树看作一棵家族树:(1) 若顶点a 邻接到顶点b, 则称b 是a 的儿子, a 是b 的父亲;(2) 若b和c为同一个顶点的儿子, 则称b和c是兄弟;(3) 若a b且a可达b, 则称a是b的祖先, b是a的后代. 设v为根树的一个顶点且不是树根, 称v及其所有后代的导出子图为以v为根的根子树.根树的分类有序树: 将根树同层上的顶点规定次序r元树:根树的每个分支点至多有r个儿子r元正则树: 根树的每个分支点恰有r个儿子r元完全正则树: 树叶层数相同的r元正则树r元有序树: 有序的r元树r元正则有序树: 有序的r元正则树r元完全正则有序树: 有序的r元完全正则树最优2元树求最优树Huffman算法:给定实数w1, w2, …, wt,①作t片树叶, 分别以w1, w2, …, wt为权.②在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 以这2个顶点为儿子, 其权等于这2个儿子的权之和.③重复②, 直到只有1个入度为0 的顶点为止.W(T)等于所有分支点的权之和实例例求带权为1, 1, 2, 3, 4, 5的最优树.解题过程由下图给出，W(T)=38前缀码设α =α1α2…αn-1αn是长度为n的符号串α的前缀: α1α2…αk , k=1,2,…,n-1前缀码: {β1, β2,…, βm}, 其中β1, β2, …, βm为非空字符串, 且任何两个互不为前缀2元前缀码: 只出现两个符号(如0与1)的前缀码如{0,10,110, 1111}, {10,01,001,110}是2元前缀码{0,10,010, 1010} 不是前缀码前缀码(续)一棵2元树产生一个二元前缀码:对每个分支点, 若关联2条边, 则给左边标0, 右边标1;若只关联1条边, 则可以给它标0(看作左边), 也可以标1(看作右边). 将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处, 所得的字符串构成一个前缀码.如右图所示最佳前缀码例在通信中，设八进制数字出现的频率如下：0：25% 1：20% 2：15% 3：10%4：10% 5：10% 6：5% 7：5%采用2元前缀码, 求传输数字最少的2元前缀码(称作最佳前缀码), 并求传输10n(n≥2)个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3) 的码字传输需要多少个二进制数字?解用Huffman算法求以频率(乘以100)为权的最优2元树. 这里w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最优2元树如图所示.编码:0---011---112---0013---1004---1015---00016---000007---00001传100个按比例出现的八进制数字所需二进制数字的个数为W(T)=285.传10n(n≥2)个所用二进制数字的个数为2.85?10n, 而用等长码(长为3)需要用3?10n个数字.波兰符号法与逆波兰符号法行遍(周游)根树T : 对T 的每个顶点访问且仅访问一次.行遍2元有序正则树的方式：①中序行遍法: 左子树、根、右子树②前序行遍法: 根、左子树、右子树③后序行遍法: 左子树、右子树、根例如, 对图所示根树按中序、前序、后序行遍法访问结果分别为：b a (f d g)c e a b (c (d f g) e) b ((f g d)e c) a带下划线的是(子)树根, 一对括号内是一棵子树波兰符号法与逆波兰符号法(续)用2元有序正则树表示算式: 最高层次运算放在树根上, 然后依次将运算符放在根子树的根上, 数放在树叶上, 规定被除数、被减数放在左子树树叶上.例如, 右图表示算式((b+(c+d))*a)÷((e*f)-(g+h)*(i*j))波兰符号法与逆波兰符号法(续)波兰符号法(前缀符号法): 按前序行遍法访问表示算式的2元有序正则树, 其结果不加括号, 规定每个运算符号与其后面紧邻两个数进行运算.例如, 对上页中树的访问结果为÷*+ b + c d a -* e f * + g h * i j逆波兰符号法(后缀符号法): 按后序行遍法访问,规定每个运算符与前面紧邻两数运算.例如, 对上页中树的访问结果为b c d + + a * e f * g h + i j **-÷。