离散数学--7.1-2 树及其应用.ppt
第第7 7章章 树及其应用树及其应用1第第7 7章章 树及其应用树及其应用7.1 无向树无向树7.2 根树及其应用根树及其应用27.1 无向树无向树7.1.1 无向树的定义及其性质无向树的定义及其性质7.1.2 生成树与基本回路和基本割集生成树与基本回路和基本割集7.1.3 最小生成树最小生成树3无向树的定义无向树的定义无向树无向树:连通无回路的无向图连通无回路的无向图平凡树平凡树:平凡图平凡图森林森林:每个连通分支都是树的非连通的无向图每个连通分支都是树的非连通的无向图树叶树叶:树中度数为树中度数为1的顶点的顶点分支点分支点:树中度数树中度数 2的顶点的顶点例如例如(a)(b)4无向树的性质无向树的性质定理定理7.1 设设G=是是n阶阶m条边的无向图条边的无向图,下面各命题是下面各命题是等价的：等价的：(1)G是树是树(连通无回路连通无回路);(2)G中任意两个顶点之间存在惟一的路径中任意两个顶点之间存在惟一的路径;(3)G是连通的且是连通的且m=n 1;(4)G中无回路且中无回路且m=n 1;(5)G中中无无回回路路,但但在在任任何何两两个个不不相相邻邻的的顶顶点点之之间间加加一一条条边边 所得图中有惟一的一条初级回路所得图中有惟一的一条初级回路.(6)G是连通的且是连通的且G中任意一条边均为桥中任意一条边均为桥.5定理定理7.1的证明的证明(1)(2)由连通性由连通性,任意任意2个顶点之间有一条路径个顶点之间有一条路径.又又,假假设设某某2个顶点之间有个顶点之间有2条路径条路径,则这则这2条路径可组合成一条回条路径可组合成一条回路路,与树的定义矛盾与树的定义矛盾.(2)(3)显然连通显然连通,要证要证m=n 1.对对n作归纳证明作归纳证明.当当n=1时时,显然显然m=0,结论成立结论成立.假设当假设当n k(k 1)时结论成立时结论成立,考虑考虑n=k+1.任取一条边任取一条边e=(u,v),它是它是u,v之间惟一的通路之间惟一的通路,删去删去e,G被分成被分成2个连通分个连通分支支,设它们分别有设它们分别有n1,n2个顶点和个顶点和m1,m2条边条边,n1 k,n2 k.由归纳假设由归纳假设,m1=n1-1,m2=n2-1,得得m=m1+m2+1=n-1.6定理定理7.1的证明的证明(续续)(3)(4)假设有回路假设有回路,任取一个回路任取一个回路,删去回路中的一条删去回路中的一条边边,所得图仍是连通的所得图仍是连通的.重复这个做法重复这个做法,直到没有回路为止直到没有回路为止,得得到一棵树到一棵树,它有它有n个个顶点顶点m-r条边条边,r0.由由(1)(2)(3),得得m-r=n-1,矛盾矛盾.(4)(1)只需证只需证G连通连通.假设假设G不连通不连通,有有p(p1)个连通分个连通分支支.设第设第k个连通分支有个连通分支有nk个顶点和个顶点和mk条边条边,由由(1)(2)(3),mk=nk-1.得到得到m=n-p,矛盾矛盾.7定理定理7.1的证明的证明(续续)(1)(5)由由(1)(2),任意任意2个不相邻的顶点之间有一条惟个不相邻的顶点之间有一条惟一的路径一的路径,故在这故在这2个顶点之间添加一条新边个顶点之间添加一条新边,必得到一必得到一条条惟一的初级回路惟一的初级回路.(5)(6)首先首先,任意任意2个不相邻的顶点之间都有一条通路个不相邻的顶点之间都有一条通路,否则在它们之间添加一条新边不可能构成回路否则在它们之间添加一条新边不可能构成回路,故故G连通连通.其次其次,若删去一条边若删去一条边G仍是连通的仍是连通的,这条边必在一条回路这条边必在一条回路上上,与与G中无回路矛盾中无回路矛盾.(6)(1)G中无回路中无回路,否则删去回路上任意条边否则删去回路上任意条边,G仍连通仍连通.8无向树的性质无向树的性质(续续)定理定理7.2 非平凡的无向树至少有两片树叶非平凡的无向树至少有两片树叶 证证 设有设有n(n1)个顶点个顶点,x片树叶片树叶,由握手定理和定理由握手定理和定理7.1,有有 解得解得 x 2.9实例实例例例1 已知无向树已知无向树T中中,有有1个个3度顶点度顶点,2个个2度顶点度顶点,其余顶其余顶点全是树叶点全是树叶.试求树叶数试求树叶数,并画出满足要求的非同构的无并画出满足要求的非同构的无向树向树.解解 设有设有x片树叶片树叶,2(2+x)=1 3+2 2+x解得解得x=3，故故T有有3片树叶片树叶.T的度数列为的度数列为1,1,1,2,2,310实例实例例例2 画出所有画出所有6阶非同构的无向树阶非同构的无向树解解 5条边条边,总度数等于总度数等于10可能的度数列可能的度数列:(1)1,1,1,1,1,5(2)1,1,1,1,2,4(3)1,1,1,1,3,3(4)1,1,1,2,2,3(5)1,1,2,2,2,2(1)(2)(3)(4a)(4b)(5)11生成树生成树定义定义7.2 设设G是无向连通图是无向连通图,若若G的生成子图的生成子图T是一棵树是一棵树,则则称称T是是G的的生成树生成树.G在在T中的边称作中的边称作T的的树枝树枝,不在不在T中的中的边边称作称作T的的弦弦.T的所有弦的集合的导出子图称作的所有弦的集合的导出子图称作T的的余树余树例如例如 图中黑边构成生成树图中黑边构成生成树红边构成余树红边构成余树注意注意:余树一般不是树余树一般不是树12生成树的存在性生成树的存在性定理定理7.3 任何无向连通图都有生成树任何无向连通图都有生成树.证证 用破圈法用破圈法.若图中无圈若图中无圈,则图本身就是自己的生成树则图本身就是自己的生成树.否则删去圈上的任一条边否则删去圈上的任一条边,不破坏连通性不破坏连通性,重复进行直到重复进行直到无圈为止无圈为止,得到图的一棵生成树得到图的一棵生成树.推论推论1 设设n阶无向连通图有阶无向连通图有m条边条边,则则m n 1.推论推论2 设设n阶无向连通图有阶无向连通图有m条边条边,则它的生成树的余树则它的生成树的余树有有m n+1条边条边.13基本回路与基本回路系统基本回路与基本回路系统定义定义7.3 设设G是是n阶阶m条边的无向连通图条边的无向连通图,T是是G的一棵生成的一棵生成树树,e1,e2,em n+1为为T的的弦弦.G中中仅仅含含T的的一一条条弦弦er的的圈圈Cr称作对应弦称作对应弦er的的基本回路基本回路.称称C1,C2,Cm n+1为对应为对应T的的基本回路系统基本回路系统例例3 图中红边为一棵生成树图中红边为一棵生成树,对应它的基本回路系统为对应它的基本回路系统为bce,fae,gaed 14基本割集与基本割集系统基本割集与基本割集系统定定义义7.4 设设T是是n阶阶连连通通图图G的的一一棵棵生生成成树树,e1,e2,e n 1为为T的树枝，的树枝，Si是是G的只含树枝的只含树枝ei,其他边都是弦其他边都是弦的割集的割集,称称Si为对应树枝为对应树枝ei 的的基本割集基本割集.称称S1,S2,Sn 1为对应为对应T的的基本割集系统基本割集系统例例4 图中红边为一棵生成树图中红边为一棵生成树,对应它的基本割集系统为对应它的基本割集系统为a,f,g,e,b,f,g,c,b,d,g15最小生成树最小生成树图图G的每一条边的每一条边e附加一个实数附加一个实数w(e),称作边称作边e的的权权.图图G连连同附加在边上的权称作同附加在边上的权称作带权图带权图,记作记作G=.设设H是是G的子图的子图,H所有边的权的和称作所有边的权的和称作H的权的权,记作记作W(H).最小生成树最小生成树:带权图权最小的生成树带权图权最小的生成树避圈法避圈法(Kruskal)(1)将所有非环边按权从小到大排列将所有非环边按权从小到大排列,设为设为e1,e2,em(2)令令T=(3)For k=1 to m Do 若若ek与与T 中的边不构成回路中的边不构成回路,则将则将ek加入加入T 中中16实例实例例例5 求图的一棵最小生成树求图的一棵最小生成树W(T)=38177.2 根树及其应用根树及其应用7.2.1 根树及其分类根树及其分类7.2.2 最优树与哈夫曼算法最优树与哈夫曼算法7.2.3 最佳前缀码最佳前缀码7.2.4 根树的周游及其应用根树的周游及其应用中序行遍法、前序行遍法和后序行遍法中序行遍法、前序行遍法和后序行遍法波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法18根树的定义根树的定义有向树有向树:略去方向后为无向树的有向图略去方向后为无向树的有向图根树根树:有一个顶点入度为有一个顶点入度为0,其余的入度均为其余的入度均为1的非平凡的的非平凡的有向树有向树树根树根:有向树中入度为有向树中入度为0的顶点的顶点树叶树叶:有向树中入度为有向树中入度为1,出度为出度为0的顶点的顶点内点内点:有向树中入度为有向树中入度为1,出度大于出度大于0的顶点的顶点分支点分支点:树根与内点的总称树根与内点的总称顶点顶点v的层数的层数:从树根到从树根到v的通路长度的通路长度树高树高:有向树中顶点的最大层数有向树中顶点的最大层数19实例实例根树的画法根树的画法:树根放最上方树根放最上方,省去所有有向边上的箭头省去所有有向边上的箭头右图中右图中 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家族树家族树把根树看作一棵把根树看作一棵家族树家族树:若顶点若顶点a邻接到顶点邻接到顶点b,则称则称b是是a的的儿子儿子,a是是b的的父亲父亲若若b和和c为同一个顶点的儿子为同一个顶点的儿子,则称则称b和和c是是兄弟兄弟若若a b且且a可达可达b,则称则称a是是b的的祖先祖先,b是是a的的后代后代设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根,称称v及其所有后代的导及其所有后代的导出子图为以出子图为以v为根的为根的根子树根子树将根树每一层上的顶点规定次序后称作将根树每一层上的顶点规定次序后称作有序树有序树21根树的分类根树的分类r元树元树:根树的每个分支点至多有根树的每个分支点至多有r个儿子个儿子r元正则树元正则树:根树的每个分支点恰有根树的每个分支点恰有r个儿子个儿子r元完全正则树元完全正则树:所有树叶层数相同的所有树叶层数相同的r元正则树元正则树r元有序树元有序树:有序的有序的r元树元树r元正则有序树元正则有序树:有序的有序的r元正则树元正则树r元完全正则有序树元完全正则有序树:有序的有序的r元完全正则树元完全正则树22最优最优2元树元树定义定义7.10 设设2元树元树T有有t片树叶片树叶v1,v2,vt,树叶的权分别为树叶的权分别为w1,w2,wt,称称 为为T的权的权,记作记作W(T),其中其中l(vi)是是vi的层数的层数.在所有有在所有有t片树叶片树叶,带权带权w1,w2,wt 的的 2元元树中树中,权最小的权最小的2元树称为元树称为最优最优2元树元树例如例如134 561345613456W(T1)=47W(T2)=54W(T3)=4323求最优求最优2元树的算法元树的算法哈夫曼哈夫曼(Huffman)算法算法给定实数给定实数w1,w2,wt 作作t片树叶片树叶,分别以分别以w1,w2,wt为权为权 在在所所有有入入度度为为0的的顶顶点点(不不一一定定是是树树叶叶)中中选选出出两两个个权权最最小小的的顶顶点点,添添加加一一个个新新分分支支点点,以以这这2个个顶顶点点为为儿儿子子,其其权等于这权等于这2个儿子的权之和个儿子的权之和 重复重复,直到只有直到只有1个入度为个入度为0 的顶点为止的顶点为止 W(T)等于所有分支点的权之和等于所有分支点的权之和24实例实例例例1 求以求以1,3,4,5,6为权的最优为权的最优2元树元树,并计算它的权并计算它的权解解134(a)13448(b)134456811(c)1344 5681119(d)W(T)=4+8+11+19=4225最佳前缀码最佳前缀码定定 义义 7.11 设设=1 2 n-1 n是是 长长 度度 为为 n的的 符符 号号 串串,1 2 k称作称作 的长度为的长度为k的的前缀前缀,k=1,2,n-1.若非空字符串若非空字符串 1,2,m中任何两个互不为前缀中任何两个互不为前缀,则称则称 1,2,m为为前缀码前缀码只出现两个符号只出现两个符号(如如0与与1)的前缀码称作的前缀码称作2元前缀码元前缀码例如例如 0,10,110,1111,10,01,001,110是是2元前缀码元前缀码 0,10,010,1010 不是前缀码不是前缀码26用用2元树产生元树产生2元前缀码的方法元前缀码的方法对对每每个个分分支支点点,若若关关联联2条条边边,则则给给左左边边标标0,右右边边标标1;若若只只关关联联1条条边边,则则可可以以给给它它标标0(看看作作左左边边),也也可可以以标标1(看看作作右右边边).将从树根到每一片树叶的通路上标的数字组成的字将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处符串记在树叶处,所得的字符串构成一个前缀码所得的字符串构成一个前缀码.例如例如前缀码前缀码00,11,011,010027实例实例例例2 在通信中在通信中,设八进制数字出现的频率设八进制数字出现的频率(%)如下如下:0:25,1:20,2:15,3:10,4:10,5:10,6:5,7:5采用采用2元前缀码元前缀码,求传输数字最少的求传输数字最少的2元前缀码元前缀码(称作称作最佳最佳前缀码前缀码),并求传输并求传输100个按上述比例出现的八进制数字需个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的要多少个二进制数字？若用等长的(长为长为3)的码字传输需的码字传输需要多少个二进制数字要多少个二进制数字?解解 用用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优2元树元树.这里这里w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.28实例实例(续续)编码编码:0-01 1-112-0013-1004-1015-00016-000007-00001传传100个按比例出现的八进制数字需个按比例出现的八进制数字需W(T)=285个二进制数个二进制数字字,用等长码用等长码(长为长为3)需要用需要用 300个数字个数字.29根树的周游及其应用根树的周游及其应用对一棵根树的每个顶点访问一次且仅访问一次称作对根对一棵根树的每个顶点访问一次且仅访问一次称作对根树的树的行遍行遍或或周游周游 行遍行遍2元有序正则树的方式：元有序正则树的方式：中序行遍法中序行遍法:左子树、树根、右子树左子树、树根、右子树 前序行遍法前序行遍法:树根、左子树、右子树树根、左子树、右子树 后序行遍法后序行遍法:左子树、右子树、树根左子树、右子树、树根30实例实例例例3中序行遍中序行遍:前序行遍前序行遍:后序行遍后序行遍:b a(f d g)c e)a b(c(d f g)e)b(f g d)e c)a带下划线的是带下划线的是(子子)树根树根,一对括号内是一棵子树一对括号内是一棵子树31波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法用用2元有序正则树表示算术运算算式如下元有序正则树表示算术运算算式如下:以中序行遍方以中序行遍方式将运算符和数标记在顶点上式将运算符和数标记在顶点上,即将运算符放在分支点上即将运算符放在分支点上,数放在树叶上数放在树叶上,每个运算符对它所在分支点的每个运算符对它所在分支点的2棵子树进棵子树进行运算行运算,并规定左子树是被除数或被减数并规定左子树是被除数或被减数.例例4 右图表示算式右图表示算式(b+(c+d)a)(e f)(g+h)(i j)32波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法(续续)波兰符号法波兰符号法(前缀符号法前缀符号法):按前序行遍法访问按前序行遍法访问,不加括号不加括号.从右到左进行从右到左进行,每个运算符对其后面紧邻两个数进行运算每个运算符对其后面紧邻两个数进行运算.逆波兰符号法逆波兰符号法(后缀符号法后缀符号法):按后序行遍法访问按后序行遍法访问,不加括号不加括号.从左到右进行从左到右进行,每个运算符对前面紧邻两数运算每个运算符对前面紧邻两数运算.例例4(续续)波兰符号法波兰符号法逆波兰符号法逆波兰符号法 b+c d a e f +g h i j b c d+a e f g h+i j 33
