离散数学图论ppt课件.ppt

1,上节知识回顾,图,G=，其中V是非空点集，E是边集,树,：是一种特殊的图,2,上节知识回顾,7-7 无向树及其性质定义7-7.1 连通无回路的无向图称为无向树，简称树,常用T表示树。平凡图称为平凡树。若无向图G的每个连通分支都是树，则称G为森林。在无向树中，度为1的结点称为树叶，度数大于或等于2的结点称为分枝点或内点。,。,3,上节知识回顾,定理7-7.1 设G=是n阶m条边的无向图,则下面各命题是等价的：（1）G是树。（2）G中任意两个结点之间有且仅有一条路。（3）G中无回路且m=n-1。（4）G是连通的且m=n-1。(5)G是连通的且G中任何边均为桥。(6)G中没有回路，但在任何两个不同的结点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。,4,7-8 根树及其应用1、根树的相关定义2、根树的性质及应用 二叉树、m叉树3、小结,本节内容安排,5,第七章 图论,定义7-8.1设D是有向图，若不考虑D图边的方向时是一棵无向树，则称D为有向树。,如：,结点度的概念如前所讲,6,第七章 图论,设T是n(n 2)阶有向树，若T中恰好有一个结点的入度为0，其余结点的入度均为1，则称T为根树,定义7-8.2根树,入度为0的结点称为根,层次最大结点的层次称为树高,入度为1出度为0的结点称为叶,出度不为0的结点称为内点或分枝点,从树根到T的任意结点v的单向通路长度称为v的层次,定义7-8.3：根树包含一个或多个结点，这些结点中某一个称为根，其他所有结点被分成有限个子根树,平凡树也称为根树。,。,7,第七章 图论,由于各有向边的方向一致，故常省略，并且树根在最上方。,在根树中，若将T中层数相同的结点都标定次序，则称T为有序树。,根树的不同画法：,8,第七章 图论,设T为一棵非平凡的根树，vi,vjV(T),若vi 可达vj,则称vi为vj的祖先,vj 为vi的后代若vi邻接到vj（即 E(T)），则称vi为vj的父亲，而vj为vi的儿子若vj,vk的父亲相同，则称vj与vk是兄弟。,补充定义,9,第七章 图论,定义7-8.4在根树T中，若每个结点的出度的小于或等于r，则称T为r叉树。,若每个结点的出度恰好等于r或0，则称T为完全r叉树。若完全r叉树所有树叶层次相同，则称T为正则r叉树。,当r=2时，称为二叉树。,10,第七章 图论,例：,二叉树?,正则二叉树?,请证明在完全二叉树中，边的总数等于2(nt-1)，nt为树叶数。,完全二叉树?,11,第七章 图论,二叉树在实际生活中应用广泛。,例如：M和E两人进行象棋比赛，规定一人连胜两盘或共胜三盘即为获胜，则所有可能的比赛结果可用如下二叉树来描述。,在m叉树中，二叉树相对来讲比较容易处理，所以常常把m叉树的问题转换到二叉树上来讨论。,比赛开始,12,第七章 图论,根树应用1：一棵m叉有序树改写为一棵二叉树方法,任何一棵有序树都可以改写为一个对应的二叉树：除了最左边的分枝结点外，删去所有从每一个结点长出的分枝。在同一层次中，兄弟结点之间用从左到右的有向边连接。选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依次类推。,13,第七章 图论,例：把下面的m叉树改写为二叉树。,除了最左边的分枝结点外，删去所有从每一个结点长出的分枝,在同一层次中，兄弟结点之间用从左到右的有向边连接,直接处于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子,14,第七章 图论,练习：把下面的有序树改写为二叉树。,知识点提示：此方法可推广至有序森林到二叉树的转换。此方法具有可逆性。,课下自学,15,第七章 图论,定理7-8.1 设有完全m叉树，共有t片树叶，i 个分枝点，则(m-1)i=t-1。,证明：完全m叉树中结点总数为:t+i也可表示为 mi+1故得(m-1)i=t-1,根树应用2：完全m叉树的应用,16,第七章 图论,例：有28盏灯，拟用一个电源插座，问至少需要多少块四插座的接线板？,解：将四叉树的每个分枝点看作是四插座的接线板，树叶看作是灯，则根据定理7-8.1可知需要9块。,请思考？,分析：四插座m叉树m接线板分枝点i灯 树叶 t,完全m叉树，有t片树叶，i 个分枝点，则(m-1)i=t-1,17,第七章 图论,根树应用3：二叉树的应用最优树问题,定义7-8.5 在根树中，一个结点的通路长度为从树根到此结点的通路中的边数。分枝点的通路长度称为内部通路长度。树叶的通路长度称为外部通路长度。,A,18,第七章 图论,定理7-8.2 若完全二叉树有n个分枝点，且内部通路长度总和为L，外部通路长度总和为E，则 E=L+2n。,证明：对分枝点数目n进行归纳证明。当n=1时，如右图所示，,L=0，E=2，显然，E=L+2n成立。,19,第七章 图论,定理7-8.2 若完全二叉树有n个分枝点，且内部通路长度总和为L，外部通路长度总和为E，则 E=L+2n。,证明：假设n=k-1时成立，即E=L+2(k-1)。当n=k时，若删去一个分枝点v(即变为叶)，设v与根的通路长度为t,且v的两个儿子是树叶，得到新树T。,由于T 有k-1个分枝点，则E=L+2(k-1)在原树T中，L=L+tE=E+2(t+1)-t=E+t+2,即得 E=L+2n,20,第七章 图论,补充定义 给定一组权1,2,t，不妨设12 t。设有一棵二叉树，共有t片树叶，分别带权1,2,t，该二叉树称为带权二叉树。,21,第七章 图论,定义7-8.6 设二叉树T有t片树叶，v1,v2,vt权分别为1,2,t，称(t)=为T的权，其中L(vi)是vi的层数。在所有有t片树叶，带权1,2,t的二叉树中，权最小的那棵二叉树称为最优树。,例：求二叉树T的权。,解：(T)=40,是不是最优二叉树呢？,22,第七章 图论,定理 7-8.3 设T为带权12 t的最优树，则(1)带权1，2的树叶v1，v2是兄弟。(2)以树叶v1，v2 为儿子的分枝点，其通路长度最长。,定理 7-8.4 设T为带权12 t的最优树，若将以带权1，2的树叶为儿子的分枝点改为带权1+2 的树叶，得到新树T,则T也是最优树。,23,第七章 图论,Huffman算法 一种求最优树的算法给定实数1,2,t，且1 2 t。（1）连接权为1,2的两片树叶，得一个分枝点，其权为1+2。（2）在1+2,3,t中选出两个最小的权，连接它们对应的结点（不一定是树叶），得新分枝点及所带的权。,用此算法求上例的最优二叉树。,（3）重复（2），直到形成t-1个分枝点，t片树叶为止。,24,第七章 图论,共分为四个步骤：,最优树为(4)所示，(T)=37,(1),(2),(3),(4),练习：画一棵权为3,4,5,6,7,8,9的最优二叉树，并计算其权。,25,第七章 图论,定义7-8.7 设12 n-1n为长为n的符号串，称其子串1,12,12 n-1分别为该符号串的长度为1,2,n-1的前缀，设A=1,2,m为一个符号串集合，若对于任意的i,j A，i j,i,j互不为前缀，则称A为前缀码，若符号串中i(i=1,2,m)只出现0，1两个符号，则称A为二元前缀码。,如：1,0,10,01,11,001abc,cba,bca,bac,acb,cab1,00,011,01001,01000是(二元)前缀码吗？,如何产生二元前缀码呢？,根树应用4：二叉树的应用前缀码问题,26,第七章 图论,定理7-8.5 任意一棵2叉树的树叶可对应一个前缀码。,定理7-8.6 任意一个前缀码都对应一棵2叉树。,用二叉树产生二元前缀码之做法给定一棵2叉树T，设它有t片树叶。设v为T的一个分枝点，则v至少有一个儿子，最多有两个儿子。若v有两个儿子，在由v引出的两条边上，左边的标上0，右边的标上1；若v有一个儿子，在由v引出的边上可标上0，也可标上1。设vi为T的任一片树叶，从树根到vi的通路上各边的标号组成的0，1串组成的符号串放在vi处，t片树叶处的t个符号串组成的集合为一个二元前缀码。,27,第七章 图论,由上面做法知，vi处的符号串的前缀均在vi所在的通路上除vi外的结点处达到，因而所得符号串集合为二元前缀码。若T存在单子分枝点，则由T产生的前缀码可能不唯一。若T为正则2叉树，则由T产生的前缀码唯一。,注意：因最优2叉树构造的不唯一性，最佳前缀码也可能不唯一，但其各自对应的最优2叉树的权应该相等。,28,第七章 图论,练：在某通信系统中，a、b、c、d、e、f、g、h各字符的传输频率依次为25%、20%、15%、10%、10%、10%、5%、5%，求传输的最佳前缀码，并求传输10n(n=2)个按上述比例的字符需要多少个二进制数字？若采用等长编码需要多少个二进制数字？,29,小 结,根树的相关定义,根树性质及应用,有序树，根树，r叉树，完全r叉树，正则r叉树,本节作业：P337 7-8习题(3)(5),30,结束语,Thanks,