离散数学：7-1 树

1、复习思考题15n 重新画下图的平面嵌入，使其外部面的次数分别为1，3，4。n 上图是极大平面图。 ( )n 同构的两个图的对偶图一定同构。 ( )n 设无向图G与K3,3同胚，至少从G中删除_条边才能使所得图为平面图。 n设设G为为8阶阶极大平面图，则极大平面图，则G的面数的面数r =_R0R1R2R3第7章 树 7.1 无向树及生成树7.2 根树及其应用最小生成树问题n 树是一类既简单而又非常重要的图，它是计算机中一种基本的数据结构和表示方法。n 在输电网络分析、有机化学、最短连接及渠道设计等领域也都有广泛的应用，如：n某一地区有若干个主要城市，拟修建高速公路某一地区有若干个主要城市，拟修建

2、高速公路把这些城市连接起来，使得其中任何一个城市把这些城市连接起来，使得其中任何一个城市都可以经高速公路直接或间接到达另一个城市，都可以经高速公路直接或间接到达另一个城市，设已知任意两个城市之间修建高速的成本，设已知任意两个城市之间修建高速的成本，那那么应如何决定在哪些城市间修建高速公路，使么应如何决定在哪些城市间修建高速公路，使得总成本最小？得总成本最小？ 树的应用n 英国数学家凯莱英国数学家凯莱(Arthur Cayley)于于19世纪中叶研世纪中叶研究究饱和碳氢化合物饱和碳氢化合物CnH2n+2的同分异构体的同分异构体时提出树时提出树的概念的概念. n 当当n=1,2,3时时, 都只有一

3、棵非同构的树都只有一棵非同构的树; n 当当n=4时时, 有有2棵不同构的树棵不同构的树. 甲烷甲烷乙烷乙烷丙烷丙烷丁烷丁烷异丁烷异丁烷7.1 无向树及生成树n 无向树无向树: 连通无回路的无向图。连通无回路的无向图。n树叶树叶: : 树中度数为树中度数为1 1的顶点。的顶点。n分支点分支点: : 树中度数树中度数 2 2的顶点。的顶点。n 规定：规定：平凡图也是树，叫平凡图也是树，叫平凡树。平凡树。n 森林森林: 每个连通分支都是树的非连通的无向图。每个连通分支都是树的非连通的无向图。n 声明声明:本章中所讨论的回路均指简单回路或初级回路。本章中所讨论的回路均指简单回路或初级回路。 (a)

4、树(b)森林无向树的几个等价定义定理定理7.1 设G = 是 n 阶 m 条边的无向图，则下面各命题是等价的：（1）G是树是树(连通连通、无回路无回路);（2）G中每对顶点之间具有惟一的一条路径中每对顶点之间具有惟一的一条路径;（3）G中无回路且中无回路且 m=n 1;（4）G是连通的且是连通的且 m=n 1;（5）G是连通的且是连通的且G中任何边均为桥中任何边均为桥;（6）G中无回路中无回路, 但在任两个不相邻的顶点之间加但在任两个不相邻的顶点之间加一条新边后所得图中有惟一的一个含新边的回路一条新边后所得图中有惟一的一个含新边的回路.求6个顶点的非同构无向树n 顶点数n = 6，树的边数m

