第8章+图论-8(树)

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

2、子叶子分支点分支点根根4返回 结束3、多个树称为森林森林；4、孤立顶点叫做平凡树平凡树 。123456789101512131114平凡树平凡树5返回 结束v 定理定理 T=(V, E) 是结点数是结点数 n=|V| 1 的树，则下述命的树，则下述命题等价：题等价：（1） T是无回路的连通图；是无回路的连通图；（2）T是连通的，且有是连通的，且有n 1条边；条边；（3）T有有n 1条边，且条边，且T中无回路；中无回路；（4）T的任意两点间有且只有唯一的通路；的任意两点间有且只有唯一的通路；（5）T中无回路，但若在中无回路，但若在T的任一对不相邻的顶点之的任一对不相邻的顶点之间增加一条边，则构成

3、间增加一条边，则构成T中的唯一回路。中的唯一回路。6返回 结束有向树有向树 一个弱连通有向图，若去掉方向后得到一一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为棵树，则称此有向图为一棵有向树，记为T。根树根树 一棵有向树一棵有向树T，若其中有且仅有一个结点，若其中有且仅有一个结点v0的入度为的入度为0，其余结点的入度为，其余结点的入度为1，则称，则称T是一棵以是一棵以v0为根的根树或为根的根树或外向树外向树。其中出度为。其中出度为0的结点称为的结点称为有根树的叶子。有根树的叶子。把外向树之定向反过来，得到的有向树叫内向树内向树。 v0v07返回 结束v根树通常画成倒长的

4、；v一个 结点的子结点画在它的v下一层，边的方向省略；v“同辈兄弟”画在同一层。8返回 结束树的高度树的高度 设有根树设有根树 T=( (V, A) )，v0为树根。为树根。u V的深度是从的深度是从v0 开始到达开始到达u的有向路的长度，的有向路的长度，T的高度是从的高度是从v0到到T的叶子的最长路的长度。的叶子的最长路的长度。根结点深度为根结点深度为0，称为第，称为第0层；层；深度同为深度同为i 的结点构成树的第的结点构成树的第i 层；层；具有最大深度的结点的深度称为树的深度具有最大深度的结点的深度称为树的深度（高度）。（高度）。9返回 结束AHGFEDCBL evel: 0L evel:

5、 1L evel: 2L evel: 310返回 结束定义定义 对有向树对有向树 T=(V, A)，若，若 u ,v V且且 A，则称，则称 u为为v的父亲，的父亲，v为为u的儿子。若从的儿子。若从u到到v存在有向道路，存在有向道路，则称则称u是是v的祖先，的祖先，v是是u的后代（子孙）的后代（子孙）有序树有序树 将各树的每个结点的所有儿子按次序排列，将各树的每个结点的所有儿子按次序排列，称这样的根树为有序树。称这样的根树为有序树。有序树的每个结点的出度小于或等于有序树的每个结点的出度小于或等于m时，称为时，称为m叉叉有序树。有序树。有序树的每个结点的出度只为有序树的每个结点的出度只为 0或或

6、 m 时，称为时，称为m叉叉正则有序树。正则有序树。11返回 结束v例 设有4个银币，已知其中3个一定是真的，真假的区别在于银币的重量，现用一天平设法找出假币。解：用a、b、c、d分别表示银币，a:b表示在天平上作比较。a:ba:cc重c轻a:dd重全真d轻a:ca轻b重a:cb轻a重12返回 结束容易看出，上例中方法并不唯一。a,b:c,da:cd:cc轻a重a:c全真d:cb重d轻a轻c重a:ba:bb轻d重13返回 结束二叉树二叉树 除树叶外，每个结点的最多有两个子结点，分别称为除树叶外，每个结点的最多有两个子结点，分别称为左子结点和右子结点的根树称为二叉树左子结点和右子结点的根树称为二

7、叉树二叉树的另外一个定义：二叉树或者是空树，或者有一个二叉树的另外一个定义：二叉树或者是空树，或者有一个根结点和两个分别称为左右子树的二叉树构成。根结点和两个分别称为左右子树的二叉树构成。二叉树的性质二叉树的性质第第i 层的结点数最多为层的结点数最多为2i；深度为深度为k的二叉树最多有的二叉树最多有2k+1- -1个结点；个结点；记二叉树出度为记二叉树出度为2的结点数目为的结点数目为n2，叶子数目为，叶子数目为n0，则有：，则有： n0=n2+11)多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中该结点的左儿子；以结点的右兄弟为对

