《离散数学》树.ppt

《《离散数学》树.ppt》由会员分享，可在线阅读，更多相关《《离散数学》树.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第9章章 树树 n9.1 无向树及生成树无向树及生成树n9.2 根树及其应用根树及其应用 19.1 无向树及生成树无向树及生成树 无向树、森林无向树、森林树枝、弦、余树树枝、弦、余树生成树生成树基本回路与基本回路系统基本回路与基本回路系统基本割集与基本割集系统基本割集与基本割集系统最小生成树最小生成树 2无向树从无向图出发定义的树无向树从无向图出发定义的树n无向树无向树(树树):连通而无回路的无向图，一般用连通而无回路的无向图，一般用T表示表示n树叶树叶:树中度数为树中度数为1的顶点的顶点n分支点分支点:树中度数树中度数 2的顶点的顶点n森林森林:一一个个非非连连通通图图，如如果果其其每每个

2、个连连通通分分支支都都是是树树，则则称称为为森林森林n平凡树平凡树:平凡图，只有一个点且无边的图平凡图，只有一个点且无边的图n右图为一棵右图为一棵12阶树阶树.n声明声明:本章中所讨论的回路均本章中所讨论的回路均n 指简单回路或初级回路指简单回路或初级回路 3无向树的性质无向树的性质定定理理9.1 设设G=是是n阶阶m条条边边的的无无向向图图，则则下下面面各各命命题题是是等价的：等价的：（1）G是树是树(连通无回路连通无回路);（2）G中任意两个顶点之间存在惟一的中任意两个顶点之间存在惟一的路径路径(初级通路初级通路);（3）G中无回路且中无回路且m=n 1;（4）G是连通的且是连通的且m=n

3、 1;（5）G是连通的且是连通的且G中任何边均为桥中任何边均为桥;（6）G中没有回路中没有回路,但在任何两个不同的顶点之间加一条新但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈边后所得图中有惟一的一个含新边的圈.4定理定理9.29.2 设设T T 是是n n阶非平凡的无向树，则阶非平凡的无向树，则T T中至少有两片树叶中至少有两片树叶.证证 设设T T有有x x片树叶，片树叶，m m条边。由握手定理及定理条边。由握手定理及定理9.19.1可知，可知，由上式解出由上式解出x x 2.2.无向树的性质无向树的性质(续续)5例题例题例例1 已已知知无无向向树树T中中,有有1个个

4、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棵非同构的无向树棵非同构的无向树,如图所示如图所示6例题例题例例2 已已知知无无向向树树T有有5片片树树叶叶,2度度与与3度度顶顶点点各各1个个,其其余余顶顶点点的的度度数数均均

5、为为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棵非同构的无向树棵非同构的无向树 7p生成树生成树p设设G G为为无无向向连连通通图图，若若G G的的生生成成子子图图（v=vv=v）是是一一棵棵树树,则称这棵树为则称这棵树为G G的的生成树；生成树；p设设G G的的一一

6、棵棵生生成成树树为为T,T,则则T T中中的的边边称称为为T T的的树树枝枝,在在G G中中而而不在不在T T中的边称为中的边称为T T的的弦弦,p所有弦的集合称为所有弦的集合称为生成树生成树T T的余树的余树 p注意：余树不一定连通注意：余树不一定连通,也不一定不含回路也不一定不含回路.p右图黑边构成生成树右图黑边构成生成树p红边构成余树红边构成余树生成树生成树 8生成树的存在性生成树的存在性 n定理：任何无向连通图至少存在一颗生成树定理：任何无向连通图至少存在一颗生成树.n证 用破圈法.若图中无圈,则图本身就是自己的生成树.否则删去圈上的任一条边,这不破坏连通性,重复进行直到无圈为止,剩下

7、的图是一棵生成树.n推论1：设n阶无向连通图有m条边,则mn1.理解：生成树有n-1条边；少于n-1条边就不连通；n推论2：设n阶无向连通图有m条边,则它的生成树的余树 有mn+1条边.推论3 设 为G的生成树 T 的余树，C 为G 中任意一个圈，则C与 一定有公共边.9基本回路与基本回路系统 n定义：设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,emn+1为T的弦.设Cr为T添加弦er产生的G中惟一的圈(由er和树枝组成),称Cr为对应弦er的基本回路或基本圈,r=1,2,mn+1.称C1,C2,Cmn+1为对应T的基本回路系统.n理解：T是树，有n-1条边；G有m条边，则有m-

