第十六章 树 主要内容 无向树及其性质 生成树 根树及其应用.

Presentation on theme: "第十六章 树 主要内容 无向树及其性质 生成树 根树及其应用."— Presentation transcript:

1 第十六章 树 主要内容 无向树及其性质 生成树 根树及其应用

2 16.1 无向树及其性质 定义16.1 (1) 无向树——连通无回路的无向图 (2) 平凡树——平凡图
(3) 森林——至少由两个连通分支（每个都是树）组成 (4) 树叶——1度顶点 (5) 分支点——度数2的顶点

3 无向树的等价定义 定理16.1 设G=<V,E>是n阶m条边的无向图，则下面各命题 是等价的： (1) G 是树
(3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1. (5) G 是连通的且 G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈.

4 证明思路 (1)(2). （关键一步是, 若路径不惟一必有回路. ）
由G的连通性可知， u,vV，u和v之间存在一条路径。若路径不唯一，设L和H都是u到v的路径，则必存在 由L和H上的边构成的回路，这与G中无回路矛盾。 (2)(3). 若G中有回路，则回路上任意两点之间的路径不 惟一. 对n用归纳法证明m=n1. n=1为平凡图，正确. 设n k时结论成立，证n=k+1时结 论亦成立：取G中边e，Ge有且仅有两个连通分支G1,G2 (为什么?) . ni 为顶点数，mi为边数， i=1,2. ni k， i=1,2.由归纳假设得 mi=ni1, i=1,2. 于是，m=m1+m2+1=n1+n22+1=n1.

5 证明思路 (3)(4). 只需证明G连通. 用反证法. 否则G有s（s2）个连通 分支都是小树. 于是有mi=ni1, ，
这与m=n1矛盾. (4)(5). 只需证明G 中每条边都是桥. 为此只需证明命题 “G 是 n 阶 m 条边的无向连通图，则 mn1”. 命题的证明: 对n归纳. eE, Ge只有n2条边，由命题可知Ge不连通，故e为桥. (5)(6). 由(5)易知G为树，由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈. (6)(1). 只需证明G连通，这是显然的.

6 无向树的性质 定理16.2 设T是n阶非平凡的无向树，则T 中至少有两片树叶. 证 设 T 有 x 片树叶，由握手定理及定理16.1可知，

7 例题 例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 的度数列应为 1, 1, 1, 2, 2, 3， 易知3度顶点与1个2度顶点相邻与和2个2度顶点均相邻是非同构的，因而有2棵非同构的无向树T1, T2，如图所示.

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

9 例题 T的度数列为1, 1, 1, 1, 1, 2, 3, 4，共有3棵非同构的无向树，如图所示.

10 16.2 生成树 定义16.2 设G为无向图 (1) G的树——T 是G 的子图并且是树 (2) G的生成树——T 是G 的生成子图并且是树
(3) 生成树T的树枝——T 中的边 (4) 生成树T的弦——不在T 中的边 (5) 生成树T的余树 ——全体弦组成的集合的导出子图 不一定连通，也不一定不含回路，如图所示

11 生成树的存在性 定理 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树.
定理 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 这不破坏连通性, 重复进行 直到无圈为止,剩下的图是一棵生成树. 推论1 设n阶无向连通图有m条边, 则mn1. 推论2 设n阶无向连通图有m条边, 则它的生成树的余树 有mn+1条边. 推论3 设 为G的生成树 T 的余树，C 为G 中任意一个圈，则C与 一定有公共边. 证 否则，C中的边全在T中，这与T为树矛盾.

12 基本回路系统 定理16.4 设T为G的生成树，e为T的任意一条弦，则Te中 含一个只有一条弦e其余边均为T的树枝的圈. 不同的弦对应
的圈也不同. 定义16.3 设T是n阶m条边的无向连通图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). 求基本回路的算法：设弦e=(u,v)，先求T中u到v的路径uv，再并上弦e，即得对应e的基本回路.