8、应二叉树中该结点的右儿该结点的左儿子；以结点的右兄弟为对应二叉树中该结点的右儿子。子。14返回 结束满二叉树满二叉树 二叉树的每个结点的出度或者是二叉树的每个结点的出度或者是0或者是或者是2 。满二叉树也称正则二叉树。满二叉树也称正则二叉树完美二叉树完美二叉树 满二叉树且所有结点在同一层。满二叉树且所有结点在同一层。对完美二叉树对完美二叉树 的结点按从上到下，同层结点从左的结点按从上到下，同层结点从左到右的原则编号，得到结点从到右的原则编号，得到结点从12k+1- -1 的编号序列。的编号序列。得到上述结点编号的二叉树称为编号二叉树。得到上述结点编号的二叉树称为编号二叉树。完全二叉树完全二叉树

9、若设二叉树的高度为若设二叉树的高度为h，除第，除第 h 层层外，其它各层外，其它各层 (1h-1) 的结点数都达到最大的结点数都达到最大个数，第个数，第 h 层从右向左连续缺若干结点，这层从右向左连续缺若干结点，这就是完全二叉树。就是完全二叉树。 。15返回 结束高度为高度为k的完全二叉树，其的完全二叉树，其k- -1层以上结点构成一棵高度层以上结点构成一棵高度为为k- -1 的完美二叉树。的完美二叉树。完全二叉树的叶结点或者在同一层或者完全二叉树的叶结点或者在同一层或者 在相邻的两层。在相邻的两层。满二叉树完美二叉树完全二叉树16返回 结束定义定义设设T是有是有t片叶子的二叉树，其中片叶子的

10、二叉树，其中t片叶子分别带有片叶子分别带有非负实权非负实权 ，则称，则称T为为加权二叉树加权二叉树。称。称W(T) 为二叉树为二叉树T的权，其中的权，其中hi为带权为带权wi的的树叶树叶vi的层数。在所有的带权的层数。在所有的带权 的二叉的二叉树中，带权最小的二叉树称为树中，带权最小的二叉树称为最优二叉树最优二叉树(哈夫曼哈夫曼树树 )twww,21t1iiihtwww,2117返回 结束v【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：(a) W(T)=7*2+5*2+2*2+4*2=36(b) W(T)= =

11、7*3+5*3+2*1+4*2=46(c) W(T)= =7*1+5*2+2*3+4*3=35其中(c)树的W最小，它就是最优二叉树最优二叉树(哈夫曼哈夫曼树树 )。 18返回 结束vHuffmanHuffman树树Huffman 算法算法 给定给定t个非负实数，构造以它们为叶子带权且具有最小个非负实数，构造以它们为叶子带权且具有最小M(T) 的最优二叉树。的最优二叉树。i t；若若 i =1 结束；结束；将将 i 个非负实数权由小到大排列成序，以最小的两个个非负实数权由小到大排列成序，以最小的两个数作为左右儿子，构造其父亲结点，并以此左右儿子数作为左右儿子，构造其父亲结点，并以此左右儿子的权

12、值之和作为新构造的父亲结点的权值。在权序列的权值之和作为新构造的父亲结点的权值。在权序列中删去此左右儿子对应的权值，增加新构造的父亲结中删去此左右儿子对应的权值，增加新构造的父亲结点的权值。点的权值。 i i-1 ，转转 (2)。19返回 结束v例：有例：有4个权值个权值7,5,2,4，试构造一棵有，试构造一棵有4个个叶子结点的哈夫曼树。叶子结点的哈夫曼树。20返回 结束Huffman树树 由由Huffman算法构造的二叉树称算法构造的二叉树称为相对于非负实数权为相对于非负实数权 wi (i=1,2, t) 的的Huffman树。树。定理定理 Huffman树是一棵相对于非负实数权树是一棵相对

