离散数学图论树精.ppt

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

1、离散数学图论树第1页，本讲稿共43页2022/10/15第七章 图论8.2 树树 树的术语起源于植物学和家谱学。早在1857年，英国数学Arthur Cayley(18211895)就发现了树，当时他正在试图列举形为CnH2n+2的化合物的同分异构体。树具有广泛的应用，特别在计算机科学与管理科学中。如用树构造存储和传输数据的有效编码，用树构造最便宜的电话线连接分布式计算机网络，用树模拟一系列决策完成的过程等。第2页，本讲稿共43页8.2.1 树的概念和基本性质树的概念和基本性质v在图论中：1、连通的无环图称为树树。2、除根之外，度1的顶点称为叶子叶子，度1的顶点称为分支点分支点或者内点内点。叶

2、子叶子分支点分支点根根第3页，本讲稿共43页8.2.1 树的概念和基本性质树的概念和基本性质3、多个树称为森林森林；4、孤立顶点叫做平凡树平凡树。123456789101512131114平凡树平凡树第4页，本讲稿共43页8.2.1 树的概念和基本性质树的概念和基本性质v 定理定理 T=(V,E)是结点数是结点数 n=|V|1 的树，则下述命题等的树，则下述命题等价：价：（1）T是无回路的连通图；是无回路的连通图；（2）T是连通的，且有是连通的，且有n 1条边；条边；（3）T有有n 1条边，且条边，且T中无回路；中无回路；（4）T的任意两点间有且只有唯一的通路；的任意两点间有且只有唯一的通路；

3、（5）T中无回路，但若在中无回路，但若在T的任一对不相邻的顶点之的任一对不相邻的顶点之间增加一条边，则构成间增加一条边，则构成T中的唯一回路。中的唯一回路。第5页，本讲稿共43页1根树根树8.2.2 几类常用树几类常用树有向树有向树 一个弱连通有向图，若去掉方向后得到一棵一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为树，则称此有向图为一棵有向树，记为T。根树根树 一棵有向树一棵有向树T，若其中有且仅有一个结点，若其中有且仅有一个结点v0的的入度为入度为0，其余结点的入度为，其余结点的入度为1，则称，则称T是一棵以是一棵以v0为根为根的根树或的根树或外向树外向树。其中出

4、度为。其中出度为0的结点称为有根树的的结点称为有根树的叶子。叶子。把外向树之定向反过来，得到的有向树叫内向内向树树。v0v0第6页，本讲稿共43页8.2.2 几类常用树几类常用树v根树通常画成倒长的；v一个 结点的子结点画在它的v下一层，边的方向省略；v“同辈兄弟”画在同一层。第7页，本讲稿共43页8.2.2 几类常用树几类常用树树的高度树的高度 设有根树设有根树 T=(V,A)，v0为树根。为树根。u V的深度是从的深度是从v0 开始到达开始到达u的有向路的长度，的有向路的长度，T的高度是从的高度是从v0到到T的叶子的最长路的长度。的叶子的最长路的长度。根结点深度为根结点深度为0，称为第，称

5、为第0层；层；深度同为深度同为i 的结点构成树的第的结点构成树的第i 层；层；具有最大深度的结点的深度称为树的深度具有最大深度的结点的深度称为树的深度（高度）。（高度）。第8页，本讲稿共43页8.2.2 几类常用树几类常用树Tree Node Level and Path Length第9页，本讲稿共43页8.2.2 几类常用树几类常用树2有序树有序树定义定义 对有向树对有向树 T=(V,A)，若，若 u,v V且且 A，则称，则称 u为为v的父亲，的父亲，v为为u的儿子。若从的儿子。若从u到到v存在有向道路，则称存在有向道路，则称u是是v的祖先，的祖先，v是是u的后代（子孙）的后代（子孙）有

6、序树有序树 将各树的每个结点的所有儿子按次序排列，称将各树的每个结点的所有儿子按次序排列，称这样的根树为有序树。这样的根树为有序树。v有序树的每个结点的出度小于或等于有序树的每个结点的出度小于或等于m时，称为时，称为m叉叉有序树。有序树。v有序树的每个结点的出度只为有序树的每个结点的出度只为 0或或 m 时，称为时，称为m叉叉正正则有序树。则有序树。第10页，本讲稿共43页8.2.2 几类常用树几类常用树v例 设有4个银币，已知其中3个一定是真的，真假的区别在于银币的重量，现用一天平设法找出假币。解：用a、b、c、d分别表示银币，a:b表示在天平上作比较。a:ba:cc重c轻a:dd重全真d轻

