离散数学特殊图课件.ppt

《离散数学特殊图课件.ppt》由会员分享，可在线阅读，更多相关《离散数学特殊图课件.ppt（56页珍藏版）》请在三一办公上搜索。

1、树,.1 无向树及生成树定义 9.1 连通无回路的无向图称为无向树,简称树,常用T表示树。(即树是不包含回路的连通图)平凡图称为平凡树。若无向图G至少有两个连通分支,则称G为森林。在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支点。,例 9.1 判断下列哪些图是树？,v1,v2,v3,v4,v5,v1,v2,v3,v4,v5,v1,v2,v4,v3,v5,(a),(b),(c),解:图(a)是树,因为它连通又不包含回路。图(b),(c)不是树,因为图(b)虽连通但有回路,图(c)虽无回路但不连通。在图(a)中,v1、v4、v5为均为叶，v2、v3均为分支节点。,例 9.2 连通图、

2、树和森林之间的相互转换。,定理 9.1 设G=,则下面各命题是等价的：（1）G连通而不含回路（G是树）。（2）G中每对顶点之间存在唯一的路径。（3）G中无回路且 n=m+1。（4）G是连通的且 n=m+1。(5)G中没有回路，但在任何两个不同的顶点 之间加一条新边，在所得的图中得到唯 一的一个含新边的圈。(6)G是连通的且G中任何边均为桥。(7)G是连通的,但删除任何一条边后，就不 连通了。其中n为G中顶点数，m为边数。,以上两个定理给出了无向树的主要性质，利用这些性质和握手定理，可以画出阶数n比较小的所有非同构的无向树。,定理9.2 设T是n阶非平凡的无向树，则T中 至少有两片树叶。证:因为

3、T是非平凡树,所以T中每个顶点的度数都大于等于1,设T有k片树叶,则有(n-k)个顶点度数大于等于2,由握手定理及定理9.1可知 2m=d(vi)k+2(n-k)由定理9.1可知,m=n-1,将此结果代入上式后解得 k 2.,例9.3：画出5阶所有非同构的无向树。,解：设Ti为5阶无向树,则Ti的边数为4，Ti的度序列之和为8，(Ti)4,(Ti)1,可能的度序列为：(1)1,1,1,1,4(2)1,1,1,2,3(3)1,1,2,2,2,称只有一个分支点且其度数为n-1的n阶无向树为星形图，称唯一的分支点为星心。,解：由握手定理 2m=d(vi)及定理9.1 n=m+1 设G有n个顶点,则有

4、下列关系式 5 x 1+3 x 2+(n-5-3)x 3=2 x(n-1)解得：n=11,例9.3：无向树G有5片树叶，3个2度分支点，其余分支点均为3度，问G有多少个顶点？,解：由握手定理 2m=d(vi)及定理9.1 n=m+1 设G有t个1顶点,则有下列关系式 2 x 2+3+4 x 3+t=2 m=2 x(n-1)=2 x(2+1+3+t-1)解得：t=9,例9.4：无向树G有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为多少？,解：设G有t个4度分支点,则有下列关系式 8 x 1+2 x 3+t x 4=2 x(8+2+t-1)解得：t=2 则G中共有12个顶点，11条边

5、，度数序列之 和为22，(Ti)=4,(Ti)=1,度序列为：1,1,1,1,1,1,1,1,3,3,4,4 其非同构的图形为：,n,例 9.5：无向树G有8片树叶，2个3度分支点，其余分支点均为4度，问G有多少个4度分支点？画出其非同构的情况。,其非同构的图形为：,图中，红色边表示生成树，白色边组成其余树。可见，余树可能不连通，也可能含回路。,定义9.2 设T是无向图G的生成子图并且为树，则称T为G的生成树。G在T中的边称为T的树枝，G不在T中的边称为T的弦。T的所有弦的集合的导出子图称为T的余树,在下图中，(2)为(1)的一棵生成树T，(3)为T的余树，注意：余树不一定是树。一个无向连通图

6、，如果它本身不是树，它的生成树是不唯一的。但所有的连通图都具有生成树。事实上，若G是连通图，又G中无回路，则G本身就是树。,a,b,c,d,e,a,b,c,d,e,a,b,c,d,(1),(2),(3),定理9.3 无向图G具有生成树 G是连通图。推论1 设G是n阶m条边的无向连通图，则m n-1。推论2 设G是n阶m条边的无向连通图，T为G 的生成树，则T的余树T中含有 m-n+1边(即T有m-n+1条弦)。,定义9.3 设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,em-n+1为T的弦，设Cr为T添加弦er产生的G的回路，r=1,2,m-n+1。则称Cr为对应于弦er的基本回路

