91无向树及生成树ppt课件

1、第第9章章 树树 n9.1 无向树及生成树无向树及生成树n9.2 根树及其运用根树及其运用 9.1 无向树及生成树无向树及生成树 无向树、森林无向树、森林树枝、弦、余树树枝、弦、余树生成树生成树根本回路与根本回路系统根本回路与根本回路系统根本割集与根本割集系统根本割集与根本割集系统最小生成树最小生成树 无向树无向树无向树无向树(树树): 连通而无回路的无向图，用连通而无回路的无向图，用T表示表示.平凡树平凡树: 平凡图平凡图森林森林: 每个连通分支都是树的非连通的无向图每个连通分支都是树的非连通的无向图树叶树叶: 树中度数为树中度数为1的顶点的顶点分支点分支点: 树中度数树中度数2的顶点的顶点

2、右图为一棵右图为一棵12阶树阶树.声明声明:本章中所讨论的回路均本章中所讨论的回路均 指简单回路或初级回路指简单回路或初级回路 无向树的性质无向树的性质定理定理9.1 设设G=是是n阶阶m条边的无向图，那么下条边的无向图，那么下面各命题是等价的：面各命题是等价的：1G是树是树(连通无回路连通无回路);2G中恣意两个顶点之间存在独一的途径中恣意两个顶点之间存在独一的途径;3G中无回路且中无回路且m=n1;4G是连通的且是连通的且m=n1;5G是连通的且是连通的且G中任何边均为桥中任何边均为桥;6G中没有回路中没有回路, 但在任何两个不同的顶点之间但在任何两个不同的顶点之间加一条新边后所得图中有独