8、n+1条弦；树加一条弦后，定会出现回路，即形成圈。对应生成m-n+1条回路；n求基本回路的算法:设弦e=(u,v),先求T中u到v的路径uv,再并上弦e,即得对应e的基本回路.10defabc实线部分构成生成树T，树枝有d,e,f;弦有a,b,c;基本回路（用边的序列表示）：C1=aed;C2=bdf;C3=cef基本回路系统：C1,C2,C3显然，基本回路的个数是固定的11基本割集与基本割集系统基本割集与基本割集系统 n定义 设T是n阶连通图G的一棵生成树,e1,e2,en1为T的树枝，Si是G的只含树枝ei,其他边都是弦的割集,称Si为对应生成树T由树枝ei生成的基本割集,i=1,2,n1

9、.称S1,S2,Sn1为对应T的基本割集系统.理解：基本割集是图G的割集，其边有弦一条树枝构成；有几条树枝就有几个基本割集；基本割集用边的集合表示；n求基本割集的算法:设e为生成树T的树枝,Te由两棵子树T1与T2组成,令 Se=e|eE(G)且e的两个端点分别属于T1与T2 则Se为e对应的基本割集.12实例实例例例 图中红边为一棵生成树图中红边为一棵生成树,求对应它的基本回路系统求对应它的基本回路系统 与基本割集系统与基本割集系统解解 弦弦e,f,g对应的基本回路分别为对应的基本回路分别为 Ce=e b c,Cf=f a b c,Cg=g a b c d,C基基=Ce,Cf,Cg.树枝树枝

10、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.13无向图与最小生成树无向图与最小生成树 对对无向图或有向图的每一条边无向图或有向图的每一条边e附加一个实数附加一个实数w(e),称作称作边边e的权的权.图连同附加在边上的权称作图连同附加在边上的权称作带权图带权图,记作记作G=.设设G 是是G的的子子图图,G 所所有有边边的的权权的的和和称称作作G 的的权权,记记作作W(G).最小生成树最小生成树:带权图的权最小的生成树带权图的权最小的生成树求最小生成树的算法求最小生成树的算法避圈

11、法避圈法(Kruskal)设设G=,将将非环边按权从小到大排序：非环边按权从小到大排序：e1,e2,em.(1)把把e1加入加入T中中(2)检检查查e2,若若e2与与e1不不构构成成回回路路,则则将将e2加加入入T中中,否否则则弃弃去去e2.(3)检查检查e3,重复进行直至得到生成树为止重复进行直至得到生成树为止.14实例实例例例 求图的一棵最小生成树求图的一棵最小生成树 W(T)=381512344567781234456778169.2 根树及其应用据有向图定义的树根树及其应用据有向图定义的树有向树有向树根树、树根、树叶、内点、分支点根树、树根、树叶、内点、分支点家族树、根子树、有序树家族

12、树、根子树、有序树r元树（元树（r元有序树）元有序树）r元正则树（元正则树（r元有序正则树）元有序正则树）r元完全正则树（元完全正则树（r元有序完全正则树）元有序完全正则树）最优最优2元树与元树与Huffman算法算法前缀吗与最佳前缀吗前缀吗与最佳前缀吗中序行遍法、前序行遍法、后续行遍法中序行遍法、前序行遍法、后续行遍法波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法 17有向树与根树的定义有向树与根树的定义 n有向树有向树:基图为无向树的有向图基图为无向树的有向图n根树根树:有一个顶点入度为有一个顶点入度为0,其余的入度均为其余的入度均为1的的非平凡的有向树非平凡的有向树n树根树根:有向树中

13、入度为有向树中入度为0的顶点的顶点n树叶树叶:有向树中入度为有向树中入度为1,出度为出度为0的顶点的顶点n内点内点:-对应分支点对应分支点有向树中入度为有向树中入度为1,出度大于出度大于0的顶点的顶点18n分支点分支点:树根与内点的总称树根与内点的总称n顶点顶点v的层数的层数:从树根到从树根到v的通路长度的通路长度n树高树高:有向树中顶点的最大层数有向树中顶点的最大层数19根树根树(续续)根树的画法根树的画法:树根放上方树根放上方,省去所有有向边上的箭头省去所有有向边上的箭头如右图所示如右图所示 a是树根是树根 b,e,f,h,i是树叶是树叶 c,d,g是内点是内点 a,c,d,g是分支点是分