7、，称C1,C2,Cm-n+1为对应生成数T的基本回路系统，,a,b,c,d,e,f,在右图中,Ca=aed,Cb=dbf,Cc=cef,为对应生成树T的基本回路，Ca,Cb,Cc为T的基本回路系统。一个连通图G对应不同的生成树的基本回路及基本回路系统可能不同，但基本回路的个数G所固有的参数(弦)，等于m-n+1,定义 9.4 设T是n阶连通图G的一棵生成树,称T的n-1个树枝对应的G的n-1个割集（每个割集只含一个树枝，其余的边都是弦）S1,S2,Sn-1为对应生成树T的G的基本割集,称S1,S2,Sn-1为对应生成树T的基本割集系统。,a,b,c,d,e,f,在右图中,T的树枝d对应G的一个

8、割集d,b,a,e对应一个割集e,a,c,树枝f对应一个割集f,c,b。3个树枝对应的G的割集的特点是：每个割集中只含一个树枝，其余的边都是弦。这样的割集称为基本割集。,例9.5 在右下图所示的图G中,实数边所构成的子图是G的一棵生成树T，求T对应的基本回路和基本回路系统，基本割集和基本割集系统解:G中顶点数n=6,边数m=9，基本回路个数为m-n+1=4,即T有4条弦，f,g,h,i。对应每条弦有一个基本回路：Cf=face;Cr=gba;Ch=hdcb;Ci=ied;基本回路系统为 Cf,Cr,Ch,Ci,a,b,c,d,e,f,g,h,i,T有5个树枝a,b,c,d,e,因而有5个基本割

9、集:Sa=a,g,f;Sb=b,g,h;Sc=c,f,h;Sd=d,i,h;Se=e,f,i 基本割集系统为,Sa,Sb,Sc,Sd,Se,定义9.5 设无向连通带权图G=,T是G的一棵生成树，T的各边权之和称为T的权，记作W(T)。G的所有生成树中权最小的生成树称为G的最小生成树。求最小生成树的算法很多，我们只介绍避圈法（Kruskal算法）,设n阶无向连通带权图G=有m条边,不妨设G中无环(否则可先删去)，算法为：将m条边按权从小到大顺序排列，设为 e1,e2,em。(2)取e1在T中，然后依次检查e2,em，若ej(j=2,3,m)与T中的边不能构成回路，则取ej在T中，否则放弃ej，考

10、虑下一条边，直至jm。(3)算法停止时得到的T为G的最小生成树。,Kruskal算法 一种求最小生成树的算法,例9.6 用避圈法求下图所示的最小生成树,a,b,c,d,e,f,5,5,5,5,1,3,6,6,4,2,解:W(T)=1+2+3+4+5=15,注意：最小生成树的结点数与原图相等，边的数目比原图少。,避圈法 Kruskal(克鲁斯卡尔算法),例9.7：铺设一个连接各个城市的光纤通信网络,f,e,例9.8：铺设一个连接各个城市的光纤通信网络。（单位：万元）,1,1,3,1,。,。,。,。,。,OK!,例9.9：用Kruskal算法求下图的最小生成树。,例9.10：用Kruskal算法求

11、下图的最小生成树。,W(T)=1+1+2+3+2+5=14,W(T)=1+1+2+3+2+5=14,破圈法,上述算法是贪婪地增加不构成回路的边，以求得最小生成树(最优树)，所以通常称为“避圈法”；我们还可以从另一个角度来考虑最小成树(最优树)问题，由G的圈（回路）最优条件，我们也可以在原连通权图G中逐步删除构成回路中权最大的边，最后剩下的无回路的生成子图为最小成树(最优树)。我们把这种方法称为“破圈法”。,例 9.11 在图(a)中给出了一个连通图,求此图的生 成树,(a),2,例9.12 用“破圈法”求其最优树的过程。,设D是有向图,如果略去有向边的方向所得无向图为一棵无向树,则称D为有向树

