大学本科生课程 离 散 数 学 第16章 树 软件与理论教研室.

Presentation on theme: "大学本科生课程 离 散 数 学 第16章 树 软件与理论教研室."— Presentation transcript:

1 大学本科生课程 离 散 数 学 第16章 树 软件与理论教研室

2 本章说明 树是图论中重要内容之一。 本章所谈回路均指初级回路（圈）或简单回路，不含复杂回路（有重复边出现的回路）。

3 本章说明 16.1 无向树及其性质 16.2 生成树 16.3 根树及其应用 本章小结 习 题 作 业

4 16.1 无向树及其性质 定义16.1 无向树——连通无回路的无向图，简称树，用T表示。 平凡树——平凡图。
森林——若无向图G至少有两个连通分支（每个都是树）。 树叶——无向图中悬挂顶点。 分支点——度数大于或等于2的顶点。 举例 如图为九个顶点的树。

5 无向树的等价定义 定理16.1 设G＝<V,E>是n阶m条边的无向图，则下面各命题是等价的： （1）G是树。
（3）G中无回路且m＝n1。 （4）G是连通的且m＝n1。 （5）G是连通的且G中任何边均为桥。 （6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。 无向树有许多性质，这些性质中有些既是树的必要条件又是充分条件，因而都可以看作树的等价定义。

6 (1)(2) 如果G是树，则G中任意两个顶点之间存在唯一的路径。 存在性。
由G的连通性及定理14.5的推论（在n阶图G中，若从顶点vi到vj(vivj)存在通路，则vi到vj 一定存在长度小于等于n-1的初级通路(路径)）可知， u,v∈V，u与v之间存在路径。 唯一性（反证法）。 若路径不是唯一的，设Г1与Г2都是u到v的路径， 易知必存在由Г1和Г2上的边构成的回路， 这与G中无回路矛盾。

7 (2)(3) 如果G中任意两个顶点之间存在唯一的路径， 则G中无回路且m＝n-1。 首先证明 G中无回路。 若G中存在关联某顶点v的环，
则v到v存在长为0和1的两条路经 (注意初级回路是路径的特殊情况)， 这与已知矛盾。 若G中存在长度大于或等于2的圈， 则圈上任何两个顶点之间都存在两条不同的路径， 这也与已知矛盾。

8 (2)(3) 如果G中任意两个顶点之间存在唯一的路径， 则G中无回路且m＝n-1。 其次证明 m＝n-1。（归纳法）
n＝1时，G为平凡图，结论显然成立。 设n≤k(k≥1)时结论成立， 当n=k+1时，设e＝(u,v)为G中的一条边， 由于G中无回路，所以G-e为两个连通分支G1、G2。 设ni、mi分别为Gi中的顶点数和边数，则ni≤k ，i＝1,2， 由归纳假设可知mi＝ni-1，于是 m＝m1+m2+1＝n1-1+n2-1+1＝n1+n2-1＝n-1。

9 (3)(4) 如果G中无回路且m＝n-1，则G是连通的且m＝n -1。 只需证明G是连通的。（采用反证法）
假设G是不连通的，由s(s≥2)个连通分支G1,G2,…,Gs组成，并且Gi中均无回路，因而Gi全为树。 由(1)(2)(3)可知，mi＝ni-1。于是， 由于s≥2，与m＝n-1矛盾。

10 (4)(5) 如果G是连通的且m＝n1，则G是连通的且G中任何边均为桥。 只需证明G中每条边均为桥。
e∈E，均有|E(G-e)|＝n-1-1＝n-2， 由习题十四题49（若G是n阶m条边的无向连通图，则m≥n-1）可知，G-e已不是连通图， 所以，e为桥。

11 (5)(6) 如果G是连通的且G中任何边均为桥，则G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。
因为G中每条边均为桥，删掉任何边，将使G变成不连通图，所以，G中没有回路，也即G中无圈。 又由于G连通，所以G为树，由(1) (2)可知， u,v∈V，且u≠v，则u与v之间存在唯一的路径Г， 则Г∪(u,v)（(u,v)为加的新边）为G中的圈， 显然圈是唯一的。