14、支点 a为为0层层;1层有层有b,c;2层有层有d,e,f;3层有层有g,h;4层有层有i.树高为树高为420家族树家族树定义定义 把根树看作一棵把根树看作一棵家族树家族树:(1)若顶点若顶点 a 邻接到顶点邻接到顶点 b,则称则称 b 是是 a 的的儿子儿子,a 是是 b 的的父亲父亲;(2)若若b和和c为同一个顶点的儿子为同一个顶点的儿子,则称则称b和和c是是兄弟兄弟;(3)若若a b且且a可达可达b,则称则称a是是b的的祖先祖先,b是是a的的后代后代.设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根,称称v及其所有后及其所有后代的导出子图为以代的导出子图为以v为根的为根的根子树

15、根子树.21根树的分类根树的分类n有序树有序树:将将根根树树每每一一层层上上的的顶顶点点都都规规定定次次序序，这这样样的的树树称称为为有有序树序树V1V0V2V4V5V6V7V3比如规定节点顺序：从上到下，从左到右22nr元树元树:根树的每个分支点至多有根树的每个分支点至多有r个儿子个儿子n点的出度不超过点的出度不超过rnr元完全树元完全树:根树的每个分支点恰有根树的每个分支点恰有r个儿子个儿子n内点的度数内点的度数2n正则树正则树所有树叶的层数相同所有树叶的层数相同nr元完全正则树元完全正则树:所有树叶层数相同的所有树叶层数相同的r元正则树元正则树nr元有序树元有序树:有序的有序的r元树元树

16、nr元正则有序树元正则有序树:有序的有序的r元正则树元正则树nr元完全正则有序树元完全正则有序树:有序的有序的r元完全正则树元完全正则树23n定理:在完全m元树T中若树叶数为t,分支点数为i，则有（m-1）ii-1。n定理：若二元完全树有n个分支点,且各分支点的层数之和为,各树叶的层数之和为E,则E=+2n。完全二元树分支点比叶少一个,在完全正则二元树中,树高是K,则叶是2K个,分支点是2K-1个,边是22k-1条边。24带权二元树n给一组数,不妨假设w1w2wt。若有一棵二元树,共有t片叶,分别带权 ,称该二元树为带权二叉树。n树的权：w（i）是叶子Vi的权，L（Vi）是Vi的层数，25在所

17、有有t片树叶,带权 w1,w2,wt 的 2元树中,权最小的2元树称为最优2元树.最优最优2元树元树 26n定理定理:设设T为带权为带权w1w2wt的最优树的最优树,则则n(1)带权带权w1，w2的树叶的树叶vw1，vw2是兄弟；是兄弟；n(2)以树叶以树叶vw1，vw2为儿子的分枝点的通路最长为儿子的分枝点的通路最长证明证明:略，略，n即权越小的叶要挂在路最长的分支点，权越大挂的即权越小的叶要挂在路最长的分支点，权越大挂的叶要挂在路短的分支点上，显然最优树一定是完全叶要挂在路短的分支点上，显然最优树一定是完全二叉树。二叉树。27如何依据给定的权求最优二元树？如何依据给定的权求最优二元树？Hu

18、ffman算法算法:给给定定实实数数w1,w2,wt，求求以以上上述实数为权的最优二元树述实数为权的最优二元树。n哈夫曼算法:给定树求最优树1、给初始权集S=；t个叶子vi带权2、在S中找出两个权最小的数不妨记作w1,w2,用父结点v将两个带权的儿子v1,v2连结起来,形成一个新的子树并把该子树看作一个结点v，带权w1+w2。3.置权集S:=（S-w1,w2w1+w24.检查S中是否只有一个元素？是就停止,否则转入228实例实例例例 求带权为求带权为1,1,2,3,4,5的最优树的最优树.解题过程由下图给出，解题过程由下图给出，W(T)=38（不唯一）（不唯一）29前缀码前缀码 n设设 =1