13 基本割集的存在 定理16.5 设T是连通图G的一棵生成树，e为T的树枝，则G 中存在只含树枝e，其余边都是弦的割集，且不同的树枝对
应的割集也不同. 证 由定理16.1可知，e是T的桥，因而Te有两个连通分支T1 和T2，令 Se={e | eE(G)且 e 的两个端点分别属于V(T1)和V(T2)}， 由构造显然可知Se为G的割集，eSe且Se中除e外都是弦， 所以Se为所求. 显然不同的树枝对应的割集不同.

14 基本割集与基本割集系统 定义16.4 设T是n阶连通图G的一棵生成树，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). 求基本割集的算法 设e为生成树T 的树枝，Te为两棵小树T1与T2，令 Se ={e | eE(G)且e的两个端点分别属于T1与T2} 则Se为e 对应的基本割集.

15 实例 例3 图5实线边所示为生成树，求基本回路系统与基本割集系统 解 弦e, f, g对应的基本回路分别为
例3 图5实线边所示为生成树，求基本回路系统与基本割集系统 解 弦e, f, g对应的基本回路分别为 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基={Ce, 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}.

16 最小生成树 定义16.5 T是G=<V,E,W>的生成树 (1) W(T)——T各边权之和
求最小生成树的一个算法 避圈法（Kruskal）设G=<V,E,W>，将G中非环边按权从小 到大排序：e1, e2, …, em. (1) 取e1在T中 (2) 查e2，若e2与e1不构成回路，取e2也在T 中，否则弃e2. (3) 再查e3,…, 直到得到生成树为止.

17 实例 例4 求图的一棵最小生成树. 所求最小生成树如 图所示，W(T)=38.

18 实例 如下图所示的赋权图表示某七个城市 预先算出它们之间的一些直接通信线路造价，试给出一个
设计方案，使得各城市之间能够通信而且总造价最小（画 出图即可）。

19 16.3 根树及其应用 定义16.6 T是有向树（基图为无向树） (1) T 为根树——T 中一个顶点入度为0，其余的入度均为1.
16.3 根树及其应用 定义16.6 T是有向树（基图为无向树） (1) T 为根树——T 中一个顶点入度为0，其余的入度均为1. (2) 树根——入度为0的顶点 (3) 树叶——入度为1，出度为0的顶点 (4) 内点——入度为1，出度不为0的顶点 (5) 分支点——树根与内点的总称 (6) 顶点v的层数——从树根到v的通路长度 (7) 树高——T 中层数最大顶点的层数 (8) 平凡根树——平凡图

20 根树(续) 根树的画法:树根放上方,省去所有有向边上的箭头 如右图所示 a是树根 b,e,f,h,i是树叶 c,d,g是内点
a,c,d,g是分支点 a为0层;1层有b,c; 2层有d,e,f; 3层有g,h; 4层有i. 树高为4

21 根树实例 根树的画法——树根放上方，省去所有有向边上的箭头

22 家族树 定义 把根树看作一棵家族树: (1) 若顶点 a 邻接到顶点 b, 则称 b 是 a 的儿子, a 是 b 的父亲;
定义 把根树看作一棵家族树: (1) 若顶点 a 邻接到顶点 b, 则称 b 是 a 的儿子, a 是 b 的父亲; (2) 若b和c为同一个顶点的儿子, 则称b和c是兄弟; (3) 若ab且a可达b, 则称a是b的祖先, b是a的后代. 设v为根树的一个顶点且不是树根, 称v及其所有后 代的导出子图为以v为根的根子树.

23 根树的分类 (1) T 为有序根树——同层上顶点标定次序的根树 (2) 分类 ① r 叉树——每个分支点至多有r 个儿子

24 最优二叉树 定义16.9 设2叉树T 有t片树叶v1, v2, …, vt，权分别为w1, w2, …, wt，称 为T 的权，其中l(vi)是vi 的层数. 在所有有t片树叶，带权w1, w2, …, wt 的2叉树中，权最小的2叉树称为最优2叉树. 求最优树的算法—— Huffman算法 给定实数w1, w2, …, wt，且w1w2…wt. (1) 连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2. (2) 在w1+w2, w3, …, wt 中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权. (3) 重复(2)，直到形成 t1个分支点，t片树叶为止.

25 例 5 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由图9给出，W(T)=38