《离散数学第九章：树.ppt》由会员分享，可在线阅读，更多相关《离散数学第九章：树.ppt（30页珍藏版）》请在三一办公上搜索。
1、树,第 九 章,9.1 无向树及生成树,树：连通而不含回路的无向图称为无向树，简称树，记作 T。,森林：连通分支数大于等于2，且每个连通分支均是树的非连通无向图。,平凡树：平凡图为平凡树。,一、树的概念,森林,树叶:树中度数为1的顶点分支点:树中度数2的顶点,树的性质：,(1)G连通而不含回路；,(2)每对顶点之间具有唯一一条初级通路,(3)n=m+1,(4)若在G中任意两个不相邻的顶点之间增加一条边，就形成唯一一条初级回路。,(5)连通且每条边都是桥,(6)连通但删除任何一条边后就不连通,设G=是n阶m条边的无向树，则下面各命题是等价的：,性质(7):任一棵非平凡树 T=，至少有两片叶。,证
2、明：设T有x片树叶，由握手定理及定理9.1知，,由上式解出x2.,生成树：若图G为无向连通图.T为G的生成子图，且T为树，称T为G的生成树。,三、生成树及其构造方法,树枝与弦：G在T中的边称为T的树枝，G不 在T中的边称为T的弦。,余树：T的弦的集合的导出子图称为T的余树。,生成树,余树,余树,例子,无向连通图的生成树不一定唯一生成树的余树不一定是树,带权图的最小生成树：设G=是带权的连通简单图，,具有权最小的生成树称为最小生成树。,T是G的一棵生成树，T中所有枝的权之和称为T的权，记作：W(T)。,四、最小生成树,方法：避圈法,在不产生回路的基础上依次画出权值最小的边，直至画出n-1条边为止
3、,v1,5,6,5,6,5,4,1,v2,v4,v5,v3,2,3,例：,5,v1,5,4,1,v2,v4,v5,v3,2,3,W(T)=1+2+3+4+5=15,6,5,1,v2,v4,v5,v3,2,3,例：,v1,5,5,1,v2,v4,v5,v3,2,3,v1,5,6,5,5,5,1,v2,v4,v5,v3,2,3,5,5,or,or,5,5,1,v2,v4,v5,v3,2,3,W(T)=1+2+3+5+5=16,！最小生成树不一定唯一,定义：设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,emn+1为T的弦.设Cr为T添加弦er产生的G中惟一的圈(由er和树枝组成),称Cr
4、为对应弦er的基本回路r=1,2,mn+1.称C1,C2,Cmn+1为对应T的基本回路系统.,五：基本回路与基本回路系统,例：,Ca=aef,Cb=bde,Cc=cdf,基本回路系统为：Ca,Cb,Cc,定义：设T是n阶连通图G的一棵生成树,e1,e2,en1为T的树枝，Si是G的只含树枝ei,其他边都是弦的割集,称Si为对应生成树T由树枝ei生成的基本割集。i=1,2,n1.称S1,S2,Sn1为对应T的基本割集系统.,六：基本割集与基本割集系统,例：,Sa=a,f,g,Sb=b,g,h,Sd=d,h,i,Sc=c,f,h,Se=e,f,i,基本割集系统为：Sa,Sb,Sc,Sd,Se,课后
5、例题：9.5，9.6，9.7，9.8课后作业：9.1，9.3，9.4，9.5，9.6，9.7，9.8,9.2 根树及其应用,一、树的概念,有向树:基图为无向树的有向图根树:有一个顶点入度为0,其余的入度均为1的 非平凡的有向树树根:有向树中入度为0的顶点树叶:有向树中入度为1,出度为0的顶点内点:有向树中入度为1,出度大于0的顶点分支点:树根与内点的总称(出度大于等于1）顶点v的层数:从树根到v的通路长度，记作l(v)树高:有向树中顶点的最大层数，记作h(T),根树的画法:树根放上方,省去所有有向边上的箭头如右图所示 a是树根 b,e,f,h,i是树叶 c,d,g是内点 a,c,d,g是分支点
6、 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)若ab且a可达b,则称a是b的祖先,b是a的后代.(4)设v为根树的一个顶点且不是树根,称v及其所有后代的导出子图为以v为根的根子树.,家族树：,有序树:每一层的结点均有序r元树:根树的每个分支点至多有r个儿子r元正则树:根树的每个分支点恰有r个儿子r元完全正则树:所有树叶层数相同都等于树高的r元 正则树r元有序树:有序的r元树r元正则有序树:有序的r元
7、正则树r元完全正则有序树:有序的r元完全正则树,根树的分类：,定义 设2元树T有t片树叶v1,v2,vt,树叶的权分别 为w1,w2,wt,称 为T的权,记作 W(T),其中l(vi)是vi的层数.在所有有t片树叶,带权 w1,w2,wt 的 2元树中,权最小的2元树称为最优 2元树.,最优二元树：,给定实数w1,w2,wt,作t片树叶,分别以w1,w2,wt为权.在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,以这2个顶点为儿子,其权等于这2个儿子的权之和.重复,直到只有1个入度为0 的顶点为止.W(T)等于所有分支点的权之和,Huffman算法,例 求带权为1
8、,1,2,3,4,5的最优树.解题过程由下图给出，W(T)=38,例：,设=12n-1n是长度为n的符号串的前缀:12k,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元树产生一个二元前缀码:对每个分支点,若关联2条边,则给左边标0,右边标1;若只关联1条边,则可以给它标0(看作左边),也可以标1(看作右边).将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处,所得的字
9、符串构成一个前缀码.如右图所示：,树的编码：,最优2进制编码：使信息传递的2进制数最短,例 在通信中，设八进制数字出现的频率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%采用2元前缀码,求传输数字最少的2元前缀码(称作最佳前缀码),并求传输10n(n2)个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3)的码字传输需要多少个二进制数字?解 用Huffman算法求以频率(乘以100)为权的最优2元树.这里 w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.最优2元树如图所示.,例：,编码:0-01 1
10、-11 2-001 3-100 4-101 5-0001 6-00000 7-00001传100个按比例出现的八进制数字所需二进制数字的个数为 W(T)=285.传10n(n2)个所用二进制数字的个数为2.8510n,而用等长码(长为3)需要用 310n个数字.课后习题：9.9，9.13,行遍(周游)根树T:对T 的每个顶点访问且仅访问一次.行遍2元有序正则树的方式：中序行遍法:左子树、根、右子树 前序行遍法:根、左子树、右子树 后序行遍法:左子树、右子树、根 例如,对图所示根树按中序、前序、后序行遍法访问结果分别为：b a(f d g)c e a b(c(d f g)e)b(f g d)e
11、c)a带下划线的是(子)树根,一对括号内是一棵子树,树的遍历：,用2元有序正则树表示算式:最高层次运算放在树根上,然后依次将运算符放在根子树的根上,数放在树叶上,规定被除数、被减数放在左子树树叶上.例如,右图表示算式(b+(c+d)a)(ef)(g+h)(ij),应用：算术式的波兰符号法与逆波兰符号法,波兰符号法(前缀符号法):按前序法遍历算式树,其结果不加括号.例如,对上页中树的访问结果为 b+c d a e f+g h i j 逆波兰符号法(后缀符号法):按后序法遍历,规定每个运算符与前面紧邻两数运算.例如,对上页中树的访问结果为b c d+a e f g h+i j,课后作业：9.11，9.14,小结与学习要求,1.掌握树的概念及其各种等价定义；2.熟悉生成树与回路和割集的关系，掌握最小生成树的构造方法；3.熟练掌握根树的性质和最优二元树的生成方法和应用;4.了解平面图的概念及其性质。,作业六,课后习题：，9.11，9.13,
