离散数学-专题7：树

1、1第七章第七章 树树主要内容主要内容l 无向树及其性质无向树及其性质l 生成树生成树l 根树及其应用根树及其应用 27.1 无向树及其性质无向树及其性质定义定义7.1 (1) 无向树无向树连通无回路的无向图连通无回路的无向图(2) 平凡树平凡树平凡图平凡图(3) 森林森林至少由两个连通分支（每个都是树）组成至少由两个连通分支（每个都是树）组成(4) 树叶树叶1度顶点度顶点(5) 分支点分支点度数度数 2的顶点的顶点 3无向树的等价定义无向树的等价定义定理定理7.1 设设G=是是n阶阶m条边的无向图，则下面各命题条边的无向图，则下面各命题是等价的：是等价的：(1) G 是树是树(2) G 中任意

2、两个顶点之间存在惟一的路径中任意两个顶点之间存在惟一的路径.(3) G 中无回路且中无回路且 m=n 1. (4) G 是连通的且是连通的且 m=n 1.(5) G 是连通的且是连通的且 G 中任何边均为桥中任何边均为桥.(6) G 中没有回路，但在任何两个不同的顶点之间加一条新中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈边，在所得图中得到惟一的一个含新边的圈. 42022-6-9定理定理7.1证明证明(1)(2)证明证明: (1)(2)(3)(4)(5)(6)(1)(1) G是树是树(连通无回连通无回)(2) G中任何中任何2顶点之间有唯一路径顶点之间

3、有唯一路径(1)(2): u,v V, G连通连通, u,v之间的短程线是路径之间的短程线是路径. 如果如果u,v之间的路径不唯一之间的路径不唯一, 则则G中有回路中有回路, 矛盾矛盾!52022-6-9定理定理7.1证明证明(2)(3) (2) G中任何中任何2顶点之间有唯一路径顶点之间有唯一路径 (3) G无圈无圈 m=n-1证明证明(续续): (2)(3): 任任2点之间有唯一路径点之间有唯一路径无圈无圈(反反证证: 有圈有圈存在存在2点点,它们之间有它们之间有2条路径条路径.) m=n-1(归纳法归纳法): n=1时时,m=0. 设设n k时成立时成立, 当当n=k+1时时, 任选任选

4、1边边e, G-e有有2个连通分支个连通分支, m=m1+m2+1=(n1-1)+(n2-1)+1=n1+n2-1 =n-1. m1=n1-1m2=n2-1e62022-6-9定理定理7.1证明证明(3)(4) (3) G无圈无圈 m=n-1 (4) G连通连通 m=n-1证明证明(续续): (3)(4): G连通连通: 假设假设G有有s个连通分支个连通分支, 则每个连则每个连通分支都是树通分支都是树, 所以所以m=m1+m2+ ms=(n1-1)+(n2-1)+(ns-1) =n1+n2+ns-s=n-s=n-1, 所以所以s=1.m1=n1-1m2=n2-1ms=ns-172022-6-9

5、定理定理7.1证明证明(4)(5) (4) G连通连通 m=n-1 (5) G极小连通极小连通: 连通连通 所有边是桥所有边是桥证明证明(续续): (4)(5): 所有边是桥所有边是桥: e E, G-e是是n阶阶(n-2)边图边图, 一定不连通一定不连通(连通连通m n-1), 所以所以e是割边是割边. m=n-1em=n-282022-6-9定理定理7.1证明证明(5)(6) (5) G极小连通极小连通: 连通连通 所有边是桥所有边是桥 (6) G极大无回极大无回: 无圈无圈 增加任何新边得唯一圈增加任何新边得唯一圈证明证明(续续): (5)(6): 所有边是桥所有边是桥无圈无圈. u,v