5、= n-1=5n 树的总度数为n 树中各顶点度数分配情况可为(1) 1, 1, 1, 1, 1, 5 (2) 1, 1, 1, 1, 2, 4(3) 1, 1, 1, 1, 3, 3 (4) 1, 1, 1, 2, 2, 3(5) 1, 1, 2, 2, 2, 25)(110522)(1iniivdmvd，无向树的性质 定理定理7.2 设设T 是是 n 阶非平凡的无向树，则阶非平凡的无向树，则T 中至少中至少有两片树叶有两片树叶. 证证： 由由定理定理7.1(树的定义树的定义)可知树可知树 T 共有共有n-1条边，条边， 由握手定理得：由握手定理得： 设设 T 有有 k 片树叶，则片树叶，则

6、T 中的分支点为中的分支点为 n-k 个，每个分个，每个分支点的度数支点的度数 2，所有分支点度数之和，所有分支点度数之和 2(nk)，从而下式成，从而下式成立：立： 由上式解出由上式解出 k 2.niinvd1) 1(2)(niikknvdn1( 212()()例题1已知无向树 T 中, 有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求树叶数, 并画出满足要求的非同构的无向树. 解：解：用用树的性质树的性质m=n 1和和握手定理握手定理. 设有设有k片树叶，于是片树叶，于是 n = 1+2+k = 3+k, 2m=2(n 1)=2 (3+k-1)=1 3+2 2+k 1 解出解出k

7、=3，故，故T有有3片树叶片树叶. T的度数列为的度数列为1, 1, 1, 2, 2, 3 有有2棵非同构的无向树：棵非同构的无向树：例题2已知无向树T 有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T 的阶数n, 并画出满足要求的所有非同构的无向树. 解解：设设4度顶点的个数为度顶点的个数为 k 个，则个，则n=5+1+1+k =7+k 树的树的边数边数m= (7+k)-1 =6+k 由握手定理得由握手定理得 2m=2(6+k)=5 1+2 1+3 1+4k 解出解出k=1, 则则 n = 7+k = 8. T的度数列为的度数列为1,1,1,1,1,2,3,4 有有3棵非同

8、构的无向树棵非同构的无向树 生成树 设G为无向连通图n G的生成树: G的生成子图并且是树。的生成子图并且是树。n 生成树T的树枝: G在在T中的边。中的边。n 生成树T的弦: G不在不在T中的边。中的边。n 生成树T的余树 : 所有弦的集合的导出子图。所有弦的集合的导出子图。n 注意： 不一定连通、不一定不含回路、不一定连通、不一定不含回路、不一定不一定是树。是树。TTT的余树的余树G生成树生成树T生成树的存在性 n定理定理 任何无向连通图都有生成树任何无向连通图都有生成树. .n证：用破圈法. 若若图中无圈图中无圈, 则图本身就是自己的生成树则图本身就是自己的生成树. 否则删去圈上的任一条

9、边否则删去圈上的任一条边, 这不破坏连通性这不破坏连通性, 重复进行直到无圈为止重复进行直到无圈为止,剩下的图是一棵生成树剩下的图是一棵生成树.n推论推论 设设n阶无向连通图有阶无向连通图有m条边条边, 则则m n 1. 基本回路与基本回路系统 n基本回路基本回路n设设T是连通图是连通图G的一棵生成树的一棵生成树, 对对每一条每一条弦弦e, 存在存在惟一惟一的由的由弦弦e和和T的树枝构成的树枝构成的初级回路的初级回路Ce, 称称Ce为对应于弦为对应于弦e的的基本回路基本回路.n基本回路系统基本回路系统所有基本回路的集合。n求基本回路的算法求基本回路的算法: n设设弦弦e=(u,v), n先求先

10、求T中中u到到v的路径的路径 uv, 再并上弦再并上弦e, n即得对应即得对应e的基本回路的基本回路. 基本回路与基本回路系统实例图中红边为一棵生成树,求对应它的基本回路系统。解：解： 弦弦e, f, g对应的基本回路分别为对应的基本回路分别为 加加e 得基本回路得基本回路Ce=e b c , 加加f 得基本回路得基本回路 Cf=f a b c , 加加g 得基本回路得基本回路Cg=g a b c d , 则：则：C基基=Ce , Cf , Cg . 回路合并n合并合并回路回路C1和和C2(C1 C2): C1 C2是是C1和和C2上的边的对称差构成的上的边的对称差构成的(一条一条或几条或几条

11、)回路回路.基本回路的性质n连通图中的任一条回路连通图中的任一条回路都可以表都可以表成成对应对应它它所含弦的基本回路的合并所含弦的基本回路的合并.例如例如, Ce = bce Cf = abcf Cg= abcdg Ce Cf = aef Ce Cg = aedg Cf Cg = fdg Ce Cf Cg = bcdgfe基本割集与基本割集系统 n基本割集基本割集n设设T是连通图是连通图G的一棵生成树的一棵生成树, 对对T的的每一条每一条树枝树枝a, 存在存在惟一惟一的由的由树枝树枝a, 其余的其余的边都是弦的割集边都是弦的割集Sa, 称称Sa为对应树枝为对应树枝a的的基本割集基本割集。n基本

12、割集系统是是所有基本割集的集合所有基本割集的集合。n基本割集的算法基本割集的算法 设设a为生成树为生成树T的树枝的树枝, T a由两棵子树由两棵子树T1与与T2组成组成, Sa=e | e E(G)且且e的两个端点分别属于的两个端点分别属于T1与与T2 .基本割集与基本割集系统实例例 图中红边为一棵生成树, 求对应它的基本割集系统解：解： 树枝树枝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.基本割集的性质n连通图中的任一连通图中的任一割集割集都可以表都可

13、以表成成对应对应它它所所含含树枝树枝的基本的基本割集割集的的对称差对称差.例如例如 ： Sa = a, f, g, Sb = b, e, f, g, Sc = c, e, f g, Sd = d, g, Sa Sb = a,b,e Sa Sc= a,e,c Sb Sd = b,e,f,d无向图与最小生成树 n 定义 n对无向图或有向图的每一条边对无向图或有向图的每一条边e附加一个实数附加一个实数w(e), 称作称作边边e的权的权. n图连同附加在边上的权称作图连同附加在边上的权称作带权图带权图, 记作记作G=. n设设T是是G的生成树的生成树, T所有边的权的和称作所有边的权的和称作T的权的权

14、, 记作记作W(T).n 最小生成树: 带权图中权最小的生成树。带权图中权最小的生成树。求最小生成树的算法避圈法 (Kruskal)设设G=, 将除环外的边按权将除环外的边按权从小到大排序从小到大排序：e1, , em.(1) 取取e1在在T中中(2) 检查检查e2,若若e2与与e1不构成回路不构成回路, 则将则将e2加入加入T中中, 否则弃去否则弃去e2.(3) 检查检查e3, 重复进行直至得到生成树为止重复进行直至得到生成树为止. v1v2v3v4v5v621145 22244v3v41v11v22v5v622实例例例 求图的一棵最小生成树求图的一棵最小生成树 W(T) =38最小生成树的

15、应用n最小生成树聚类算法n设有一设有一组数据组数据D=a1,a2,an,D中的任意两个数中的任意两个数据据ai,aj的相似程度可以用一个相似度函数的相似程度可以用一个相似度函数d(ai,aj)来度量，称为这两个数据的距离来度量，称为这两个数据的距离。n给定给定一个正整数一个正整数k(1kn)，D的一个的一个k聚类是聚类是D的一个的一个k划分划分 ，使得同一子类中的数据间的距，使得同一子类中的数据间的距离尽可能地离尽可能地“近近”，不同子类的数据间的距离尽，不同子类的数据间的距离尽可能地可能地“远远”。7.2 根树及其应用n有向树: 基图为无向树的有向图基图为无向树的有向图. .n根树: 有一个

16、顶点入度为有一个顶点入度为0, 其余的入度均其余的入度均为为1的非平凡的有向树的非平凡的有向树.n树根: 有向树中入度为有向树中入度为0的顶点的顶点.n树叶: 有向树中入度为有向树中入度为1, 出度为出度为0的顶点的顶点.n内点: 有向树中入度为有向树中入度为1, 出度大于出度大于0的顶点的顶点.n分支点: 树根与内点的总称树根与内点的总称. .根树n根树的画法:n树根放上方树根放上方, ,省去所有有向边上的箭头省去所有有向边上的箭头n如右图所示n a 是树根是树根n b, e, f, h, i 是树叶是树叶n c, d, g是内点是内点n a, c, d, g 是分支点是分支点 第第0层：层

17、：a 第第1层：层：b，c 第第2层：层：d，e, f 第第3层：层：g，h 第第4层：层：i 树高：树高：4根树n顶点顶点v的层数的层数n在根树中，从树根到任意顶点在根树中，从树根到任意顶点v只能有唯一的一只能有唯一的一条路，这条路的长度称为条路，这条路的长度称为v的的级级(层层)数数。n树高: 有向树中顶点的最大层数。有向树中顶点的最大层数。家族树n把根树看作一棵家族树:(1) 若顶点若顶点 a 邻接到顶点邻接到顶点 b, 则称则称 b 是是 a 的的儿子儿子, a 是是 b 的的父亲父亲;(2) 若若b和和c为同一个顶点的儿子为同一个顶点的儿子, 则称则称b和和c是是兄弟兄弟;(3) 若

18、若a d且且a可达可达d, 则称则称a是是d的的祖先祖先, d是是a的的后代后代.n根子树n设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根, 称称v及其所有后代的导出子图为以及其所有后代的导出子图为以v为根的为根的. 根树的分类n r 叉树叉树:根树的每个分支点根树的每个分支点至多至多有有r 个儿子个儿子n r 叉正则树叉正则树: 根树的每个分支点根树的每个分支点恰有恰有r 个儿子个儿子n r 叉完全正则树叉完全正则树: 树叶树叶层数相同层数相同的的r 叉正则树叉正则树二叉树二叉树二叉正二叉正则树则树二叉完全二叉完全正则树正则树根树的分类n 有序树有序树: 将根树同层上的顶点规定次

19、序将根树同层上的顶点规定次序. .n r 叉有序树叉有序树: 有序的有序的r叉树叉树.n r 叉叉正正则有序树则有序树: 有序的有序的r叉正则树叉正则树.n r 叉叉完全完全正则有序树正则有序树: 有序的有序的r叉完全正则树叉完全正则树.二叉有序二叉有序树树二叉正二叉正则有序树则有序树二叉完全二叉完全正则有序树正则有序树1 21 2 3 41 21 21 2 3 41 2 3 4 5 6 7 81 21 2 31 2最优 2 叉树 n 定义定义 n设设2叉树叉树T有有t片树叶片树叶v1, v2, , vt, 树叶的权分别为树叶的权分别为w1, w2, , wt, n称称 为为T 的权的权, 其

20、中其中l(vi)是是vi的层数的层数. n 在所有t片树叶, 带权w1, w2, , wt 的 2叉树中, 权最小的2叉树称为最优 2叉树.)()(itiivlwTW1赋权二叉树权值的计算nT1、T2和T3都是带权2,2,3,3,5的二叉树，n W(T1) =(22 3)2(35)3 = 38n W(T2) =(35)4332221 = 47n W(T3) =(33)3(522)2 = 36n注意：T1、T2和T3都不是最优二叉树! 求最优树的算法-Huffman算法n 给定t片树叶的权为w1,w2,wt且w1 w2 wt。n 连接权为w1，w2的两片树叶，得一分枝点，其权为w1w2 n 在w1w2，w3，