离散数学图论精选文档.ppt

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

1、离散数学图论离散数学图论1本讲稿第一页，共三十一页上节知识回顾上节知识回顾图图G=G=，其中V V是非空点集，E E是边集无向图无向图有向图有向图连通图连通图非连通图非连通图树树：是一种特殊的图：是一种特殊的图无向树无向树有向树有向树2本讲稿第二页，共三十一页上节知识回顾上节知识回顾7-7 7-7 无向树及其性质无向树及其性质定义定义7-7.1 7-7.1 v连通无回路的无向图称为连通无回路的无向图称为无向树无向树，简称，简称树树,常用常用T T表示树。表示树。v平凡图称为平凡图称为平凡树。平凡树。v若无向图若无向图G的每个连通分支都是树，则称的每个连通分支都是树，则称G为为森林森林。v在无向

2、树中，度为在无向树中，度为1 1的结点称为的结点称为树叶树叶，度数大于或等于，度数大于或等于2 2的结点称为的结点称为分枝点分枝点或或内点内点。3本讲稿第三页，共三十一页上节知识回顾上节知识回顾定理定理7-7.17-7.1 设设G=G=是是n n阶阶m m条边的无向图条边的无向图,则下面各命题是等则下面各命题是等价的：价的：（1 1）G G是是树树。（2 2）G G中任意两个结点之间中任意两个结点之间有且仅有有且仅有一条路。一条路。（3 3）G G中无回路且中无回路且m=n-1m=n-1。（4 4）G G是连通的且是连通的且m=n-1m=n-1。(5)G(5)G是连通的且是连通的且G G中任何

3、边均为中任何边均为桥桥。(6)G(6)G中没有回路，但在任何两个不同的结点之间加一条新中没有回路，但在任何两个不同的结点之间加一条新边，在所得的图中得到唯一的一个含新边的边，在所得的图中得到唯一的一个含新边的圈圈。4本讲稿第四页，共三十一页7-8 根树及其应用根树及其应用1 1、根树的相关定义、根树的相关定义2 2、根树的性质及应用、根树的性质及应用 二叉树、二叉树、m m叉树叉树3 3、小结、小结本节内容安排本节内容安排5本讲稿第五页，共三十一页第七章第七章 图论图论定义定义7-8.17-8.1设设D是有向图，若不考虑是有向图，若不考虑D图边的方向时是一棵无向树，则称图边的方向时是一棵无向树

4、，则称D为为有向树有向树。V V1 1。V V2 2。V V5 5。V V3 3。V V4 4。V V6 6。V V7 7。V V8 8。V V9 9。如：如：结点度结点度的概念如前所讲的概念如前所讲6本讲稿第六页，共三十一页第七章第七章 图论图论设设T是是n(n 2)阶有向树，阶有向树，若若T中恰好有一个结点的入度为中恰好有一个结点的入度为0，其余结点的入度均为其余结点的入度均为1，则称，则称T为为根树根树定义定义7-8.27-8.2根树根树l入度为入度为0的结点称为的结点称为根根l层次最大结点的层次称为层次最大结点的层次称为树高树高l入度为入度为1出度为出度为0的结点称为的结点称为叶叶l出

5、度不为出度不为0的结点称为的结点称为内点内点或或分枝点分枝点l从树根到从树根到T的任意结点的任意结点v的单向通路长度称的单向通路长度称为为v的的层次层次定义定义7-8.3：根树包含一个或多个结点，这些结点中某一：根树包含一个或多个结点，这些结点中某一个称为个称为根根，其他所有结点被分成有限个，其他所有结点被分成有限个子根树子根树l平凡树也称为根树。平凡树也称为根树。V V1 1。V V2 2。V V5 5。V V3 3。V V4 4。V V6 6。V V7 7。V V8 8。V V9 9。7本讲稿第七页，共三十一页第七章第七章 图论图论由于各有向边的方向一致，故常由于各有向边的方向一致，故常省

6、略，并且树根在最上方省略，并且树根在最上方。V V1 1。V V2 2。V V5 5。V V3 3。V V4 4。V V6 6。V V7 7。V V8 8。V V9 9。V V1 1。V V2 2。V V5 5。V V3 3。V V4 4。V V6 6。V V7 7。V V8 8。V V9 9。V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7 7V V8 8V V9 9在根树中，若将在根树中，若将T中层数相同的中层数相同的结点都标定次序，则称结点都标定次序，则称T为为有序有序树树。根树的不同画法：根树的不同画法：8本讲稿第八页，共三十一页第七章第七章 图论图论设