7、a:ca轻b重a:cb轻a重第11页，本讲稿共43页8.2.2 几类常用树几类常用树容易看出，上例中方法并不唯一。a,b:c,da:cd:cc轻a重a:c全真d:cb重d轻a轻c重a:ba:bb轻d重第12页，本讲稿共43页8.2.2 几类常用树几类常用树三三三三 、最优二叉树最优二叉树最优二叉树最优二叉树二叉树二叉树 除树叶外，每个结点的最多有两个子结点，分别称为左子除树叶外，每个结点的最多有两个子结点，分别称为左子结点和右子结点的根树称为二叉树结点和右子结点的根树称为二叉树v二叉树的另外一个定义：二叉树或者是空树，或者有一个根结点二叉树的另外一个定义：二叉树或者是空树，或者有一个根结点和两

8、个分别称为左右子树的二叉树构成。和两个分别称为左右子树的二叉树构成。二叉树的性质二叉树的性质1)第第i 层的结点数最多为层的结点数最多为2i；2)深度为深度为k的二叉树最多有的二叉树最多有2k+1-1个结点；个结点；3)记二叉树出度为记二叉树出度为2的结点数目为的结点数目为n2，叶子数目为，叶子数目为n0，则有：，则有：n0=n2+14)多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中该结点的左儿子；多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中该结点的左儿子；以结点的右兄弟为对应二叉树中该结点的右儿子。以结点的右兄弟为对应二叉树中该结点的右儿子。第13页，本讲稿共43页8.

9、2.2 几类常用树几类常用树满二叉树满二叉树 二叉树的每个结点的出度或者是二叉树的每个结点的出度或者是0或者是或者是2。满二叉树也称正则二叉树满二叉树也称正则二叉树完美二叉树完美二叉树 满二叉树且所有结点在同一层。满二叉树且所有结点在同一层。对完美二叉树对完美二叉树 的结点按从上到下，同层结点从左到的结点按从上到下，同层结点从左到右的原则编号，得到结点从右的原则编号，得到结点从12k+1-1 的编号序列。得的编号序列。得到上述结点编号的二叉树称为编号二叉树。到上述结点编号的二叉树称为编号二叉树。完全二叉树完全二叉树若设二叉树的高度为若设二叉树的高度为h，除第，除第 h 层外，层外，其它各层其它

10、各层(1h-1)的结点数都达到最大个数，的结点数都达到最大个数，第第 h 层从右向左连续缺若干结点，这就是完层从右向左连续缺若干结点，这就是完全二叉树。全二叉树。第14页，本讲稿共43页8.2.2 几类常用树几类常用树高度为高度为k的完全二叉树，其的完全二叉树，其k-1层以上结点构成一棵高度为层以上结点构成一棵高度为k-1 的完美二叉树。的完美二叉树。完全二叉树的叶结点或者在同一层或者完全二叉树的叶结点或者在同一层或者 在相邻的两层。在相邻的两层。1671213 141511109584231211109876543211671415958423满二叉树完美二叉树完全二叉树第15页，本讲稿共4

11、3页8.2.2 几类常用树几类常用树三三、最优二叉树最优二叉树定义定义设设T是有是有t片叶子的二叉树，其中片叶子的二叉树，其中t片叶子分别带有片叶子分别带有非负实权非负实权 ，则称，则称T为为加权二叉树加权二叉树。称。称W(T)为二叉树为二叉树T的权，其中的权，其中hi为带权为带权wi的树的树叶叶vi的层数。在所有的带权的层数。在所有的带权 的二叉树的二叉树中，带权最小的二叉树称为中，带权最小的二叉树称为最优二叉树最优二叉树(哈夫曼树哈夫曼树)第16页，本讲稿共43页8.2.2 几类常用树几类常用树v【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有

12、许多棵)，它们的带权路径长度分别为：(a)W(T)=7*2+5*2+2*2+4*2=36(b)W(T)=7*3+5*3+2*1+4*2=46(c)W(T)=7*1+5*2+2*3+4*3=35其中(c)树的W最小，它就是最优二叉树最优二叉树(哈夫曼哈夫曼树树)。第17页，本讲稿共43页8.2.2 几类常用树几类常用树vHuffmanHuffman树树Huffman 算法算法 给定给定t个非负实数，构造以它们为叶子带权且具有最小个非负实数，构造以它们为叶子带权且具有最小M(T)的最的最优二叉树。优二叉树。(1)i t；(2)若若 i=1 结束；结束；(3)将将 i 个非负实数权由小到大排列成序，

