离散数学树解读课件

1第第7章章 树树 n7.1 无向树及生成树无向树及生成树n7.2 根树及其应用根树及其应用 1第7章 树 7.1 无向树及生成树27.1 无向树及生成树无向树及生成树 无向树与森林无向树与森林生成树与余树生成树与余树基本回路与基本回路系统基本回路与基本回路系统基本割集与基本割集系统基本割集与基本割集系统最小生成树与避圈法最小生成树与避圈法 27.1 无向树及生成树 无向树与森林3无向树无向树无向树无向树:无回路的连通无向图无回路的连通无向图平凡树平凡树:平凡图平凡图森林森林:每个连通分支都是树的非连通的无向图每个连通分支都是树的非连通的无向图树叶树叶:树中度数为树中度数为1的顶点的顶点分支点分支点:树中度数树中度数 2的顶点的顶点右图为一棵右图为一棵12阶树阶树.注注:本章中所讨论的回路均本章中所讨论的回路均 指简单回路或初级回路指简单回路或初级回路 3无向树无向树:无回路的连通无向图树的应用树的应用英国数学家英国数学家凯莱莱(Arthur Cayley)于于19世世纪中叶研究中叶研究饱和碳和碳氢化合物化合物CnH2n+2的同分异构体的同分异构体时提出提出树的概的概念念.当当n=1,2,3时,都只有一棵非同构的都只有一棵非同构的树;当当n=4时,有有2棵不同构的棵不同构的树.4甲甲烷乙乙烷丙丙烷丁丁烷异丁异丁烷树的应用英国数学家凯莱(Arthur Cayley)于19世5无向树的性质无向树的性质定理定理 设设G=是是n阶阶m条边的无向图条边的无向图,则下面各命则下面各命题是等价的：题是等价的：(1)G是是树(连通无回路通无回路);(2)G中任意两个中任意两个顶点之点之间存在惟一的路径存在惟一的路径;(3)G中无回路且中无回路且m=n 1;(4)G是是连通的且通的且m=n 1;(5)G是是连通的且通的且G中任何中任何边均均为桥;(6)G中没有回路中没有回路,但在任何两个不同的但在任何两个不同的顶点之点之间加加一条新边后所得图中有惟一的一个含新边的圈一条新边后所得图中有惟一的一个含新边的圈.5无向树的性质定理 设G=是n阶m条边的无向图,6无向树的性质无向树的性质(续续)定定理理 设设T 是是 n 阶阶非非平平凡凡的的无无向向树树，则则T中中至至少少有有两两片树叶片树叶.证证 设设T有有x片树叶片树叶,由握手定理及前面的定理，由握手定理及前面的定理，2(n-1)x+2(n-x)解得解得 x 2.6无向树的性质(续)定理 设T 是 n 阶非平凡的无向树，7例题例题例例1 已知无向树已知无向树T中中,有有1个个3度顶点度顶点,2个个2度顶点度顶点,其余顶点全其余顶点全是树叶是树叶.试求树叶数试求树叶数,并画出满足要求的非同构的无向树并画出满足要求的非同构的无向树.解解 用树的性质用树的性质m=n 1和握手定理和握手定理.设有设有x片树叶，于是片树叶，于是 n=1+2+x=3+x,2m=2(2+x)=1 3+2 2+x解得解得x=3，故，故T有有3片树叶片树叶.T的度数列为的度数列为1,1,1,2,2,3有有2棵非同构的无向树棵非同构的无向树.7例题例1 已知无向树T中,有1个3度顶点,2个2度顶点8例题例题例例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棵非同构的无向树棵非同构的无向树 8例题例2 已知无向树T有5片树叶,2度与3度顶点各1个,9生成树生成树 设设G为无向连通图为无向连通图G的的生成树生成树:G的生成子图并且是树的生成子图并且是树生成树生成树T的的树枝树枝:G在在T中的边中的边生成树生成树T的的弦弦:G不在不在T中的边中的边生成树生成树T的的余树余树 :所有弦的集合的导出子图所有弦的集合的导出子图注意：注意：不一定连通不一定连通,也不一定不含回路也不一定不含回路.黑边构成生成树黑边构成生成树红边构成余树红边构成余树9生成树 设G为无向连通图10生成树的存在性生成树的存在性 定理定理 任何无向连通图都有生成树任何无向连通图都有生成树.证证 用破圈法用破圈法.若图中无圈若图中无圈,则图本身就是自己的生成树则图本身就是自己的生成树.否则删去圈上的任一条边否则删去圈上的任一条边,这不破坏连通性这不破坏连通性,重复进行重复进行 直到无圈为止直到无圈为止,剩下的图是一棵生成树剩下的图是一棵生成树.推论推论 设设n阶无向连通图有阶无向连通图有m条边条边,则则m n 1.10生成树的存在性 定理 任何无向连通图都有生成树.11基本回路与基本回路系统基本回路与基本回路系统 定定义义设T是是连通通图G的的一一棵棵生生成成树,对每每一一条条弦弦e,存存在在惟惟一一的的由由弦弦e和和T的的树枝枝构构成成的的初初级回回路路Ce,称称Ce为对应于于弦弦e的的基基本本回回路路.称称所所有有基基本本回回路路的的集集合合为对应生成生成树T的的基本回路系统基本回路系统.求基本回路的算法求基本回路的算法:设弦设弦e=(u,v),先求先求T中中u到到v的路的路径径 uv,再加上弦再加上弦e.例如例如Ce=e b c,Cf=f a b c,Cg=g a b c d,C基基=Ce,Cf,Cg.11基本回路与基本回路系统 定义设T是连通图G的一棵生成树,12基本割集与基本割集系统基本割集与基本割集系统 定定义义设T是是连通通图G的的一一棵棵生生成成树,对T的的每每一一条条树枝枝a,存存在在惟惟一一的的由由树枝枝a,其其余余的的边都都是是弦弦的的割割集集Sa,称称Sa为对应树枝枝a的的基基本本割割集集，称称所所有有基基本本割割集集的的集合集合为对应生成生成树T的的基本割集系统基本割集系统.求基本割集的算法求基本割集的算法:设设a为生成树为生成树T的树枝的树枝,T a由两由两棵子树棵子树T1与与T2组成组成,则则 Sa=e|e E(G)且且e的两个端点分别属于的两个端点分别属于T1与与T2.例如例如 Sa=a,f,g,Sb=b,e,f,g,Sc=c,e,f g,Sd=d,g,S基基=Sa,Sb,Sc,Sd.12基本割集与基本割集系统 定义设T是连通图G的一棵生成树,回路合并回路合并合并合并回路回路C1和和C2(C1 C2):C1 C2是是C1和和C2上的上的边的的对称差构成的称差构成的(一条或几条一条或几条)回路回路.13回路合并合并回路C1和C2(C1C2):C1C2是C1基本回路的性质基本回路的性质连通通图中的任一条回路都可以表中的任一条回路都可以表成成对应它它所含弦的所含弦的基本回路的合并基本回路的合并.例如例如,abcf=Cf aef=Ce Cf aedg=Ce Cg bcdgfe=Ce Cf Cg 14基本回路的性质连通图中的任一条回路都可以表成对应它所含弦的基基本割集的性质基本割集的性质连通通图中的任一中的任一割集割集都可以表都可以表成成对应它它所含所含树枝枝的的基本基本割集割集的的对称差称差.例如例如 g,d=Sd a,b,e=Sa Sb a,e,c=Sa Sc b,e,f,d=Sb Sd 15基本割集的性质连通图中的任一割集都可以表成对应它所含树枝的基16无向图与最小生成树无向图与最小生成树 对无向图或有向图的每一条边对无向图或有向图的每一条边e附加一个实数附加一个实数w(e),称作称作边边e的权的权.图连同附加在边上的权称作图连同附加在边上的权称作带权图带权图,记作记作G=.设设T是是G的生成树的生成树,T所有边的权的和称作所有边的权的和称作T的权的权,记作记作W(T).最小生成树最小生成树:带权图权最小的生成树带权图权最小的生成树避圈法避圈法(Kruskal)求最小生成求最小生成树的算法的算法设G是是n阶无向无向连通通带权图G.(1)按按权从小到大排列从小到大排列边(环除外除外),设W(e1)W(e2)W(em).(2)令令T,i1,k0.(3)若若ei与与T中的中的边不构成回路，不构成回路，则令令TT ei,kk+1.(4)若若kn-1,则令令ii+1,转(3).16无向图与最小生成树 对无向图或有向图的每一条边e附加一个17例例 求图的一棵最小生成树求图的一棵最小生成树 w(T)=38实例实例17例 求图的一棵最小生成树 w(T)=38实例187.2 根树及其应用根树及其应用有向树与根树有向树与根树家族树与根子树家族树与根子树有序树有序树根树与有序树的分类根树与有序树的分类 r叉叉(有序有序)树树,r叉正则叉正则(有序有序)树树,r叉完全正则叉完全正则(有序有序)树树最优最优2叉树与叉树与Huffman算法算法前缀码与最佳前缀码前缀码与最佳前缀码中序行遍法、前序行遍法、后序行遍法中序行遍法、前序行遍法、后序行遍法波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法 187.2 根树及其应用有向树与根树19有向树与根树有向树与根树 有向树有向树:基图为无向树的有向图基图为无向树的有向图根树根树:有一个顶点入度为有一个顶点入度为0,其余的入度均为其余的入度均为1的的 非平凡的有向树非平凡的有向树树根树根:有向树中入度为有向树中入度为0的顶点的顶点树叶树叶:有向树中入度为有向树中入度为1,出度为出度为0的顶点的顶点内点内点:有向树中入度为有向树中入度为1,出度大于出度大于0的顶点的顶点分支点分支点:树根与内点的总称树根与内点的总称顶点顶点v的层数的层数:从树根到从树根到v的通路长度的通路长度树高树高:有向树中顶点的最大层数有向树中顶点的最大层数19有向树与根树 有向树:基图为无向树的有向图20根树根树(续续)根树的画法根树的画法:树根放上方树根放上方,省去所有有向边上的箭头省去所有有向边上的箭头如右图所示如右图所示 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.树高为树高为420根树(续)根树的画法:树根放上方,省去所有有向边上的箭头21家族树家族树定义定义 把根树看作一棵把根树看作一棵家族树家族树:(1)若顶点若顶点 a 邻接到顶点邻接到顶点 b,则称则称 b 是是 a 的的儿子儿子,a 是是 b 的的父亲父亲;(2)若若b和和c为同一个顶点的儿子为同一个顶点的儿子,则称则称b和和c是是兄弟兄弟;(3)若若a b且且a可达可达b,则称则称a是是b的的祖先祖先,b是是a的的后代后代.设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根,称称v及其所有后及其所有后代的导出子图为以代的导出子图为以v为根的为根的根子树根子树.21家族树定义 把根树看作一棵家族树:22根树的分类根树的分类有序树有序树:将根树同层上的顶点规定次序将根树同层上的顶点规定次序r叉树叉树:根树的每个分支点至多有根树的每个分支点至多有r个儿子个儿子r叉正则树叉正则树:根树的每个分支点恰有根树的每个分支点恰有r个儿子个儿子r叉完全正则树叉完全正则树:树叶层数相同的树叶层数相同的r元正则树元正则树r叉有序树叉有序树:有序的有序的r叉树叉树r叉正则有序树叉正则有序树:有序的有序的r叉正则树叉正则树r叉完全正则有序树叉完全正则有序树:有序的有序的r叉完全正则树叉完全正则树22根树的分类有序树:将根树同层上的顶点规定次序23最优最优2叉树叉树 定义定义 设设2叉树叉树T有有t片树叶片树叶v1,v2,vt,树叶的权分别树叶的权分别 为为w1,w2,wt,称称 为为T的权的权,其中其中 l(vi)是是vi的层数的层数.在所有权为在所有权为w1,w2,wt 的的t片树叶片树叶的的2叉树中叉树中,权最小的权最小的2叉树称为叉树称为最优最优 2叉树叉树.例如例如W(T1)=47W(T2)=54W(T3)=4223最优2叉树 定义 设2叉树T有t片树叶v1,v2,24求最求最优2叉叉树的算法的算法 Huffman算法算法:给定实数给定实数w1,w2,wt,作作t片树叶片树叶,分别以分别以w1,w2,wt为权为权.在在所所有有入入度度为为0的的顶顶点点(不不一一定定是是树树叶叶)中中选选出出两两个个权权最最小小的的顶顶点点,添添加加一一个个新新分分支支点点,以以这这2个个顶顶点点为为儿子儿子,其权等于这其权等于这2个儿子的权之和个儿子的权之和.重复重复,直到只有直到只有1个入度为个入度为0 的顶点为止的顶点为止.W(T)等于所有分支点的权之和等于所有分支点的权之和24求最优2叉树的算法 Huffman算法:25实例实例例例 求权为求权为 1,3,4,5,6的最优树的最优树.25实例例 求权为 1,3,4,5,6的最优树.26实例实例例例(续续)W(T)=42,前面的前面的T3也是最优的也是最优的.26实例例(续)27前缀码前缀码 设设 =1 2 n-1 n是长度为是长度为n的符号串的符号串 的的前缀前缀:1 2 k,k=1,2,n-1,n 前前缀缀码码:1,2,m,其其中中 1,2,m为为非非空空字字符符 串串,且任何两个互不为前缀且任何两个互不为前缀2元前缀码元前缀码:只有两个符号只有两个符号(如如0与与1)的前缀码的前缀码如如 0,10,110,1111,10,01,001,110是是2元前缀码元前缀码 0,10,010,1010 不是前缀码不是前缀码27前缀码 设=12n-1n是长度为n的符号串28前缀码前缀码(续续)一棵一棵2叉树产生一个二元前缀码叉树产生一个二元前缀码:对每个分支点对每个分支点,若关联若关联2条边条边,则给左边标则给左边标0,右边标右边标1;若只关联若只关联1条边条边,则可以给它标则可以给它标0(看作左边看作左边),也可以也可以标标1(看作右边看作右边).将从树根到每一片树叶的通路上标将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处的数字组成的字符串记在树叶处,所得的字符串构成所得的字符串构成一个前缀码一个前缀码.例如例如28前缀码(续)一棵2叉树产生一个二元前缀码:最佳前缀码最佳前缀码设要要传输的的电文中含有文中含有t个字符个字符,字符字符ai出出现的的频率率为pi,它的它的编码的的长度度为li,那么那么100个字符的个字符的电文的文的编码的期望的期望长度是度是100 .称称编码期望期望长度最小度最小的的2元前元前缀码为最佳最佳2元前元前缀码.在用在用2叉叉树产生生2元前元前缀码时,每个二每个二进制串的制串的长度度等于它所在等于它所在树叶的深度叶的深度,因而因而权为100p1,100p2,100pt的最的最优2叉叉树产生的生的2元前元前缀码是最佳是最佳2元前元前缀码.于是于是,给定字符出定字符出现的的频率率,可以用可以用Huffman算算法法产生最佳生最佳2元前元前缀码.29最佳前缀码设要传输的电文中含有t个字符,字符ai出现的频率30实例实例例例 在通信中，设八进制数字出现的频率如下：在通信中，设八进制数字出现的频率如下：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.30实例例 在通信中，设八进制数字出现的频率如下：31例例(续续)编码编码:0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001传传100个按比例出现的八进制数字所需二进制数字的个数个按比例出现的八进制数字所需二进制数字的个数为为 W(T)=285.传传10n(n 2)个所用二进制数字的个数为个所用二进制数字的个数为2.85 10n,而用等而用等长长码码(长为长为3)需要用需要用 3 10n个数字个数字.31例(续)32行遍行遍2叉有序叉有序树行遍行遍(周游周游)根树根树T:对对T 的每个顶点访问且仅访问一次的每个顶点访问且仅访问一次.行遍行遍2叉有序树的方式：叉有序树的方式：中序行遍法中序行遍法:左子树、根、右子树左子树、根、右子树 前序行遍法前序行遍法:根、左子树、右子树根、左子树、右子树 后序行遍法后序行遍法:左子树、右子树、根左子树、右子树、根 当不是正则树时当不是正则树时,左子树或右子树可缺省左子树或右子树可缺省例如例如,中序行遍中序行遍:b a(f d g)c e 前序行遍前序行遍:a b(c(d f g)e)后序行遍后序行遍:b(f g d)e c)a32行遍2叉有序树行遍(周游)根树T:对T 的每个顶点访33用用2叉有序叉有序树表示算式表示算式每一个分支点放一个运算符每一个分支点放一个运算符.二元运算符二元运算符所在所在的分的分支点有支点有2个儿子个儿子,运算运算对象是以象是以这2个儿子个儿子为根的根根的根子子树表示的子表达式表示的子表达式,并并规定被减数和被除数放在定被减数和被除数放在左子左子树上上;一元运算符一元运算符所在所在的分支点只有一个儿的分支点只有一个儿子子,运算运算对象是以象是以这个儿子个儿子为根的根子根的根子树表示的子表示的子表达式表达式.数字和数字和变量放在量放在树叶上叶上.33用2叉有序树表示算式每一个分支点放一个运算符.二元运算实例实例例例1 表示表示(b+(c+d)a)(e f)(g+h)(i j)的的2叉有序叉有序树中序行遍中序行遍:(b+(c+d)a)(e f)(g+h)(i j)前序行遍前序行遍:(b(cd)a)(ef)(gh)(ij)后序行遍后序行遍:(b(cd)a)(ef)(gh)(ij)注注:中序行遍的中序行遍的结果是原式果是原式34实例例1 表示(b+(c+d)a)(ef)(35波兰符号法波兰符号法波波兰兰符符号号法法(前前缀缀符符号号法法):按按前前序序行行遍遍法法访访问问表表示示算式的算式的2叉有序树叉有序树,并舍去所有括号并舍去所有括号.例例1(续续)b+cdaef+gh ij 计计算算方方法法:从从左左到到右右,每每个个运运算算符符号号对对它它后后面面紧紧邻邻的的2个个(或或1个个)数进行运算数进行运算.例例1(续续)设设a=3,b=1,c=d=2,e=f=3,g=i=1,h=j=2.1+22333+12 12,14333+12 12 5333+12 12,(15)33+12 12(15)9+12 12,(15)9 3 12(15)9 32,(15)96,(15)3,535波兰符号法波兰符号法(前缀符号法):按前序行遍法访问表36逆波兰符号法逆波兰符号法逆逆波波兰兰符符号号法法(后后缀缀符符号号法法):按按后后序序行行遍遍法法访访问问表表示算式的示算式的2叉有序树叉有序树,并舍去所有括号并舍去所有括号.例例1(续续)bcd+a ef gh+ij 计计算算方方法法:从从右右到到左左,每每个个运运算算符符号号对对它它前前面面紧紧邻邻的的2个个(或或1个个)数进行运算数进行运算.例例1(续续)122+3 33 12+12 122+3 33 12+2 ,122+3 33 32 122+3 33 6 ,122+3 96 122+3 3 ,14+3 3 ,53 3 ,(15)3 ,536逆波兰符号法逆波兰符号法(后缀符号法):按后序行遍法访实例实例例例2 用用2叉有序叉有序树表示下述命表示下述命题公式公式,并写出它的波并写出它的波兰符号法和逆波符号法和逆波兰符号法表达式符号法表达式.(pq)(p r)(q r)解解波兰符号法表达波兰符号法表达式式 p qpr qr逆波兰符号法表达逆波兰符号法表达式式 pqp r qr注注:当一元运算符在运算当一元运算符在运算对象前面象前面时,应画成右儿子画成右儿子.37 ppqqrr实例例2 用2叉有序树表示下述命题公式,并写出它的波兰符号人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。人有了知识，就会具备各种分析能力，离散数学树解读课件