7、设T为一棵非平凡的根树，为一棵非平凡的根树，v vi i,v vj j V(T),若若v vi i 可达可达vj j,则称则称v vi i为为vj j的的祖先祖先,vj j 为为v vi i的的后代后代若若v vi i邻接到邻接到vj j（即（即 E(T)），则称），则称v vi i为为vj j的的父亲父亲，而而vj j为为v vi i的的儿子儿子若若vj j,vk k的父亲相同，则称的父亲相同，则称vj j与与vk k是是兄弟兄弟。补充定义补充定义V V1 1。V V2 2。V V5 5。V V3 3。V V4 4。V V6 6。V V7 7。V V8 8。V V9 9。9本讲稿第九页，共三

8、十一页第七章第七章 图论图论定义定义7-8.47-8.4在根树在根树T中，中，若每个结点的若每个结点的出度出度的小于或等于的小于或等于r，则称，则称T为为r叉树叉树。若每个结点的若每个结点的出度出度恰好等于恰好等于r或或0，则称，则称T为为完全完全r叉树叉树。若完全若完全r叉树所有叉树所有树叶层次树叶层次相同，则称相同，则称T为为正则正则r叉树叉树。当当r=2时，称为二叉树。时，称为二叉树。10本讲稿第十页，共三十一页第七章第七章 图论图论例：例：。二叉树二叉树?正则二叉树正则二叉树?请证明请证明在完全二叉树中，边的总数等于在完全二叉树中，边的总数等于2(nt-1)，nt为树叶数。为树叶数。完

9、全二叉树完全二叉树?11本讲稿第十一页，共三十一页第七章第七章 图论图论二叉树在实际生活中应用广泛。二叉树在实际生活中应用广泛。例如：例如：M和和E两人进行象棋两人进行象棋比赛，规定一人连胜两盘比赛，规定一人连胜两盘或共胜三盘即为获胜，则或共胜三盘即为获胜，则所有可能的比赛结果可用所有可能的比赛结果可用如下二叉树来描述。如下二叉树来描述。在在m叉树中，二叉树相对来讲比较容易处理，所以常常把叉树中，二叉树相对来讲比较容易处理，所以常常把m叉树的问叉树的问题转换到二叉树上来讨论。题转换到二叉树上来讨论。比赛开始比赛开始比赛开始比赛开始12本讲稿第十二页，共三十一页第七章第七章 图论图论根树应用根树

10、应用1 1：一棵：一棵m m叉有序树改写为一棵二叉树方法叉有序树改写为一棵二叉树方法任何一棵有序树都可以改写为一个对应的二叉树：任何一棵有序树都可以改写为一个对应的二叉树：除了除了最左边最左边的分枝结点外，删去所有从每一个结点长出的分的分枝结点外，删去所有从每一个结点长出的分枝。在同一层次中，枝。在同一层次中，兄弟结点之间用从左到右的有向边兄弟结点之间用从左到右的有向边连连接。接。选定二叉树的左儿子和右儿子如下：直接处于给定结点下面选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为的结点，作为左儿子左儿子，对于同一水平线上与给定结点右邻的结，对于同一水平线上与给定结点右邻的结点，

11、作为点，作为右儿子右儿子，依次类推。，依次类推。13本讲稿第十三页，共三十一页第七章第七章 图论图论例：把下面的例：把下面的m叉树改写为二叉树。叉树改写为二叉树。除了除了最左边最左边的分枝结点的分枝结点外，删去所有从每一个外，删去所有从每一个结点长出的分枝结点长出的分枝在同一层次中，兄弟结在同一层次中，兄弟结点之间用从左到右的有点之间用从左到右的有向边连接向边连接直接处于给定结点下面的结点，直接处于给定结点下面的结点，作为作为左儿子左儿子，对于同一水平线上与给，对于同一水平线上与给定结点右邻的结点，作为定结点右邻的结点，作为右儿子右儿子14本讲稿第十四页，共三十一页第七章第七章 图论图论练习：