6、 V, G连通连通, u,v之间有唯一路径之间有唯一路径 , 则则(u,v)是唯一的圈是唯一的圈. 92022-6-9定理定理7.1证明证明(6)(1)(6) G极大无回极大无回: 无圈无圈 增加任何新边得唯一圈增加任何新边得唯一圈(1) G是树是树(连通无回连通无回)证明证明(续续): (6)(1): G连通连通: u,v V, G (u,v)有唯一的圈有唯一的圈C, C-(u,v)是是u,v之间的路径之间的路径. # 10)(2)()1(2xnxvdni 由上式解出由上式解出x 2. 定理定理7.2 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T 中至少有两片树叶中至少有两片树叶.

7、 无向树的性质无向树的性质证证 设设 T 有有 x 片树叶，由握手定理可知，片树叶，由握手定理可知，11例题例题例例1 已知无向树已知无向树T中有中有1个个3度顶点，度顶点，2个个2度顶点，其余顶点度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树全是树叶，试求树叶数，并画出满足要求的非同构的无向树. 解解 解本题用树的性质解本题用树的性质m=n 1，握手定理，握手定理. 设有设有x片树叶，于是片树叶，于是 n = 1+2+x = 3+x, 2m = 2(n 1) = 2 (2+x) = 1 3+2 2+x解出解出x = 3，故，故T有有3片树叶片树叶.T 的度数列应为的度数

8、列应为 1, 1, 1, 2, 2, 3，易知易知3度顶点与度顶点与1个个2度顶点相邻度顶点相邻与和与和2个个2度顶点均相邻是非同度顶点均相邻是非同构的，因而有构的，因而有2棵非同构的无向棵非同构的无向树树T1, T2，如图所示，如图所示. 12例例2 已知无向树已知无向树T有有5片树叶，片树叶，2度与度与3度顶点各度顶点各1个，其余顶个，其余顶点的度数均为点的度数均为4，求，求T的阶数的阶数n，并画出满足要求的所有非同，并画出满足要求的所有非同构的无向树构的无向树. 例题例题解解 设设T的阶数为的阶数为n, 则边数为则边数为n 1，4度顶点的个数为度顶点的个数为n 7. 由握手定理得由握手定

9、理得 2m = 2(n 1) = 5 1+2 1+3 1+4(n 7)解出解出n = 8，4度顶点为度顶点为1个个. 13T的度数列为的度数列为1, 1, 1, 1, 1, 2, 3, 4，共有，共有3棵非同构的无向树，棵非同构的无向树，如图所示如图所示.例题例题142022-6-9tn表表n tnntnntnntn119471748,62925104,636,890211010618123,86726279,793,450311123519317,95527751,065,460421255120823,065282,023,443,03253131,301212,144,505295,46

10、9,566,58566143,159225,623,7563014,830,871,802711157,7412314,828,0743140,330,829,0308231619,3202439,299,89732109,972,410,221152022-6-9无向树的枚举无向树的枚举(enumeration)画出所有非同构的画出所有非同构的n阶无向树阶无向树n=1: n=2: n=3: n=4:n=5: 162022-6-96阶非同构无向树阶非同构无向树n=6: t6=6 172022-6-97阶非同构无向树阶非同构无向树n=7: t7=11182022-6-98阶非同构无向树阶非同构无

11、向树n=8: t8=23192022-6-98阶非同构无向树阶非同构无向树(续续)n=8: t8=23202022-6-98阶非同构无向树阶非同构无向树(解法解法2)n=8: 度数列有度数列有11种种:(1)1 1 1 1 1 1 1 1 7 (7)1 1 1 1 1 1 3 3 3(2)1 1 1 1 1 1 1 2 6 (8)5 1 1 1 1 2 2 3 3(3)1 1 1 1 1 1 1 3 5 (9)3 1 1 1 1 2 2 2 4(4)1 1 1 1 1 1 1 4 4 (10)4 1 1 1 2 2 2 2 3(5)2 1 1 1 1 1 2 2 5 (11)1 1 1 2 2