13、于非负实数权 wi (i=1,2, t) 的最优二叉树。的最优二叉树。21返回 结束定义定义： 有一个序列的集合，如果在这个集合中。任何序列都不是另一个序列的前缀，则称这个集合为前缀码前缀码。v例如，001是001011的前缀，集合000,001,01,10,11是前缀码，而1,00,01,000,0001不是前缀码。二元前缀码二元前缀码前缀码前缀码A= 1, 2, , m 中的中的 i 只由两种符号（如只由两种符号（如0、1）组成时，称）组成时，称A为一为一个二元个二元前缀码。前缀码。22返回 结束v对有序二叉树的顶点编码如下：(1)根不标码；(2)兄弟有序，左为兄，标0，右为弟，标1；(3

14、)从根始到叶上的道路依次抄出各点之码，写在叶下方，称该叶的前缀该叶的前缀；(4)全树的叶从左到有把它们的前缀依次抄出，叫做该树的前缀码该树的前缀码，每个叶子的前缀后加逗号，最后一个叶子前缀后加句号。显然有序二叉树与前缀码一一对应。23返回 结束v例如，0000，0001，001，010，011，100，101，11这一前缀码对应的有序二叉树如下图所示：v001101010010101000000010010100111001011124返回 结束Huffman编码编码 以各个源码符号在源码电文中以各个源码符号在源码电文中出现的频率为权值，构造以源码符号为叶子出现的频率为权值，构造以源码符号为叶

15、子的的Huffman树，得到关于源码符号集的一个树，得到关于源码符号集的一个二叉前缀码，称为其二叉前缀码，称为其Huffman编码。编码。定理定理 Huffman编码是关于该源码符号集的最编码是关于该源码符号集的最短二叉前缀码。短二叉前缀码。证明证明 略略25返回 结束实现译文长度最短的二叉前缀码设计过程：实现译文长度最短的二叉前缀码设计过程：q字频统计字频统计q等概率假设等概率假设qHuffman树构造树构造qHuffman编码方案确定编码方案确定例例 设一段电文含有设一段电文含有x1,x2,x3,x4,x5,x6,x7共共7个符号，个符号，它们出现的频率分别是：它们出现的频率分别是：x1:

16、 35% x2: 20% x3: 15% x4:10 x5: 10% x6:5% x7:5%。试为这。试为这7个符个符号设计一套最短二叉前缀编码方案。号设计一套最短二叉前缀编码方案。26返回 结束27返回 结束Huffman树的用途很广：如果出现概率越大的分枝（条件语句）离根越近，那么所需执行的判断语句就越少，这样便可提高程序的执行效率；：根据文件中字符出现的频率，建成一棵Huffman树，出现次数越多的字符的Huffman编码越短，这样可以达到文件的压缩。28返回 结束生成树生成树如果一棵树T是图G的子图，则树T称为图G的生成树生成树或支撑树支撑树；GE(T)称为树T的余树余树，记作：T；T

17、中的边称为图G的弦弦，也是树T的弦。1234567812345678余树余树弦弦29返回 结束定理定理 任何连通图至少有一棵生成树。任何连通图至少有一棵生成树。 证明略证明略定理定理 若连通图G=(V,E)，n=|V|，则图的生成生成树树有n1条边。用归纳法易证明。30返回 结束 图的平面性问题，除了它的理论意义外，有许多实际应用。例如，单面印刷电路板和集成电路的布线问题。近年来，大规模集成电路的发展促进了图的平面性的研究。 31返回 结束 可平面性可平面性 一个图一个图 G=(V,E) ，若能将其画在平面上，若能将其画在平面上，且任意两条边的交点只能是且任意两条边的交点只能是G的顶点，则称的

18、顶点，则称G可嵌入可嵌入平面，或称平面，或称G是可平面的。可平面图在平面上的一个是可平面的。可平面图在平面上的一个嵌入称为一个平面图。嵌入称为一个平面图。树是一类重要的平面图。树是一类重要的平面图。应用举例：印刷电路版、集成电路设计。应用举例：印刷电路版、集成电路设计。(a)(b)(c)(a)是可平面图，(b),(c) 是(a)的平面嵌入，是平面图。32返回 结束 例例 K5 和和K3,3 是不可平面的。是不可平面的。K5K3,3K5K3,333返回 结束 区域区域 由平面图的边包围而成，其中不含图的由平面图的边包围而成，其中不含图的顶点。也称为顶点。也称为面面。包围域。包围域R的所有边组成的