12、把下面的有序树改写为二叉树。练习：把下面的有序树改写为二叉树。知识点提示知识点提示：l此方法可推广至有序森林到二叉树的转换。此方法可推广至有序森林到二叉树的转换。l此方法具有可逆性。此方法具有可逆性。课下自学课下自学15本讲稿第十五页，共三十一页第七章第七章 图论图论定理定理7-8.17-8.1 设有完全设有完全m叉树，共有叉树，共有t片树叶，片树叶，i 个分枝点，则个分枝点，则(m-1)i=t-1。证明：证明：完全完全m叉树中结点总数为叉树中结点总数为:t+i也可表示为也可表示为 mi+1故得故得 (m-1)i=t-1根树应用根树应用2 2：完全：完全m m叉树的应用叉树的应用。16本讲稿第

13、十六页，共三十一页第七章第七章 图论图论例例：有：有28盏灯，拟用一个电源插座，问至少需要多少块四插座盏灯，拟用一个电源插座，问至少需要多少块四插座的接线板？的接线板？解：解：将四叉树的每个分枝点看作是四插座的接线板，树叶看作是灯，将四叉树的每个分枝点看作是四插座的接线板，树叶看作是灯，则根据则根据定理定理7-8.17-8.1可知需要可知需要9块。块。请思考？请思考？分析：分析：四插座四插座m叉树叉树m接线板接线板分枝点分枝点i灯灯 树叶树叶 t完全完全完全完全mm叉树，有叉树，有叉树，有叉树，有t t片树叶，片树叶，片树叶，片树叶，i i 个个个个分枝点，则分枝点，则分枝点，则分枝点，则(m

14、-1)i=t-1(m-1)i=t-117本讲稿第十七页，共三十一页第七章第七章 图论图论根树应用根树应用3 3：二叉树的应用：二叉树的应用最优树问题最优树问题定义定义7-8.57-8.5 在根树中，在根树中，l一个结点的一个结点的通路长度通路长度为从树根到此结点的通路中的边数。为从树根到此结点的通路中的边数。l分枝点的通路长度称为分枝点的通路长度称为内部通路长度内部通路长度。l树叶的通路长度称为树叶的通路长度称为外部通路长度外部通路长度。A A18本讲稿第十八页，共三十一页第七章第七章 图论图论定理定理7-8.27-8.2 若完全二叉树有若完全二叉树有n个分枝点，且内部通路长度总和为个分枝点，

15、且内部通路长度总和为L，外部通路，外部通路长度总和为长度总和为E，则，则 E=L+2n。证明：证明：对分枝点数目对分枝点数目n进行归纳证明。进行归纳证明。当当n=1时，如右图所示，时，如右图所示，L=0，E=2，显然，显然，E=L+2n成立。成立。19本讲稿第十九页，共三十一页第七章第七章 图论图论定理定理7-8.27-8.2 若完全二叉树有若完全二叉树有n个分枝点，且内部通路长度总和为个分枝点，且内部通路长度总和为L，外部通路长度总和为外部通路长度总和为E，则，则 E=L+2n。证明：证明：假设假设n=k-1时成立，即时成立，即E=L+2(k-1)。当当n=k时，若删去一个分枝点时，若删去一

16、个分枝点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本讲稿第二十一页，共三十一页第七章第

17、七章 图论图论定义定义7-8.67-8.6 设二叉树设二叉树T有有t片树叶，片树叶，v1,v2,vt权分别为权分别为1,2,t，称称 (t)=为为T的的权权，其中，其中L(vi)是是vi的层数。的层数。在所有有在所有有t片树叶，带权片树叶，带权1,2,t的二叉树中，权最小的那棵的二叉树中，权最小的那棵二叉树称为二叉树称为最优树最优树。例：求二叉树例：求二叉树T的权。的权。3 32 23 33 35 5解：解：(T)=40是不是最优二叉是不是最优二叉树呢？树呢？22本讲稿第二十二页，共三十一页第七章第七章 图论图论定理定理 7-8.37-8.3 设设T为带权为带权12 t的最优树，则的最优树，则

18、 (1)带权带权1，2的树叶的树叶v1，v2是兄弟。是兄弟。(2)以树叶以树叶v1，v2 为儿子的分枝点，其通路长度最长。为儿子的分枝点，其通路长度最长。定理定理 7-8.47-8.4 设设T为带权为带权12 t的最优树，若将以带权的最优树，若将以带权1，2的树叶为的树叶为儿子的分枝点改为带权儿子的分枝点改为带权1+2 的树叶，得到新树的树叶，得到新树T,则则T也是最也是最优树。优树。23本讲稿第二十三页，共三十一页第七章第七章 图论图论HuffmanHuffman算法算法 一种求最优树的算法一种求最优树的算法给定实数给定实数1,2,t，且，且1 2 t。（1）连接权为）连接权为1,2的两片树