13、以最小的两个数作为左个非负实数权由小到大排列成序，以最小的两个数作为左右儿子，构造其父亲结点，并以此左右儿子的权值之和作为新右儿子，构造其父亲结点，并以此左右儿子的权值之和作为新构造的父亲结点的权值。在权序列中删去此左右儿子对应的权构造的父亲结点的权值。在权序列中删去此左右儿子对应的权值，增加新构造的父亲结点的权值。值，增加新构造的父亲结点的权值。(4)i i-1，转转(2)。第18页，本讲稿共43页8.2.2 几类常用树几类常用树v例：有例：有4个权值个权值7,5,2,4，试构造一棵有，试构造一棵有4个个叶子结点的哈夫曼树。叶子结点的哈夫曼树。第19页，本讲稿共43页8.2.2 几类常用树几

14、类常用树Huffman树树 由由Huffman算法构造的二叉树称算法构造的二叉树称为相对于非负实数权为相对于非负实数权 wi(i=1,2,t)的的Huffman树。树。定理定理 Huffman树是一棵相对于非负实数权树是一棵相对于非负实数权 wi(i=1,2,t)的最优二叉树。的最优二叉树。第20页，本讲稿共43页8.2.2 几类常用树几类常用树定义：定义：有一个序列的集合，如果在这个集合中。任何序列都不是另一个序列的前缀，则称这个集合为前缀码前缀码。v例如，001是001011的前缀，集合000,001,01,10,11是前缀码，而1,00,01,000,0001不是前缀码。二元前缀码二元前

15、缀码前缀码前缀码A=1,2,m 中的中的 i 只由两种符号（如只由两种符号（如0、1）组成时，称）组成时，称A为一个为一个二元二元前缀码。前缀码。第21页，本讲稿共43页8.2.2 几类常用树几类常用树v对有序二叉树的顶点编码如下：(1)根不标码；(2)兄弟有序，左为兄，标0，右为弟，标1；(3)从根始到叶上的道路依次抄出各点之码，写在叶下方，称该叶的前缀该叶的前缀；(4)全树的叶从左到有把它们的前缀依次抄出，叫做该树的前缀码该树的前缀码，每个叶子的前缀后加逗号，最后一个叶子前缀后加句号。显然有序二叉树与前缀码一一对应。第22页，本讲稿共43页8.2.2 几类常用树几类常用树v例如，0000，

16、0001，001，010，011，100，101，11这一前缀码对应的有序二叉树如下图所示：v0011010100101010000000100101001110010111第23页，本讲稿共43页8.2.2 几类常用树几类常用树Huffman编码编码 以各个源码符号在源码电文中以各个源码符号在源码电文中出现的频率为权值，构造以源码符号为叶子出现的频率为权值，构造以源码符号为叶子的的Huffman树，得到关于源码符号集的一个树，得到关于源码符号集的一个二叉前缀码，称为其二叉前缀码，称为其Huffman编码。编码。定理定理 Huffman编码是关于该源码符号集的最编码是关于该源码符号集的最短二叉

17、前缀码。短二叉前缀码。证明证明 略略第24页，本讲稿共43页8.2.2 几类常用树几类常用树实现译文长度最短的二叉前缀码设计过程：实现译文长度最短的二叉前缀码设计过程：1.字频统计字频统计2.等概率假设等概率假设3.Huffman树构造树构造4.Huffman编码方案确定编码方案确定例例 设一段电文含有设一段电文含有x1,x2,x3,x4,x5,x6,x7共共7个符号，它们个符号，它们出现的频率分别是：出现的频率分别是：x1:35%x2:20%x3:15%x4:10 x5:10%x6:5%x7:5%。试为这。试为这7个符号设计一套最短二个符号设计一套最短二叉前缀编码方案。叉前缀编码方案。第25

18、页，本讲稿共43页8.2.2 几类常用树几类常用树例例第26页，本讲稿共43页8.2.2 几类常用树几类常用树Huffman树的用途很广：vv分支程序的判断流程分支程序的判断流程：如果出现概率越大的分枝（条件语句）离根越近，那么所需执行的判断语句就越少，这样便可提高程序的执行效率；vv文件的压缩文件的压缩：根据文件中字符出现的频率，建成一棵Huffman树，出现次数越多的字符的Huffman编码越短，这样可以达到文件的压缩。第27页，本讲稿共43页8.2.3 生成树生成树生成树生成树如果一棵树T是图G的子图，则树T称为图G的生成树生成树或支撑树支撑树；GE(T)称为树T的余树余树，记作：T；T