12 (6)(1) 如果G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈，则G是树。 只需证明G是连通的。
u,v∈V，且u≠v，则新边(u,v)∪G产生唯一的圈C， 显然有C -(u,v)为G中u到v的通路，故u～v， 由u,v的任意性可知，G是连通的。

13 无向树的性质 定理16.2 设T是n阶非平凡的无向树，则T中至少有两片树叶。 设T有x片树叶，由握手定理及定理16.1可知，
证明 设T有x片树叶，由握手定理及定理16.1可知， 由上式解出x≥2。 公式由于假设有x片度数为1的叶子，其他认为都是度数为2的，这是最小的打算，所以大于等于号成立。

14 例16.1 例16.1 画出6阶所有非同构的无向树。 解答 设Ti是6阶无向树。 由定理16.1可知，Ti的边数mi＝5，
由握手定理可知，∑dTi(vj)＝10，且δ(Ti)≥1，△(Ti)≤5。 于是Ti的度数列必为以下情况之一。 (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，2 (4)对应两棵非同构的树， 在一棵树中两个2度顶点相邻， 在另一棵树中不相邻， 其他情况均能画出一棵非同构的树。

15 例16.1 人们常称只有一个分支点，且分支点的度数为n-1的n(n≥3)阶无向树为星形图，称唯一的分支点为星心。

16 例16.2 例16.2 7阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。
例 阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。 解答 设Ti为满足要求的无向树，则边数mi＝6，于是 ∑d(vj)＝12＝e+3+d(v4)+d(v5)+d(v6)。 由于d(vj)≠1∧d(vj)≠3，而且d(vj)≥1且d(vj)≤6，j＝4,5,6， 可知d(vj)＝2，j＝4,5,6。于是Ti 的度数列为 1，1，1，2，2，2，3 由度数列可知，Ti中有一个3度顶点vi，vi的邻域N(vi)中有3个顶点，这3个顶点的度数列只能为以下三种情况之一： 1,1,2 1,2,2 2,2,2 设它们对应的树分别为T1，T2，T3。此度数列只能产生这三棵非同构的7阶无向树。

17 例16.2

18 例题 例题 已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。
解答 设有x片树叶，于是结点总数为 n＝1+2+x＝3+x 由握手定理和树的性质m＝n1可知， 2m＝2(n1)＝2×(2+x) ＝1×3+2×2+x 解出x＝3，故T有3片树叶。 故T的度数应为1、1、1、2、2、3。

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

20 例题 小节结束

21 16.2 生成树 定义16.2 设G为无向图， （1）T为G的树—T是G的子图并且是树。 （2）T为G的生成树—T是G的生成子图并且是树。
（3）e为T的树枝—设T是G的生成树，e∈E(G)，若e∈E(T)。 （4）e为T的弦—设T是G的生成树，e∈E(G)，若eE(T)。 （5）生成树T的余树—导出子图G[E(G)-E(T)] 。记作

22 说明 注意： 不一定连通，也不一定不含回路。

23 生成树的存在条件 定理16.3 无向图G具有生成树当且仅当G连通。 证明 必要性，显然。 充分性（破圈法）。
证明 必要性，显然。 充分性（破圈法）。 若G中无回路，G为自己的生成树。 若G中含圈，任取一圈，随意地删除圈上的一条边， 若再有圈再删除圈上的一条边，直到最后无圈为止。 易知所得图无圈(当然无回路)、连通且为G的生成子图， 所以为G的生成树。

24 推论 推论1 G为n阶m条边的无向连通图，则m≥n1。 证明 由定理16.3可知，G有生成树，设T为G的一棵生成树，
则m＝|E(G)|≥|E(T)|＝n-1。 推论2 设G是n阶m条边的无向连通图，T为G的生成树， 则T的余树中含有m-n+1条边（即T有m-n+1条弦）。 推论3 设T是连通图G的一棵生成树，T为T的余树， C为G中任意一个圈，则E(T)∩E(C)≠。 证明 若E(T)∩E(C)＝，则E(C)E(T)， 这说明C为T中圈，与T为树矛盾。 所以推论正确。 由推论1立刻可知推论2正确。

25 定理16.4 定理16.4 设T为无向连通图G中一棵生成树，e为T的任意一条弦，则T∪e中含G中只含一条弦其余边均为树枝的圈，而且不同的弦对应的圈也不同。 证明 T∪e中含G中只含一条弦其余边均为树枝的圈。 设e＝(u,v)，由定理16.1可知， 在T中，u, v之间存在惟一的路径 (u,v)， 则 (u,v)∪e为所要求的圈。 不同的弦对应的圈也不同是显然的。

26 基本回路与基本回路系统的定义 定义16.3 设T是n阶m条边的无向连通图G的一棵生成树，设e1, e2, …, emn+1为T的弦。设Cr为T添加弦er产生的G中只含弦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的路径(u,v)，再并上弦e，即得对应e的基本回路。

27 举例 求下图中的基本回路系统。 对应生成树的弦分别为e6,e7,e8,e10,e11。
设它们对应的基本回路分别为C1,C2,C3,C4,C5，从对应的弦开始，按逆时针（也可都按顺时针）的顺序写出它们，分别为 C1＝e6e4e5 C2＝e7e2e1 C3＝e8e9e2e1 C4＝e10e3e5e2 C5＝e11e3e5e2e9 此图的圈秩为5，基本回路系统为{C1,C2,C3,C4,C5}。 无向连通图G的圈秩与生成树的选取无关，但不同生成树对应的基本回路系统可能不同。 说明

28 定理16.5 定理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外都是弦。 不同的树枝对应的割集也不同是显然的。

29 基本割集与基本割集系统的定义 定义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对应的基本割集。

30 举例 求下图中的基本割集系统。 树枝为e1,e2,e3,e4,e5,e9。 设它们对应的基本割集分别为S1,S2,S3,S4,S5,S6。
S1＝{e1,e7,e8} S2＝{e2,e7,e8,e10,e11} S3＝{e3,e10,e11} S4＝{e4,e6} S5＝{e5,e6,e10,e11} S6＝{e9,e8,e11} 此图的割集秩为6，基本割集系统为{S1,S2,S3,S4,S5,S6}。 无向连通图G的割集秩与生成树的选取无关，但不同生成树对应的基本割集系统可能不同。 说明

31 最小生成树 定义16.5 设T是无向连通带权图G＝<V,E,W>的一棵生成树， T的各边权之和称为T的权，记作W(T)。
G的所有生成树中权最小的生成树称为G的最小生成树。 求最小生成树的算法（避圈法(Kruskal)） (1)设n阶无向连通带权图G＝<V,E,W>有m条边。不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大排序：e1,e2,…,em。 (2)取e1在T中。 (3)依次检查e2,…,em ，若ej(j≥2)与已在T中的边不构成回路，取ej也在T中，否则弃去ej。 (4)算法停止时得到的T为G的最小生成树为止。

32 例16.3 例16.3 求下图所示两个图中的最小生成树。 W(T1)＝6 W(T2)＝12

33 例题 例如 求所示图的一棵最小生成树。 解答 最小生成树 W(T)=38 小节结束

34 16.3 根树及其应用 设D是有向图，若D的基图是无向树，则称D为有向树。 在所有的有向树中，根树最重要，所以我们只讨论根树。 二叉树的应用

35 根树的定义 定义16.6 T是n(n≥2)阶有向树， (1) T为根树— T中有一个顶点入度为0，其余顶点的入度均为1
(2) 树根——入度为0的顶点 (3) 树叶——入度为1，出度为0的顶点 (4) 内点——入度为1，出度不为0的顶点 (5) 分支点——树根与内点的总称 (6) 顶点v的层数——从树根到v的通路长度 (7) 树高——T中层数最大顶点的层数 (8) 根树——平凡树

36 根树的画法 树根放上方，省去所有有向边上的箭头。 树叶——8片 内点—— 6个 分支点—— 7个 高度—— 5

37 家族树 常将根树看成家族树，家族中成员之间的关系如下定义。 定义16.7 设T为一棵非平凡的根树，
vi、vj∈V(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代。 若vi邻接到vj（即<vi,vj>∈E(T)），则称vi为vj的父亲，而vj为vi的儿子。 若vj、vk的父亲相同，则称vj与vk是兄弟。 定义16.8 设v为根树T中任意一顶点，称v及其后代的导出子图为以v为根的根子树。

38 根树的分类 (1)设T为根树，若将T中层数相同的顶点都标定次序， 则称T为有序树。 (2)分类：根据根树T中每个分支点儿子数以及是否有序
r叉树——每个分支点至多有r个儿子 r叉有序树——r叉树是有序的 r叉正则树——每个分支点恰有r个儿子 r叉正则有序树——r叉正则树是有序的 r叉完全正则树——树叶层数均为树高的r叉正则树 r叉完全正则有序树——r叉完全正则树是有序的 2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树。 很多实际问题可以用2叉树或m叉树表示，如比赛。

39 最优二叉树 定义16.9 设2叉树T有t片树叶v1, v2, …, vt，权分别为w1, w2, …, wt，称 为T的权，其中l(vi)是vi的层数，在所有有t片树叶、带权w1, w2, …, wt的2叉树中，权最小的2叉树称为最优2叉树。

40 举例 下图所示的三棵2叉树T1,T2,T3都是带权为2、2、3、3、5的2叉树。 W(T1)=2×2+2×2+3×3+5×3+3×2=38
都不是最优树 W(T1)=2×2+2×2+3×3+5×3+3×2=38 W(T2)=3×4+5×4+3×3+2×2+2×1=47 W(T3)=3×3+3×3+5×2+2×2+2×2=36

41 求最优树的算法(Huffman算法) 给定实数w1, w2, …, wt，且w1≤w2 ≤ … ≤ wt。
①连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2。 ② 在w1+w2, w3, …, wt中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权。 ③ 重复② ，直到形成t1个分支点、t片树叶为止。

42 算法举例 例如：求带权为1、1、2、3、4、5的最优树。 解答 W(T)=38

43 最佳前缀码 (1)最佳前最码的定义 定义16.10 设1, 2, …, n-1, n是长度为n的符号串，
设A={1, 2, …, m}为一个符号串集合，若对于任意的i, jA，ij，i, j互不为前缀，则称A为前缀码。 若i(i=1,2,…,m)中只出现0与1两个符号，则称A为二元前缀码。 (2)如何产生二元前缀码？ 定理16.6 由一棵给定的2叉正则树，可以产生唯一的一个二元前缀码。 在通信中，常用二进制编码表示符号。例如可用长为2的二进制编码00，01，10，11分别表示A,B,C,D.称这种表示法为等长码表示法。若在传输中，A,B,C,D出现的频率大体相同，用等长码表示是很好的方法，但当它们出现的频率相差悬殊，为了节省二进制数位，以达到提高效率的目的，就要寻找非等长的编码。

44 方法： 将每个分支点引出的两条边分别标上0和1。 结果： 图所示树产生的前缀码为{00, 10, 11, 011, 0100, 0101}。
由以上产生的任一个前缀码都可以传输5个符号，比如A,B,C,D,E，都不会传错， 但当这些字母出现频率不同时，用哪一个符号串传输哪个字母最省呢？ 这就要用各符号出现的频率（或100乘各频率）为权，利用Huffman算法求最优2叉树， 由最优2叉树产生的前缀码称为最佳前缀码， 用最佳前缀码传输对应的各符号能使传输的二进制数位最省。

45 用Huffman算法产生最佳前缀码 例16.6 在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10%
例16.6 在通信中，八进制数字出现的频率如下： 0：25% ：20% 2：15% ：10% 4：10% ：10% 6： 5% ： 5% 求传输它们的最佳前缀码？ 求传输10n（n≥2）个按上述比例出现的八进制数字需要多少个二进制数字？ 若用等长的（长为3）的码字传输需要多少个二进制数字？

46 传100个按比例出现的八进制数字所需二进制数字个数W(T)=285 ，所以传10n(n2)个所用二进制数字应为2.8510n。
解答 以100乘各频率为权，并按小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25。产生的最优树如下。  0 —— 01 1 —— 11 2 —— 001 3 —— 100 4 —— 101 5 —— 0001 6 —— 00000 7 —— 00001 前缀码节省二进制数字，能提高效率。 传100个按比例出现的八进制数字所需二进制数字个数W(T)=285 ，所以传10n(n2)个所用二进制数字应为2.8510n。 用等长码（长为3）应该用310n个数字。

47 由于在每一步选择两个最小的权的选法不唯一。 因为两个权对应的顶点所放左右位置不同。
右图为例子中的最优树。 由于在每一步选择两个最小的权的选法不唯一。 因为两个权对应的顶点所放左右位置不同。 画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权应该相等，即它们都应该是最优树。 说明

48 3、 波兰符号法与逆波兰符号法 对一棵根树的每个顶点都访问且仅访问一次称为行遍或周游一棵树。 对2叉有序正则树的周游方式： ① 中序行遍法——次序为：左子树、树根、右子树 ② 前序行遍法——次序为：树根、左子树、右子树 ③ 后序行遍法——次序为：左子树、右子树、树根 例如： 中序行遍法：b a (f d g) c e 前序行遍法：a b (c (d f g) e) 后序行遍法：b ((f g d) e c) a

49 用2叉有序正则树存放算式：  最高层次的运算符放在树根上。  依次将运算符放在根子树的根上。  参加运算的数放在树叶上， 规定：被除数、被减数放在左子树树叶上。

50 例如：用二叉有序正则树表示算式 ((b+(c+d))a)((ef)(g+h)(ij))
解答 中序行遍法访问结果是还原算式。

51 波兰符号法 按前序行遍法访问存放算式的2叉有序正则树，其结果不加括号，规定每个运算符号与其后面紧邻两个数进行运算，运算结果正确。称此算法为波兰符号法或前缀符号法。 上图前序行遍法的访问结果为    b + c d a   e f  + g h  i j

52 按后序行遍法访问，规定每个运算符与前面紧邻两数运算，称为逆波兰符号法或后缀符号法。
上图后序行遍法的访问结果为 b c d + + a  e f  g h + i j     小节结束

53 本章主要内容 无向树的定义及其性质。 生成树的定义及存在定理。 基本回路及基本回路系统。 基本割集及基本割集系统。 最小生成树。
无向树的定义及其性质。  生成树的定义及存在定理。  基本回路及基本回路系统。  基本割集及基本割集系统。  最小生成树。 根树及其分类。  最优树、Huffman算法。  最佳前缀码。  波兰符号法与逆波兰符号法。 

54 本章学习要求 深刻理解树的定义和性质。 熟练地求解无向树。 准确地求解最小生成树。
深刻理解树的定义和性质。  熟练地求解无向树。  准确地求解最小生成树。  深刻理解基本回路、基本割集、基本回路系统、基本割集系统等概念。  深刻理解根树、分类、家族树等诸多概念。  会画阶数n较小的非同构的根树。  熟练掌握用Huffman算法求最优树的方法。  熟练掌握求最佳前缀码的方法。  会用二叉树表示算式。  会求算式的波兰符号法和逆波兰符号法表示的算式。  小节结束

55 习 题 1、无向树T有ni个i度顶点，i=2, 3, …,k，其余顶点全是树叶，求T的树叶数。 提示：用树的性质m=n1及握手定理。
解答 提示：用树的性质m=n1及握手定理。 （1） （2） （3） 从而解出 。

56 2、设n阶非平凡的无向树T中，(T)  k，k  1。证明T至少有k片树叶。
反证法。 假设T至多有s片树叶，即s < k， 由于(T)  k，故存在v0，d(v0)  k。 于是， 由此解出s  k，这与s < k矛盾。

57 3、画出基图为右图所示无向树的所有非同构的根树。
解答

58 4、设T是正则2叉树，T有t片树叶，证明T的阶数n=2t1。
方法一、 利用正则2叉树的定义及树的性质直接证明。 （1）n = t+i (i为分支点数) （2）n = m+1 （m为T的边数） （3）m = 2i （正则2叉树定义） 由（2）和（3）得 ，代入（1）得n = 2t1.

59 T的树根为2度顶点，所有内点为3度顶点，而树叶为1度顶点，所以有
方法二、 利用握手定理及树的性质证明。 T的树根为2度顶点，所有内点为3度顶点，而树叶为1度顶点，所以有 （1）2m = 2+3(i1)+t （2）n = m+1 = i+t 由（1）和（2）可解出n = 2t1。 小节结束

60 作业 习题十六： 1、2、3、20、21、23、35 结束