19、叶，得一个分枝点，其权为的两片树叶，得一个分枝点，其权为1+2。（2）在）在1+2,3,t中选出两个最小的权，连接它们对中选出两个最小的权，连接它们对应的结点（不一定是树叶），得新分枝点及所带的权。应的结点（不一定是树叶），得新分枝点及所带的权。用此算法求上例的最优二叉树。用此算法求上例的最优二叉树。（3）重复（）重复（2），直到形成），直到形成t-1个分枝点，个分枝点，t片树叶为止。片树叶为止。24本讲稿第二十四页，共三十一页第七章第七章 图论图论共分为四个步骤：共分为四个步骤：。2 23 35 5。3 33 36 6。2 23 35 5。3 33 36 6。2 23 35 55 5。101

20、0。3 33 36 6。2 23 35 55 5。10101616最优树为最优树为(4)所示，所示，(T)=37(1)(2)(3)(4)练习练习：画一棵权为画一棵权为3,4,5,6,7,8,9的最优的最优二叉树，并计算其权。二叉树，并计算其权。25本讲稿第二十五页，共三十一页第七章第七章 图论图论定义定义7-8.77-8.7 设设 1 2 n-1 n为长为为长为n的符号串，称其子串的符号串，称其子串 1,1 2,1 2 n-1分别为该符号串的长度为分别为该符号串的长度为1,2,n-1的的前缀前缀，设，设A=1,2,m为一个符号串集合，若对于为一个符号串集合，若对于任意的任意的i,j A，i j

21、,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 4：二叉树的应用：二叉树的应用前缀码问题前缀码问题26本讲稿第二十六页，共三十一页第七章第七章 图论图论定理定理7-8.57-8.5 任意一棵任意一棵2叉树

22、的树叶可对应一个前缀码。叉树的树叶可对应一个前缀码。定理定理7-8.67-8.6 任意一个前缀码都对应一棵任意一个前缀码都对应一棵2叉树。叉树。用二叉树产生二元前缀码之做法用二叉树产生二元前缀码之做法给定一棵给定一棵2叉树叉树T，设它有，设它有t片树叶。设片树叶。设v为为T的一个分枝点，则的一个分枝点，则v至少有一个儿子，最多有两个儿子。若至少有一个儿子，最多有两个儿子。若v有两个儿子，在有两个儿子，在由由v引出的两条边上，左边的标上引出的两条边上，左边的标上0，右边的标上，右边的标上1；若；若v有一有一个儿子，在由个儿子，在由v引出的边上可标上引出的边上可标上0，也可标上，也可标上1。设。设

23、vi为为T的的任一片树叶，从树根到任一片树叶，从树根到vi的通路上各边的标号组成的的通路上各边的标号组成的0，1串串组成的符号串放在组成的符号串放在vi处，处，t片树叶处的片树叶处的t个符号串组成的集合为个符号串组成的集合为一个二元前缀码。一个二元前缀码。27本讲稿第二十七页，共三十一页第七章第七章 图论图论由上面做法知，由上面做法知，vi处的符号串的前缀均在处的符号串的前缀均在vi所在的通路上除所在的通路上除vi外外的结点处达到，因而所得符号串集合为二元前缀码。的结点处达到，因而所得符号串集合为二元前缀码。若若T存在单子分枝点，则由存在单子分枝点，则由T产生的前缀码可能不唯一。产生的前缀码可

24、能不唯一。若若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本讲稿第二十九页，共三十一页小小 结结l根树的相关定义根树的相关定义l根树性质及应用根树性质及应用m叉有序树改写为二叉树的方叉有序树改写为二叉树的方法法完全完全m叉树的应用叉树的应用二叉树的应用二叉树的应用最优树问题最优树问题有序树，根树，有序树，根树，r叉树，完全叉树，完全r叉树，正则叉树，正则r叉树叉树本节作业：本节作业：P P337337 7-8 7-8习题习题 (3)(5)(3)(5)30本讲稿第三十页，共三十一页结束语结束语31本讲稿第三十一页，共三十一页