12、 2 2 2 2(6)3 1 1 1 1 1 2 3 4212022-6-98阶非同构无向树阶非同构无向树(解法解法2)n=8: 度数列有度数列有11种种:(8)5 1 1 1 1 2 2 3 3 (10)4 1 1 1 2 2 2 2 322不一定连通，也不一定不含回路T定义定义7.2 设设G为无向图为无向图(1) G的的树树T 是是G 的子图并且是树的子图并且是树(2) G的的生成树生成树T 是是G 的生成子图并且是树的生成子图并且是树(3) 生成树生成树T的的树枝树枝T 中的边中的边(4) 生成树生成树T的的弦弦不在不在T 中的边中的边(5) 生成树生成树T的的余树余树 全体弦组成的集合

13、的导出子图全体弦组成的集合的导出子图T7.2 生成树生成树232022-6-9定理定理7.3无向图无向图G连通连通 G有生成树有生成树证明证明: () 显然显然. () 破圈法破圈法. #24基本回路系统基本回路系统定理定理7.4 设设T为为G的生成树，的生成树，e为为T的任意一条弦，则的任意一条弦，则T e中中含一个只有一条弦其余边均为含一个只有一条弦其余边均为T的树枝的圈的树枝的圈. 不同的弦对应的不同的弦对应的圈也不同圈也不同. 证证 设设e=(u,v)，在，在T中中u到到v有惟一路径有惟一路径 ，则，则 e为所求的圈为所求的圈. 定义定义7.3 设设T是是n阶阶m条边的无向连通图条边的

14、无向连通图G的一棵生成树，设的一棵生成树，设e 1, e 2, , e m n+1为为T 的弦的弦. 设设Cr为为T 添加弦添加弦e r 产生的只含弦产生的只含弦e r、其余边均为树枝的圈、其余边均为树枝的圈. 称称Cr为为G的对应树的对应树T 的弦的弦e r的的基本基本回路回路或或基本圈基本圈，r=1, 2, , m n+1. 并称并称C1, C2, ,Cm n+1为为G对应对应T 的的基本回路系统基本回路系统，称，称m n+1为为G的的圈秩圈秩，记作，记作 (G). 25基本割集的存在基本割集的存在定理定理7.5 设设T是连通图是连通图G的一棵生成树，的一棵生成树，e为为T的树枝，则的树枝

15、，则G中存在只含树枝中存在只含树枝e，其余边都是弦的割集，且不同的树枝对，其余边都是弦的割集，且不同的树枝对应的割集也不同应的割集也不同.证证 由定理由定理7.1可知，可知，e是是T的桥，因而的桥，因而T e有两个连通分支有两个连通分支T1和和T2，令，令 Se=e | e E(G)且且 e 的两个端点分别属于的两个端点分别属于V(T1)和和V(T2)，由构造显然可知由构造显然可知Se为为G的割集，的割集，e Se且且Se中除中除e外都是弦，外都是弦，所以所以Se为所求为所求. 显然不同的树枝对应的割集不同显然不同的树枝对应的割集不同. 26定义定义7.4 设设T是是n阶连通图阶连通图G的一棵

16、生成树，的一棵生成树，e 1, e 2, , e n 1为为T 的树枝，的树枝，Si是是G的只含树枝的只含树枝e i的割集，则称的割集，则称Si为为G的对应的对应于生成树于生成树T由树枝由树枝e i生成的生成的基本割集基本割集，i=1, 2, , n 1. 并称并称S1,S2, , Sn 1为为G 对应对应T 的的基本割集系统基本割集系统，称，称n 1为为G的的割割集秩集秩，记作，记作 (G). 基本割集与基本割集系统基本割集与基本割集系统27解解 弦弦e, f, g对应的基本回路分别为对应的基本回路分别为 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基基=Ce,

17、 Cf, Cg. 树枝树枝a, b, c, d对应的基本割集分别为对应的基本割集分别为 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S基基=Sa, Sb, Sc, Sd. 例例3 下图实线边所示为生成树，求基本回路系统与下图实线边所示为生成树，求基本回路系统与基本割集系统基本割集系统实例实例282022-6-9带权图带权图(weighted graph)G=, W: ER, W(e)称为称为e的的权权ABFECD510938 1445629最小生成树最小生成树定义定义7.5 T是是G=的生成树的生成树(1) W(T)T各边权之和各边权之和