12、。其中根树最为重要。定义 9.6 设T是n(n 2)阶有向树，若T中有一个顶点的入度为0，其余的顶点的入度均为1，则称T为根树，入度为0的顶点称为树根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和树根统称为分支点，,9.2 根树及其应用,(1),(2),v0,v1,v2,v3,v4,v5,v6,v7,v0,v1,v2,v3,v4,v5,v6,v7,例 9.13 下图(1)为一棵根树。V0为树根,v1,v4,v3,v6,v7为树叶,v2,v5为内点,v0,v2,v5为均为分支点,由于在根树中有向边的方向均一致,故可省掉其方向,如图(2),(1),(2),v0,v1,v

13、2,v3,v4,v5,v6,v7,v0,v1,v2,v3,v4,v5,v6,v7,从树根到T的任意顶点v的通路（路径）长度称为v的层数，层数最大顶点的层数称为树高平凡树也称为根树。例 9.14 下图(1)中,v1,v2,v3,在第一层上，v4,v5 在第二层上，v6,v7在第三层上。树高为3。,定义9.7 设T为一棵根树，a为T中的一个顶点，且a不是树根，称a及其后代导出的子图T为 T的以a为根的子树，简称根子树。,如图所示，由于各有向边的方向一致，故常省略，并且树根在最上方。,a,定义9.8 设T为根树，若将T中层数相同的 顶点都标定次序，则称T为有序树 根据根树T中每个分支点儿子数以及是否

14、有序，可以将根树分成下列各类；定义9.9 设T为一棵根树 若T的每个分支点至多有r个儿子,则称 T为 r 元树(r叉树)；若T的每个分支点都恰好有r个儿子,则 称它为 r 元正则树。,若r元树T是有序的,则称T为r元有序树 若r元正则树T是有序的，则称T为r元正 则有序树。若T是r元正则树，且所有树叶的层数相 同，则称T为r元完全正则树 若r元完全正则树T是有序树，则称T是 r元有序完全正则树。,二元(叉)树二元(叉)正则树,二元(叉)完全正则树,在所有的r元有序正则树中，2 元有序正则树最重要。,例 9.15,例9.16：求2元树T的权。,解:W(T)=32+22+33+53+3 2=40,

15、是不是最优2元树呢？,定义9.9 设2元树T有t片树叶，v1,v2,vt,权分别为w1,w2,wt，称 W(t)=为T的权，其中L(vi)是vi的层数，在所有有t片树叶，带权w1,w2,wt的2元树中，权最小的2元树称为最优2元树。,例:9.17 在下图所示的三棵树中,都是带权1,3,4,5,6的二元树,W(T1)=47,W(T2)=54,W(T3)=42,但它们中有无最优2元树 还不知道,T1,T2,T3,4,5,1,6,3,3,4,5,6,1,1,3,6,4,5,用此算法求上例的最优二叉树。,给定实数w1,w2,wt,且w1 w2 wt（1）连接权为w1,w2的两片树叶,得一个分支点 其权

16、为w1+w2。（2）在w1+w2,w3,wt中选出两个最小的权,连接它们对应的顶点(不一定是树叶),得新 分支点及所带的权。（3）重复(2),直到形成t-1个分支点,t片树叶 为止。,Huffman算法 一种求最优二叉树的算法,例:9.18 求带权1,3,4,5,6的最优二元树。,4,4,8,1,3,3,8,4,3,1,1,3,4,5,6,4,4,11,5,6,1,4,8,11,19,连接权为w1,w2的两片树叶,得一个分支点其权为w1+w2,在w1+w2,w3,wt中选出两个最小的权,连接它们对应的顶点(不一定是树叶),得 分支点及所带的权,重复,直到形成t-1个分支点,t片树叶为止(若得到

17、的权比后续的两个权大,则另开分支),(1),(2),(3),(4),例:9.19 求带权 3,4,5,6,12的最优二元树。,解：共分为四个步骤：,3,4,7,5,6,11,6,5,4,3,7,11,18,3,4,5,6,7,11,18,12,30,例:9.20 求带权 2,4,7,8,10,12的最优二元树。,这棵最优树的权为:2*4+4*4+7*3+12*2+8*2+10*2=105一般来说,带权w1,w2,wn的最优树不一定是唯一的,最优二叉树在通信编码中的应用,定义9.11 设=12 n-1n为长为n的符号串,称其子串 1,12,12 n-1 分别为该符号串的长度为1,2,n-1的前缀