3、一的一个含新边的圈加一条新边后所得图中有独一的一个含新边的圈. 无向树的性质无向树的性质( (续续) ) )(2)()1(2xnxvdni 定理定理9.2 设设T 是是 n 阶非平凡的无向树，那么阶非平凡的无向树，那么T中至中至少少有两片树叶有两片树叶. 证证 设设T有有x片树叶，由握手定理及定理片树叶，由握手定理及定理9.1可知，可知， 由上式解出由上式解出x2.例题例题例例1 知无向树知无向树T中中, 有有1个个3度顶点度顶点, 2个个2度顶点度顶点, 其他顶点全是其他顶点全是树叶树叶. 试求树叶数试求树叶数, 并画出满足要求的非同构的无向树并画出满足要求的非同构的无向树. 解解 用树的性

4、质用树的性质m=n1和握手定理和握手定理. 设有设有x片树叶，于是片树叶，于是 n=1+2+x=3+x, 2m=2(n1)=2(2+x)=13+22+x解出解出x=3，故，故T有有3片树叶片树叶. T的度数列为的度数列为1, 1, 1, 2, 2, 3 有有2棵非同构的无向树棵非同构的无向树, 如下图如下图例题例题例例2 知无向树知无向树T有有5片树叶片树叶, 2度与度与3度顶点各度顶点各1个个, 其他顶点的其他顶点的度数均为度数均为4. 求求T的阶数的阶数n, 并画出满足要求的一切非同构的并画出满足要求的一切非同构的无向树无向树. 解解 设设T的阶数为的阶数为n, 那么边数为那么边数为n1,

5、 4度顶点的个数为度顶点的个数为n7. 由握手定理得由握手定理得 2m=2(n1)=51+21+31+4(n7)解出解出n=8, 4度顶点为度顶点为1个个. T的度数列为的度数列为1,1,1,1,1,2,3,4 有有3棵非同构的无向树棵非同构的无向树 生成树生成树 TT设设G为无向连通图为无向连通图G的生成树的生成树: G的生成子图并且是树的生成子图并且是树生成树生成树T的树枝的树枝: G在在T中的边中的边生成树生成树T的弦的弦: G不在不在T中的边中的边生成树生成树T的余树的余树 : 一切弦的集合的导出子图一切弦的集合的导出子图留意：留意： 不一定连通不一定连通, 也不一定不含回路也不一定不

6、含回路. 右图黑边构成生成树右图黑边构成生成树红边构成余树红边构成余树生成树的存在性生成树的存在性 定理定理 任何无向连通图都有生成树任何无向连通图都有生成树.证证 用破圈法用破圈法. 假设图中无圈假设图中无圈, 那么图本身就是本人的生成树那么图本身就是本人的生成树. 否那么删去圈上的任一条边否那么删去圈上的任一条边, 这不破坏连通性这不破坏连通性, 反复进展反复进展 直到无圈为止直到无圈为止,剩下的图是一棵生成树剩下的图是一棵生成树.推论推论1 设设n阶无向连通图有阶无向连通图有m条边条边, 那么那么mn1. 推论推论2 设设n阶无向连通图有阶无向连通图有m条边条边, 那么它的生成树的余树那

7、么它的生成树的余树 有有mn+1条边条边. 推论推论3 设设 为为G的生成树的生成树 T 的余树，的余树，C 为为G 中恣意一中恣意一个圈，那么个圈，那么C与与 一定有公共边一定有公共边. TT根本回路与根本回路系统根本回路与根本回路系统 定义定义 设设T是是n阶阶m条边的无向连通图条边的无向连通图G的一棵生成的一棵生成树，设树，设e1, e2, , emn+1为为T的弦的弦. 设设Cr为为T添加弦添加弦er产生的产生的G中独一的圈中独一的圈(由由er和树枝组成和树枝组成), 称称Cr为对为对应应弦弦er的根本回路或根本圈的根本回路或根本圈, r=1, 2, , mn+1. 称称C1, C2,

8、 , Cmn+1为对应为对应T的根本回路系统的根本回路系统. 求根本回路的算法求根本回路的算法: 设弦设弦e=(u,v), 先求先求T中中u到到v的途的途径径 uv, 再并上弦再并上弦e, 即得对应即得对应e的根本回路的根本回路. 根本割集与根本割集系统根本割集与根本割集系统 定义定义 设设T是是n阶连通图阶连通图G的一棵生成树的一棵生成树, e1, e2, , en1为为T的树枝，的树枝，Si是是G的只含树枝的只含树枝ei, 其他边其他边都是弦都是弦的割集的割集, 称称Si为对应生成树为对应生成树T由树枝由树枝ei生成的根本生成的根本割割集集, i=1, 2, , n1. 称称S1, S2,

9、 , Sn1为对应为对应T的的根本根本割集系统割集系统.求根本割集的算法求根本割集的算法: 设设e为生成树为生成树T的树枝的树枝, Te由两由两棵子树棵子树T1与与T2组成组成, 令令 Se=e | eE(G)且且e的两个端点分别属于的两个端点分别属于T1与与T2 那么那么Se为为e对应的根本割集对应的根本割集. 实例实例例例 图中红边为一棵生成树图中红边为一棵生成树, , 求对应它的根本回路系统求对应它的根本回路系统 与根本割集系统与根本割集系统解解 弦弦e,f,ge,f,g对应的根本回路分别为对应的根本回路分别为 Ce=e b c, Cf=f a b c, Cg=g a b c d,Ce=

10、e b c, Cf=f a b c, Cg=g a b c d, C C基基=Ce, Cf, Cg. =Ce, Cf, Cg. 树枝树枝a,b,c,da,b,c,d对应的根本割集分别为对应的根本割集分别为 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g,f g, Sd=d, g, S S基基=Sa, Sb, Sc, Sd.=Sa, Sb, Sc, Sd.无向图与最小生成树无向图与最小生成树 对无向图或有向图的每一条边对无向图或有向图的每一条边e附加一个实数附加一个实数w(e

11、), 称作边称作边e的权的权. 图连同附加在边上的权称作带权图图连同附加在边上的权称作带权图, 记作记作G=. 设设G是是G的子图的子图, G一切边的权的和称作一切边的权的和称作G的权的权, 记作记作W(G). 最小生成树最小生成树: 带权图权最小的生成树带权图权最小的生成树求最小生成树的算法求最小生成树的算法避圈法避圈法 (Kruskal)设设G=, 将非环边按权从小到大排序：将非环边按权从小到大排序：e1, e2, , em.(1) 取取e1在在T中中(2) 检查检查e2, 假设假设e2与与e1不构成回路不构成回路, 那么将那么将e2参与参与T中中, 否那否那么弃去么弃去e2.(3) 检查

12、检查e3, 反复进展直至得到生成树为止反复进展直至得到生成树为止. 实例实例例例 求图的一棵最小生成树求图的一棵最小生成树 W(T)=389.2 根树及其运用根树及其运用有向树有向树根树、树根、树叶、内点、分支点根树、树根、树叶、内点、分支点家族树、根子树、有序树家族树、根子树、有序树r元树元树r元有序树元有序树r元正那么树元正那么树r元有序正那么树元有序正那么树r元完全正那么树元完全正那么树r元有序完全正那么树元有序完全正那么树最优最优2元树与元树与Huffman算法算法前缀吗与最正确前缀吗前缀吗与最正确前缀吗中序行遍法、前序行遍法、后续行遍法中序行遍法、前序行遍法、后续行遍法波兰符号法与逆

13、波兰符号法波兰符号法与逆波兰符号法 有向树与根树的定义有向树与根树的定义 有向树有向树: 基图为无向树的有向图基图为无向树的有向图根树根树: 有一个顶点入度为有一个顶点入度为0, 其他的入度均为其他的入度均为1的的 非平凡的有向树非平凡的有向树树根树根: 有向树中入度为有向树中入度为0的顶点的顶点树叶树叶: 有向树中入度为有向树中入度为1, 出度为出度为0的顶点的顶点内点内点: 有向树中入度为有向树中入度为1, 出度大于出度大于0的顶点的顶点分支点分支点: 树根与内点的总称树根与内点的总称顶点顶点v的层数的层数: 从树根到从树根到v的通路长度的通路长度树高树高: 有向树中顶点的最大层数有向树中

14、顶点的最大层数根树根树(续续)根树的画法根树的画法: :树根放上方树根放上方, ,省去一切有向边上的箭头省去一切有向边上的箭头如右图所示如右图所示 a a是树根是树根 b,e,f,h,ib,e,f,h,i是树叶是树叶 c,d,gc,d,g是内点是内点 a,c,d,ga,c,d,g是分支点是分支点 a a为为0 0层层;1;1层有层有b,c; 2b,c; 2层有层有d,e,f;d,e,f; 3 3层有层有g,h; 4g,h; 4层有层有i.i. 树高为树高为4 4家族树家族树定义定义 把根树看作一棵家族树把根树看作一棵家族树:(1) 假设顶点假设顶点 a 邻接到顶点邻接到顶点 b, 那么称那么称

15、 b 是是 a 的儿子的儿子, a 是是 b 的父亲的父亲;(2) 假设假设b和和c为同一个顶点的儿子为同一个顶点的儿子, 那么称那么称b和和c是兄是兄弟弟;(3) 假设假设ab且且a可达可达b, 那么称那么称a是是b的祖先的祖先, b是是a的的后代后代.设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根, 称称v及其一切后及其一切后代的导出子图为以代的导出子图为以v为根的根子树为根的根子树. 根树的分类根树的分类有序树有序树: 将根树同层上的顶点规定次序将根树同层上的顶点规定次序r元树元树:根树的每个分支点至多有根树的每个分支点至多有r个儿子个儿子r元正那么树元正那么树: 根树的每个

16、分支点恰有根树的每个分支点恰有r个儿子个儿子r元完全正那么树元完全正那么树: 树叶层数一样的树叶层数一样的r元正那么树元正那么树r元有序树元有序树: 有序的有序的r元树元树r元正那么有序树元正那么有序树: 有序的有序的r元正那么树元正那么树r元完全正那么有序树元完全正那么有序树: 有序的有序的r元完全正那么树元完全正那么树最优最优2 2元树元树 )()(1itiivlwtW 定义定义 设设2元树元树T有有t片树叶片树叶v1, v2, , vt, 树叶的权分树叶的权分别别 为为w1, w2, , wt, 称称 为为T的权的权, 记作记作 W(T), 其中其中l(vi)是是vi的层数的层数. 在一

17、切有在一切有t片树叶片树叶, 带权带权 w1, w2, , wt 的的 2元树中元树中, 权最小的权最小的2元树称为最元树称为最优优 2元树元树.求最优树求最优树 Huffman算法算法:给定实数给定实数w1, w2, , wt, 作作t片树叶片树叶, 分别以分别以w1, w2, , wt为权为权. 在一切入度为在一切入度为0的顶点的顶点(不一定是树叶不一定是树叶)中选出两个中选出两个权最小的顶点权最小的顶点, 添加一个新分支点添加一个新分支点, 以这以这2个顶点为个顶点为儿子儿子, 其权等于这其权等于这2个儿子的权之和个儿子的权之和. 反复反复, 直到只需直到只需1个入度为个入度为0 的顶点

18、为止的顶点为止. W(T)等于一切分支点的权之和等于一切分支点的权之和实例实例例例 求带权为求带权为1, 1, 2, 3, 4, 5的最优树的最优树解题过程由以下图给出，解题过程由以下图给出，W(T)=38 前缀码前缀码 设设 =12n-1n是长度为是长度为n的符号串的符号串的前缀的前缀: 12k , k=1,2,n-1 前缀码前缀码: 1, 2, , m, 其中其中1, 2, , m为为非空字符非空字符串串, 且任何两个互不为前缀且任何两个互不为前缀2元前缀码元前缀码: 只出现两个符号只出现两个符号(如如0与与1)的前缀码的前缀码如如 0,10,110, 1111, 10,01,001,11

19、0是是2元前缀码元前缀码 0,10,010, 1010 不是前缀码不是前缀码前缀码前缀码( (续续) )一棵一棵2元树产生一个二元前缀码元树产生一个二元前缀码:对每个分支点对每个分支点, 假设关联假设关联2条边条边, 那么给左边标那么给左边标0, 右边右边标标1; 假设只关联假设只关联1条边条边, 那么可以给它标那么可以给它标0(看作左边看作左边), 也也可以可以标标1(看作右边看作右边). 将从树根到每一片树叶的通路上标将从树根到每一片树叶的通路上标的数字组成的字符串的数字组成的字符串记在树叶处记在树叶处, 所得的字符所得的字符串构成一个前缀码串构成一个前缀码.如右图所示如右图所示最正确前缀

20、码最正确前缀码例例 在通讯中，设八进制数字出现的频率如下：在通讯中，设八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%采用采用2元前缀码元前缀码, 求传输数字最少的求传输数字最少的2元前缀码元前缀码 (称作最正确前称作最正确前缀码缀码), 并求传输并求传输10n(n2)个按上述比例出现的八进制数字需个按上述比例出现的八进制数字需要多少个二进制数字？假设用等长的要多少个二进制数字？假设用等长的 (长为长为3) 的码字传输需的码字传输需求求多少个二进制数字多少个二进制数字?解解 用用Huffman算法求以频率算法求以频率(乘以乘

21、以100)为权的最优为权的最优2元树元树. 这这里里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最优最优2元树如下图元树如下图. 编码编码: 0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001传传100个按比例出现的八进制数字所需二进制数字的个数个按比例出现的八进制数字所需二进制数字的个数为为 W(T)=285.传传10n(n2)个所用二进制数字的个数为个所用二进制数字的个数为2.8510n, 而用等而用等长长码码(长为长为3)需求用需求用 310n个数字个数字. 波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法 行遍行遍(周游周游)根树根树T : 对对T 的每个顶点访问且仅访问一次的每个顶点访问且仅访问一次. 行遍行遍2元有序正那么树的方式：元有序正那么树的方式： 中序行遍法中序行遍法: 左子树、根、右子树左子树、根、右子树 前序行遍法前序行遍法: 根、左子树、右子树根、左子树、右子树 后序行遍法后序行遍法: 左子树、