18、(2) 最小生成树最小生成树G的所有生成树中权最小的的所有生成树中权最小的求最小生成树的一个算法求最小生成树的一个算法避圈法避圈法（Kruskal）设）设G=，将，将G中非环边按权从小中非环边按权从小到大排序：到大排序：e1, e2, , em.(1) 取取e1在在T中中(2) 查查e2，若，若e2与与e1不构成回路，取不构成回路，取e2也在也在T 中，否则弃中，否则弃e2.(3) 再查再查e3, 直到得到生成树为止直到得到生成树为止. 30例例4 求图的一棵最小生成树求图的一棵最小生成树.所求最小生成树如所求最小生成树如图所示，图所示，W(T)=38.实例实例317.3 根根树及其应用树及其

19、应用定义定义7.6 T是有向树（基图为无向树）是有向树（基图为无向树）(1) T 为为根树根树T 中一个顶点入度为中一个顶点入度为0，其余的入度均为，其余的入度均为1.(2) 树根树根入度为入度为0的顶点的顶点(3) 树叶树叶入度为入度为1，出度为，出度为0的顶点的顶点(4) 内点内点入度为入度为1，出度不为，出度不为0的顶点的顶点(5) 分支点分支点树根与内点的总称树根与内点的总称(6) 顶点顶点v的的层数层数从树根到从树根到v的通路长度的通路长度(7) 树高树高T 中层数最大顶点的层数中层数最大顶点的层数32根根树实例树实例根树的画法根树的画法树根放上方，省去所有有向边上的箭头树根放上方，

20、省去所有有向边上的箭头33家族树与根子树家族树与根子树定义定义7.7 T 为非平凡根树为非平凡根树(1) 祖先与后代祖先与后代(2) 父亲与儿子父亲与儿子(3) 兄弟兄弟定义定义7.8 设设v为根树为根树T中任意一顶点，称中任意一顶点，称v及其后代的导出子及其后代的导出子图为以图为以v为根的为根的根子树根子树.345 根树的分类根树的分类(1) T 为为有序根树有序根树同层上顶点标定次序的根树同层上顶点标定次序的根树(2) 分类分类 r 叉树叉树每个分支点至多有每个分支点至多有r 个儿子个儿子 r 叉有序树叉有序树r 树是有序的树是有序的 r 叉正则树叉正则树每个分支点恰有每个分支点恰有r 个

21、儿子个儿子 r 叉正则有序树叉正则有序树 r 叉完全正则树叉完全正则树树叶层数相同的树叶层数相同的r叉正则树叉正则树 r 叉完全正则有序树叉完全正则有序树r叉正则树的结论叉正则树的结论定理定理 设有正则设有正则r叉树，其树叶数为叉树，其树叶数为t，分枝数为，分枝数为i，则，则(r-1)i=t-1证明证明 假设把假设把r叉树当作是每局有叉树当作是每局有r位选手参加比赛的单淘汰赛计位选手参加比赛的单淘汰赛计划表，树叶数为划表，树叶数为t表示参加比赛的选手数表示参加比赛的选手数,分枝点数为分枝点数为i表示表示比赛的局数比赛的局数 因为每局比赛将淘汰因为每局比赛将淘汰(r-1)位选手，比赛的结果共淘汰