18、,设B=1,2,m 为一个符号串集合,若对于任意的i,j B,i j,i,j 互不为前缀,则称B为前缀码,若符号串中i(i=1,2,m)只出现0,1两个符号,则称B为二元前缀码。,那么：00,01,100,1010,1011,11111 abc,cba,bca,bac,acb,cab 1,00,011,01001,01000 是(二元)前缀码吗？,如何产生二元前缀码呢？,如：0,10,110,1111 1,01,001,0001 等是(二元)前缀码而 1,11,101,001,0011 不是(二元)前缀码,给定一棵2叉树T，设它有t片树叶。设v为T的一个分支点，则v至少有一个儿子，最多有两个儿

19、子。若v有两个儿子，在由v引出的两条边上，左边的标上0，右边的标上1；若v有一个儿子，在由v引出的边上可标上0，也可标上1。设vi为T的任一片树叶，从树根到vi的通路上各边的标号组成的0，1串组成的符号串放在vi处，t片树叶处的t个符号串组成的集合为一个二元前缀码。,用二叉树产生二元前缀码之做法,由上面做法知，vi处的符号串的前缀均在vi所在的通路上除vi外的顶点处达到，因而所得符号串集合为二元前缀码。若T存在单子分支点，则由T产生的前缀码可能不唯一。若T为正则2叉树,则由T产生的前缀码唯一,0,1,0,1,1,0,1,0,1,00,0100,0101,011,11,例9.21 右图所示的二元

20、树产生的前缀吗为11,00,011,0100,0101,由一棵给定的2叉正则树，可以产生唯一的一个二元前缀码。,0,1,0,0,0,1,1,1,例9.22 右图所示的是一棵2叉正则树,它产生唯一的一个二元前缀码是000,001,01,10,11。,提示 把各字符看作为树叶,各字符出现的频率(或n倍的频率)作为其相应的权,利用Huffman算法求出最优2叉树,由此产生的前缀码即为最佳前缀码。,利用Huffman算法求出的最优2叉树产生的前缀码称为最佳前缀码。,例9.23 在通信中,0,1,2,3,4,5,6,7出现的频率如下 0：30,1：20,2：15 3：10,4：10,5：5 6：5,7：

21、5 求传输它们的最佳前缀码,例9.24 在通信中,0,1,2,3,4,5,6,7出现的频率如下 0：30,1：20,2：15 3：10,4：10,5：5 6：5,7：5 求传输它们的最佳前缀码,100,60,40,30,30,20,20,15,15,10,5,5,5,0,1,0,1,0,1,0,1,0,1,0,1,10,10,0,1,00000,00001,0001,001,100,101,11,01,解:将各字符出现的频率作为其相应的权1=5,2=5,3=5,4=10,5=10,6=15,7=20,8=30为8个权,利用Huffman算法求出的最优2叉树如图所示(码长取3,如101传5),例

22、9.24 在通信中,0,1,2,3,4,5,6,7出现的频率如下0:30,1:20,2:15,3:10,4:10 5:5,6:5,7:5求传输它们的最佳前缀码,100,60,40,30,30,20,20,15,15,10,5,5,5,0,1,0,1,0,1,0,1,0,1,0,1,10,10,0,1,00000,00001,0001,001,100,101,11,01,图中方框中的8个码子是最佳前缀码。树T是带权1,2,8的最优二元树。带权为i的树叶vi对应的码子传输出现频率为i,的数字，即,11传1,101传401传0,0001传5 001传2,101传4 11传1,00001传6 100传

23、3,00000传7,对于一棵根树的每个顶点都访问一次且仅一次称为行遍或周游一棵树。对于2叉有序正则树主要有以下三种周游方式：中序行遍法，访问的次序为：左子树，树根，右子树。前序行遍法，访问的次序为：树根，左子树，右子树。后序行遍法，访问的次序为：左子树，右子树，树根。,二叉树的周游及应用,例9.25 试用三种周游方式行遍下图。,例9.25 试用三种周游方式行遍下图。,中序行遍法访问的次序为：左子树，树根，右子树。,(a(b+c)+def)(g+(h-i)j),中序行遍法访问此树：,例9.25 试用三种周游方式行遍下图。,前序行遍法访问的次序为：树根，左子树，右子树。,前序行遍法访问此树：,(+(a(+b c)d(e f)+g(-h i j),特点：运算符在参加运算的两个数之前，每个运算符与它后面紧邻的两个数进行运算。,例9.25 试用三种周游方式行遍下图。,后序行遍法访问的次序为：左子树，右子树，树根,a b c+de f+g h i-j+,特点：运算符在参加运算的两个数之后，每个运算符与它前面紧邻的两个数进行运算。,后序行遍法访问此树：,结 束 语,本课程到此结束感谢同学们的参与配合！,