19、2 n-1 n是长度为是长度为n的符号串的符号串n 的的前缀前缀:1 2 k,k=1,2,n-1 有有n-1个个n前缀码前缀码:1,2,m,其其中中 1,2,m为为非非空空字字符符串串,且且任何两个互不为前缀任何两个互不为前缀n2元前缀码元前缀码:只出现两个符号只出现两个符号(如如0与与1)的前缀码的前缀码如如 0,10,110,1111,10,01,001,110是是2元前缀码元前缀码 0,10,010,1010 不是前缀码不是前缀码30前缀码前缀码(续续)n一棵一棵2元树产生一个二元前缀码元树产生一个二元前缀码:对每个分支点对每个分支点,若关联若关联2条边条边,则给左边标则给左边标0,右边

20、标右边标1;若若只只关关联联1条条边边,则则可可以以给给它它标标0(看看作作左左边边),也也可可以以标标1(看作右边看作右边).将将从从树树根根到到每每一一片片树树叶叶的的通通路路上上标标的的数数字字组组成成的的字字符符串记在树叶处串记在树叶处,所有所有树叶树叶处的字符串构成一个前缀码处的字符串构成一个前缀码.n如右图所示如右图所示31最佳前缀码最佳前缀码例例 在通信中，设八进制数字出现的频率如下：在通信中，设八进制数字出现的频率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%采用采用2元前缀码元前缀码,求传输数字最少的求传输数字最少的2元前缀码元前缀码(称作

21、称作最佳前最佳前缀码缀码),并求传输并求传输10n(n 2)个按上述比例出现的八进制数字需个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的要多少个二进制数字？若用等长的(长为长为3)的码字传输需要的码字传输需要多少个二进制数字多少个二进制数字?解解 用用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优2元树元树.这这里里 w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.最优最优2元树如图所示元树如图所示.32 编码编码:0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-0

22、0001传传100个按比例出现的八进制数字所需二进制数字的个数个按比例出现的八进制数字所需二进制数字的个数为为 W(T)=285.传传10n(n 2)个所用二进制数字的个数为个所用二进制数字的个数为2.85 10n,而用等长而用等长码码(长为长为3)需要用需要用 3 10n个数字个数字.33波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法 行遍行遍(周游周游)根树根树T:对对T 的每个顶点访问且仅访问一次的每个顶点访问且仅访问一次.行遍行遍2元有序正则树的方式：元有序正则树的方式：中序行遍法中序行遍法:左子树、根、右子树左子树、根、右子树 前序行遍法前序行遍法:根、左子树、右子树根、左子树、右

23、子树 后序行遍法后序行遍法:左子树、右子树、根左子树、右子树、根 例如例如,对图所示根树按中序、前序、对图所示根树按中序、前序、后序行遍法访问结果分别为：后序行遍法访问结果分别为：b a(f d g)c e a b(c(d f g)e)b(f g d)e c)a带下划线的是带下划线的是(子子)树根树根,一对括号内是一棵子树一对括号内是一棵子树 34波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法(续续)用用2元有序正则树表示算式元有序正则树表示算式:最高层次运算放在树最高层次运算放在树根上根上,然后依次将运算符放在根子树的根上然后依次将运算符放在根子树的根上,数放数放在树叶上在树叶上,规定被除

24、数、被减数放在左子树树叶上规定被除数、被减数放在左子树树叶上.例如例如,右图表示算式右图表示算式(b+(c+d)a)(e f)(g+h)(i j)35波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法(续续)波兰符号法波兰符号法(前缀符号法前缀符号法):按前序行遍法访问表示按前序行遍法访问表示算式的算式的2元有序正则树元有序正则树,其结果不加括号其结果不加括号,规定每个规定每个运算符号与其后面紧邻两个数进行运算运算符号与其后面紧邻两个数进行运算.例如例如,对上页中树的访问结果为对上页中树的访问结果为 b+c d a e f +g h i j 逆波兰符号法逆波兰符号法(后缀符号法后缀符号法):按后序行遍法访问按后序行遍法访问,规定每个运算符与前面紧邻两数运算规定每个运算符与前面紧邻两数运算.例如例如,对上页中树的访问结果为对上页中树的访问结果为 b c d+a e f g h+i j 36