22、位选手，比赛的结果共淘汰(r-1)i位选手，最后剩下一个冠军，因此位选手，最后剩下一个冠军，因此(m-1)i+1=t3536定义定义7.9 设设2叉树叉树T 有有t片树叶片树叶v1, v2, , vt，权分别为，权分别为w1, w2, , wt，称，称 为为T 的权，其中的权，其中l(vi)是是vi 的层数的层数. 在所在所有有有有t片树叶，带权片树叶，带权w1, w2, , wt 的的2叉树中，权最小的叉树中，权最小的2叉树叉树称为称为最优最优2叉树叉树. )()(1itiivlwtW最优二叉树最优二叉树求最优树的算法求最优树的算法 Huffman算法算法给定实数给定实数w1, w2, ,

23、wt，且，且w1 w2 wt. (1) 连接权为连接权为w1, w2的两片树叶，得一个分支点，其权为的两片树叶，得一个分支点，其权为w1+w2.(2) 在在w1+w2, w3, , wt 中选出两个最小的权，连接它们对应的中选出两个最小的权，连接它们对应的顶点顶点(不一定是树叶不一定是树叶)，得新分支点及所带的权，得新分支点及所带的权. (3) 重复重复(2)，直到形成，直到形成 t 1个分支点，个分支点，t片树叶为止片树叶为止. 37例例 5 求带权为求带权为1, 1, 2, 3, 4, 5的最优树的最优树. 解题过程由图给出，解题过程由图给出，W(T)=3838最佳前缀码最佳前缀码定义定义

24、7.10 设设 1, 2, , n-1, n是长度为是长度为 n 的符号串的符号串(1) 前缀前缀 1, 1 2, , 1 2 n 1 (2) 前缀码前缀码 1, 2, , m中任何两个元素互不为前缀中任何两个元素互不为前缀(3) 二元前缀码二元前缀码 i (i=1, 2, , m) 中只出现两个符号，如中只出现两个符号，如0与与1. 1，00，011，0101，01001，01000为前缀码。而为前缀码。而1，00，011，0101，0100，01001，01000不是前缀码，不是前缀码，因为因为0100既是既是01001又是又是01000的前缀。的前缀。如何产生二元前缀码？如何产生二元前缀

25、码？定理定理7.6 一棵一棵2叉树产生一个二元前缀码叉树产生一个二元前缀码.推论推论 一棵正则一棵正则2叉树产生惟一的前缀码（按左子树标叉树产生惟一的前缀码（按左子树标0，右子树标右子树标1）39图所示二叉树产生的前缀码为图所示二叉树产生的前缀码为 00, 10, 11, 011, 0100, 0101 40用用Huffman算法产生最佳前缀码算法产生最佳前缀码例例6 在通信中，八进制数字出现的频率如下：在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5%求传输它们的最佳前缀码，并求传输求传输它们的最佳前缀码，并求传输

26、10n（n 2）个按上述比）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的例出现的八进制数字需要多少个二进制数字？若用等长的（长为（长为3）的码字传输需要多少个二进制数字？）的码字传输需要多少个二进制数字？41解解 用用100个八进制数字中各数字出现的个数，即以个八进制数字中各数字出现的个数，即以100乘各频乘各频率为权，并将各权由小到大排列，得率为权，并将各权由小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 用此权产生的最优树如图所示用此权产生的最优树如图所示. 求最佳前缀码求最佳前缀码 01-0 11-

27、1 001-2 100-3 101-4 0001-500000-6 00001-7W(T)=285，传传10n(n 2)个个用二进制数字需用二进制数字需2.85 10n个个， 用等长码需用等长码需3 10n个数字个数字. 42波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法行遍或行遍或周游根树周游根树T对对T的每个顶点访问且仅访问一次的每个顶点访问且仅访问一次. 对对2叉有序正则树的周游方式：叉有序正则树的周游方式： 中序行遍法中序行遍法次序为：左子树、根、右子树次序为：左子树、根、右子树 前序行遍法前序行遍法次序为：根、左子树、右子树次序为：根、左子树、右子树 后序行遍法后序行遍法次序为：左子树、右子树、根次序为：左子树、右子树、根对图所示根树按中序、前序、对图所示根树按中序、前序、后序行遍法访问结果分别为：后序行遍法访问结果分别为： b a (f d g) c e， a b (c (d f g) e)， b (f g d) e c) a43用用2叉有序正则树存放算式叉有序正则树存放算式存放规则存放规则l 最高层次运算放在树根最高层