19、的所有边组成的回路称为该域的边界，回路长度称为该域的回路称为该域的边界，回路长度称为该域的度，记为度，记为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, deg(R3)=1R334返回 结束 内部面和外部面内部面和外部面 由平面图的边包围且无穷大的域称为由平面图的边包围且无穷大的域称为外部面。（如上例的域外部面。（如上例的域R0为外部面）为

20、外部面）一个平面图有且只有一个外部面。一个平面图有且只有一个外部面。 曲面嵌入曲面嵌入 一个图可嵌入平面当且仅当它可嵌入曲一个图可嵌入平面当且仅当它可嵌入曲面。面。定理定理5-1-1 平面图平面图G的所有域的度之和等于其边的所有域的度之和等于其边数数m的的2倍，即：倍，即：1deg()2riiRm35返回 结束v显然：可平面图的子图仍然是可平面图；包含不可平面图的图是不可平面图；v容易发现，平面图G每增加1条边，图G总的边数和面数都增加1。边界面36返回 结束 定理定理 欧拉公式欧拉公式 （必要条件必要条件） 设平面连通图设平面连通图G有有n个顶点，个顶点，m条边，条边，d个域，则有个域，则有

21、 n- -m+d = 2。证明证明 对对m作归纳。作归纳。m=0, m=1时成立。假定对于时成立。假定对于m=k成立成立: nk-mk+dk = 2 。当。当m=k+1时，考虑删除一条边后仍然连通的时，考虑删除一条边后仍然连通的情况。情况。(1) 如果如果G有回路，则删除回路上一条边后的图边数减少一，面有回路，则删除回路上一条边后的图边数减少一，面数减少一，故公式对数减少一，故公式对G成立：成立：nk-(mk+1)+(dk+1) = 2. (2) G没有回路，只有割边，必有度数为一的结点，删除相应割没有回路，只有割边，必有度数为一的结点，删除相应割边的一度顶点后，结点数和边数分别减少一，面数不

22、变，边的一度顶点后，结点数和边数分别减少一，面数不变，故仍然有故仍然有 ( nk +1)-(mk+1)+dk = 2. 欧拉公式对非简单图仍然成立。欧拉公式对非简单图仍然成立。37返回 结束对于对于n个顶点，个顶点，m条棱，条棱，d个面的凸多面体，个面的凸多面体，n-m+d=2. 推论推论 设平面图设平面图G的连通分支数为的连通分支数为k，并有，并有n个个顶点，顶点，m条边，条边，d个域，则有个域，则有 n- -m+d = k+1。证明证明 对每个连通分支使用欧拉公式，注意它对每个连通分支使用欧拉公式，注意它们共同拥有一个无穷面。们共同拥有一个无穷面。定理 若图G是简单的平面图，则图G至少有一

23、个顶点的度小于小于6。38返回 结束 极大平面图极大平面图 设设G=(V,E)为简单平面图，为简单平面图，|V| 3，若对任意若对任意vi ,vj V，且，且 (vi ,vj) E，有，有G =(V, E (vi ,vj)为非平面图，则称为非平面图，则称G为一个极大为一个极大平面图。平面图。“极大性极大性”乃针对固定顶点数的图的边的数乃针对固定顶点数的图的边的数目而言。目而言。39返回 结束v极大平面图的性质极大平面图的性质极大平面图是连通图。极大平面图是连通图。极大平面图的每个面都由极大平面图的每个面都由3条边组成。条边组成。极大平面图有极大平面图有3d=2m（d为面数目，为面数目，m 为边数目）。为边数目）。 定理定理 设极大平面图设极大平面图G有有n个顶点，个顶点，m条边，条边，d个域，个域，则有则有m=3n- -6，d=2n- -4。证明证明 将将3d=2m代入欧拉公式。代入欧拉公式。 推论推论 简单平面图简单平面图G有有 m 3n- -6，d 2n- -4。 定理定理 简单平面图至少有一个顶点的度小于简单平面图至少有一个顶点的度小于6。 证明证明 设任一点的度设任一点的度 6，得，得 m 3n，矛盾。，矛盾。40返回 结束 例例 K3,3K5K3,3K5 是不可平面的。是不可平面的。证明证明 如果如果G是平面图，是平面图，则有则有