19、中的边称为图G的弦弦，也是树T的弦。1234567812345678余树余树弦弦第28页，本讲稿共43页8.2.3 生成树生成树定理定理 任何连通图至少有一棵生成树。任何连通图至少有一棵生成树。证明略证明略定理定理 若连通图G=(V,E)，n=|V|，则图的生成生成树树有n1条边。用归纳法易证明。第29页，本讲稿共43页8.3 平面图平面图 图的平面性问题，除了它的理论意义外，有许多实际应用。例如，单面印刷电路板和集成电路的布线问题。近年来，大规模集成电路的发展促进了图的平面性的研究。第30页，本讲稿共43页8.3.1 平面图的定义平面图的定义 可平面性可平面性 一个图一个图 G=(V,E)，

20、若能将其画在平面上，且任意，若能将其画在平面上，且任意两条边的交点只能是两条边的交点只能是G的顶点，则称的顶点，则称G可嵌入平面，或称可嵌入平面，或称G是可平面的。可平面图在平面上的一个嵌入称为一个平面图。是可平面的。可平面图在平面上的一个嵌入称为一个平面图。v树是一类重要的平面图。树是一类重要的平面图。v应用举例：印刷电路版、集成电路设计。应用举例：印刷电路版、集成电路设计。(a)(b)(c)(a)是可平面图，(b),(c)是(a)的平面嵌入，是平面图。第31页，本讲稿共43页8.3.1 平面图的定义平面图的定义 例例 K5 和和K3,3 是不可平面的。是不可平面的。K5K3,3K5K3,3

21、第32页，本讲稿共43页8.3.1 平面图的定义平面图的定义 区域区域 由平面图的边包围而成，其中不含图的由平面图的边包围而成，其中不含图的顶点。也称为顶点。也称为面面。包围域。包围域R的所有边组成的回的所有边组成的回路称为该域的边界，回路长度称为该域的度，路称为该域的边界，回路长度称为该域的度，记为记为deg(R)。v2R1R2R0v1v3v4v5v6v7各域的边界：各域的边界：R0:v1 v2 v4 v5 v7 v7 v4 v3 v1R1:v1 v2 v4 v3 v1R2:v4 v5 v7 v4 v6 v4R3:v7 v7 例例deg(R0)=8,deg(R1)=4,deg(R2)=5,d

22、eg(R3)=1R3第33页，本讲稿共43页8.3.1 平面图的定义平面图的定义 内部面和外部面内部面和外部面 由平面图的边包围且无穷大的域称为外部由平面图的边包围且无穷大的域称为外部面。（如上例的域面。（如上例的域R0为外部面）为外部面）一个平面图有且只有一个外部面。一个平面图有且只有一个外部面。曲面嵌入曲面嵌入 一个图可嵌入平面当且仅当它可嵌入曲面。一个图可嵌入平面当且仅当它可嵌入曲面。定理定理5-1-1 平面图平面图G的所有域的度之和等于其边的所有域的度之和等于其边数数m的的2倍，即：倍，即：第34页，本讲稿共43页8.3.1 平面图的定义平面图的定义v显然：可平面图的子图仍然是可平面图

23、；包含不可平面图的图是不可平面图；v容易发现，平面图G每增加1条边，图G总的边数和面数都增加1。边界面第35页，本讲稿共43页8.3.2 欧拉公式欧拉公式 定理定理 欧拉公式欧拉公式 （必要条件必要条件）设平面连通图设平面连通图G有有n个顶点，个顶点，m条边，条边，d个域，则有个域，则有 n-m+d=2。证明证明 对对m作归纳。作归纳。m=0,m=1时成立。假定对于时成立。假定对于m=k成立成立:nk-mk+dk=2。当。当m=k+1时，考虑删除一条边后仍然连通的情况。时，考虑删除一条边后仍然连通的情况。(1)如果如果G有回路，则删除回路上一条边后的图边数减少一，面数有回路，则删除回路上一条边

24、后的图边数减少一，面数减少一，故公式对减少一，故公式对G成立：成立：nk-(mk+1)+(dk+1)=2.(2)G没有回路，只有割边，必有度数为一的结点，删除相应割边的没有回路，只有割边，必有度数为一的结点，删除相应割边的一度顶点后，结点数和边数分别减少一，面数不变，故仍然有一度顶点后，结点数和边数分别减少一，面数不变，故仍然有(nk+1)-(mk+1)+dk=2.v欧拉公式对非简单图仍然成立。欧拉公式对非简单图仍然成立。第36页，本讲稿共43页8.3.2 欧拉公式欧拉公式对于对于n个顶点，个顶点，m条棱，条棱，d个面的凸多面体，个面的凸多面体，n-m+d=2.推论推论 设平面图设平面图G的连

25、通分支数为的连通分支数为k，并有，并有n个个顶点，顶点，m条边，条边，d个域，则有个域，则有 n-m+d=k+1。证明证明 对每个连通分支使用欧拉公式，注意它对每个连通分支使用欧拉公式，注意它们共同拥有一个无穷面。们共同拥有一个无穷面。定理 若图G是简单的平面图，则图G至少有一个顶点的度小于小于6。第37页，本讲稿共43页8.3.3 极大平面图极大平面图 极大平面图极大平面图 设设G=(V,E)为简单平面图，为简单平面图，|V|3，若对任意，若对任意vi,vj V，且，且(vi,vj)E，有，有G=(V,E(vi,vj)为非平面图，则称为非平面图，则称G为为一个极大平面图。一个极大平面图。“极

26、大性极大性”乃针对固定顶点数的图的边的数乃针对固定顶点数的图的边的数目而言。目而言。第38页，本讲稿共43页8.3.3 极大平面图极大平面图v极大平面图的性质极大平面图的性质极大平面图是连通图。极大平面图是连通图。极大平面图的每个面都由极大平面图的每个面都由3条边组成。条边组成。极大平面图有极大平面图有3d=2m（d为面数目，为面数目，m 为边数目）。为边数目）。定理定理 设极大平面图设极大平面图G有有n个顶点，个顶点，m条边，条边，d个域，则有个域，则有m=3n-6，d=2n-4。证明证明 将将3d=2m代入欧拉公式。代入欧拉公式。推论推论 简单平面图简单平面图G有有 m 3n-6，d 2n

27、-4。定理定理 简单平面图至少有一个顶点的度小于简单平面图至少有一个顶点的度小于6。证明证明 设任一点的度设任一点的度 6，得，得 m 3n，矛盾。，矛盾。第39页，本讲稿共43页8.3.4 非平面图非平面图 例例 K3,3K5K3,3K5 是不可平面的。是不可平面的。证明证明 如果如果G是平面图，是平面图，则有则有 m 3n-6,将将n=5,m=10代入得到代入得到10 9,矛盾！矛盾！K3,3 是不可平面的。是不可平面的。证明证明 注意注意 K3,3中的回路长中的回路长度是偶数，至少是度是偶数，至少是4，即每即每个面的度数至少是个面的度数至少是4。所以，。所以，4|R|2|E|.如果如果K

28、3,3 是可平是可平面的，则面数面的，则面数=5，由此的由此的20 18。矛盾！。矛盾！第40页，本讲稿共43页8.3.4 非平面图非平面图K5 和和K3,3 称为基本的不可平面图，或称为基本的不可平面图，或 Kuratowski(库拉图斯基)图。图。同胚同胚 设设G是一个平面图，通过删除是一个平面图，通过删除G的一条边的一条边(x,y)，并且添，并且添加一个新结点加一个新结点a和两条边和两条边(x,a)与与(a,y)(所获得的任何图也是平所获得的任何图也是平面图面图)，这样的操作成为初等细分。若可以从相同的图，这样的操作成为初等细分。若可以从相同的图G通过一系列初等细分来获得图通过一系列初等

29、细分来获得图G1和和G2，称，称G1和和G2是同胚是同胚的的(homeomorphism)。例：两个同胚图第41页，本讲稿共43页8.3.4 非平面图非平面图与与K5同胚的图，称为同胚的图，称为K(1)型图；与型图；与K3,3同胚的图，称为同胚的图，称为K(2)型图；型图；K(1)型图和型图和K(2)型图统称型图统称K型图。型图。vKuratowski 定理定理 图图 G=(V,E)可平面当且仅当可平面当且仅当G中不存在任何中不存在任何K型子型子图。图。库拉图斯基定理给出了平面图的充要条件，但库拉图斯基定理给出了平面图的充要条件，但用它并不能得出判别一个图是否为平面图的有效算用它并不能得出判别一个图是否为平面图的有效算法。法。v根据Kuratowski定理，可以断定：所有树树都是平面图。第42页，本讲稿共43页8.3.4 非平面图非平面图v例例彼得森彼得森(petersen)图不是平面图图不是平面图第43页，本讲稿共43页