第三章 树 3.1 树的有关定义 给定一个图G=(V,E), 如果它不含任何回路, 我们就叫它是林, 如果G又是连通的, 即这个林只有一个连通支, 就称它是树. 定义3.1.1 一个不含任何回路的连通图称为树, 用T表示. T中的边称为树枝, 度为1的节点称为树叶.

Presentation on theme: "第三章 树 3.1 树的有关定义 给定一个图G=(V,E), 如果它不含任何回路, 我们就叫它是林, 如果G又是连通的, 即这个林只有一个连通支, 就称它是树. 定义3.1.1 一个不含任何回路的连通图称为树, 用T表示. T中的边称为树枝, 度为1的节点称为树叶."— Presentation transcript:

1 第三章 树 3.1 树的有关定义 给定一个图G=(V,E), 如果它不含任何回路, 我们就叫它是林, 如果G又是连通的, 即这个林只有一个连通支, 就称它是树. 定义3.1.1 一个不含任何回路的连通图称为树, 用T表示. T中的边称为树枝, 度为1的节点称为树叶.

2 树的有关定义 树的每条边, 都不会属于任何回路. 这样的边叫割边. 定义3.1.2
设e是G的一条边, 若G’=G-e比G的连通支树连通支数增加, 则称e是G的一条割边. 显然, 图G删去割边e=(u,v)之后, 结点u, v分属于不同的分支.

3 树的有关定义 定理3.1.1 e=(u, v)是割边,当且仅当e不属于G的任何回路. 证明:
必要性。设e=(u, v)是割边, 此时若e=(u, v)属于G的某个回路, 则G’=G-e中仍存在u到v的道路, 故结点u和v属于同一连通支, e不是割边.矛盾. 充分性。设e不属于G的任何回路, 此时若e不是割边, 则G’=G-e与G的连通支数一样. 于是u和v仍属于同一连通支. 故G’中存在道路P(u,v), P(u,v)+e就是G的一个回路.矛盾.

4 树的有关定义 定理3.1.2 设T是结点数为n≥2的树, 则下列性质等价: T连通且无回路 T连通且每条都是割边 T连通且有n-1条边

5 T连通且无回路T连通且每条都是割边 T连通且有n-1条边
12：T无回路，即T的任意边e都不属于回路，由定理3.1.1，e是割边。 23：对结点数n进行归纳。令n(T), m(T)分别表示树T的结点数和边数。当n=2时命题成立。设n≤k时，m(T)=n(T)-1成立。则n=k+1时，由于任一边e都是割边，故G’=G-e有两个连通支T1, T2。由于n(Ti)≤k，i=1,2，故m(Ti)=n(Ti)-1。所以m(T)=n(T)-1也成立。

6 3. T连通且有n-1条边 4. T有n-1条边且无回路 34：假定T有回路，设C是其中一条含有k(<n)个结点的初级回路。因为T连通，所以V(T)-V(C)中一定有结点u与C上某点v相邻，即存在边(u,v)E(T)，依此类推，最终V(T)-V(C)中的n-k个结点需要n-k条边才可能保持T连通，但|E(T)-E(C)|=(n-1)-k<n-k.矛盾.

7 4. T有n-1条边且无回路 5. T的任意两结点间有唯一道路
45：设u,v是T的任意两结点，先证道路P(u,v)的存在性，即证明T是连通的。反证法。 如果T不是连通的，则至少有两个连通分支T1, T2.由已知T中无回路可知，T1, T2也没有回路。根据1  2  3的证明，再由T1和T2是连通的且无回路可得，m(T1)=n(T1)-1, m(T2)=n(T2)-1, 则有： m(T)=m(T1)+m(T2)=(n(T1)+n(T2))-2=n-2<n-1 与已知m(T)=n-1矛盾. 再证唯一性。若存在两条不同的道路P(u,v), P’(u,v)，则其对称差P(u,v)P’(u,v)至少含有一个回路。 注：G1G2=(V,E),其中V=V1V2,E=E1E2;

8 5. T的任意两结点间有唯一道路 6. T无回路, 但在任两结点间加上一条边后恰有一个回路 1. T连通且无回路
56：显然成立 61：只要证明T是连通的。反证法。 假设T不连通，设T1,T2为T中的两个连通分支。v1为T1中的一个顶点，v2为T2中的一个顶点。在T中加边(v1,v2)不形成回路。矛盾。 v1 v2 v3 v4 v5 v6

9 总结 树是极小的连通图，减少一条边就不连通 树是极大的不含回路的连通图，增加一条边就有回路

10 树的有关定义 定理3.1.3 树T中一定存在树叶结点. 证明: 由于T是连通图,所以任一结点viV(T), 都有d(vi)≥1. 若无树叶, 则d(vi)≥2. 这样 矛盾.

11 树的有关定义 定义3.1.3 如果T是图G的支撑子图, 而且又是一棵树, 则称T是G的一棵支撑树, 或称生成树, 又简称G的树

12 生成树 定理：任何无向连通图G都存在生成树。 证明：如果G无回路，则G本身就是它的生成树。

13 一个连通图的生成树可能不唯一。 因为在取定一个回路后，就可以从中去掉任一条边，去掉的边不一样，故可能得到不同的生成树。
a e d b c (a) 1 2 3 4 5 6 7 c a e d b (b) 1 4 6 7 a e d b c (c) 1 3 5 7 在上图(a)中，删去边2,3,5，就得到生成树 (b)， 若删去边2，4，6,可得到生成树 (c)。

14 生成树 (a) (b) (c) 给定图G的一棵树T，我们称G-T，即G删去T中各边后的子图为T的余树。
d e b f a b c d e (a) (b) f (c) 给定图G的一棵树T，我们称G-T，即G删去T中各边后的子图为T的余树。 注：余树不一定连通，也不一定无回路，因而余树不一定是树，更不一定是生成树。

15 3.6 Huffman树 定义3.6.1 除树叶外, 其余结点的正度最多为2的外向树称为二叉树. 如果它们的正度都是2, 称为完全二叉树.
v5 v7 v8 v6 d e v2 b v3 v1 c v4 v0 外向树--若一个有向树T，有且只有一个顶点入度为0，其余顶点入度都为1，则称T为外向树，其中入度为0的节点称为根节点，出度为0的节点称为叶节点

16 树和二叉树 二叉树的每个结点至多只有二棵子树 二叉树的子树有左右之分，次序不能颠倒 二叉树的第i层至多有2(i−1)个结点
深度为k的二叉树至多有2k−1个结点(根结点的深度为1) 树和二叉树的两个主要差别： 树中结点的最大度数没有限制，而二叉树结点的最大出度数为2 树的结点无左、右之分，而二叉树的结点有左、右之分

17 如果二叉树T的每个树叶结点vi都分别赋以一个正实数wi, 则称T是赋权二叉树。
路径：从树中一个结点到另一个结点之间的边构成这两个结点间的路径 从根到树叶vi的路径P(v0, vi)所包含的边数计为该路径的长度l, 这样二叉树T带权的路径总长度为： a v5 2 v2 b v3 1 v1 c v4 2 v0

18 最优二叉树 如果给定了树叶数目以及它们的权值, 可以构造许多不同的赋权二叉树
在这些赋权二叉树中, 必定存在带权路径总长最小的二叉树, 这样的树称为最优二叉树

19 例：有4个结点 a, b, c, d，权值分别为 7, 5, 2, 4，试构造以此4个结点为叶子结点的二叉树。
WPL=72+52+22+42= 36 WPL=73+53+21+42= 46 5 a b c d 7 2 4 a b c d 7 5 2 4 WPL=71+52+23+43= 35 WPL=71+52+23+43= 35

20 带权路径长(WPL: Weighted Path Length )最小的二叉树
最优二叉树 带权路径长(WPL: Weighted Path Length )最小的二叉树 （权值大的结点离根最近） 因为构造这种树的算法是由哈夫曼于 1952 年提出的， 所以被称为哈夫曼树，相应的算法称为哈夫曼算法。

21 Huffman树 哈夫曼算法: 对n(≥2)个权值进行排序,满足wi1≤wi2 ≤…≤win
计算wi=wi1+wi2作为中间结点vi的权, vi的左儿子是vi1, 右儿子是vi2. 在权序列中删去wi1和wi2, 加入wi, n←n-1. 若n=1,结束. 否则转1.

22 例：有5 个结点 a, b, c, d, e，权值分别为 7, 5, 5, 2, 4，构造哈夫曼树。
10 a 7 b 5 c d 2 e 4 6 a 7 b 5 c 2 4 6 d e a 7 b 5 c 2 4 d e b 5 10 c 23 13 10 13 6 7 a 2 5 5 d e 4 b c 6 7 a 2 d e 4

23 Huffman树 定理3.6.1 由Huffman算法得到的二叉树是最优二叉树。 证明：假定n≥3, w1≤w2≤…≤wn，并设T是最优树。
则一定有w1离根最远，即l1=max{l1, l2, …, ln}。否则，假设wk>w1而lk>l1, 则有wkl1+w1lk<wklk+w1l1. 所以将wk和w1对调可得到T’，其满足WPL(T’)<WPL(T), 与T最优矛盾。 同时立即可知，w1必有兄弟。否则让w1赋值给该树叶的父亲结点，就可得到路径总长更小的树。由于w2是序列中次最小的权，故可令w1的兄弟是w2。因此分支w1+w2可以是最优树T的子图。 W1 W2 W1+W2

24 定理3.6.1-证明(续) 设Tn是n个树叶的最优树，收缩分支w1+w2后是对应的n-1个树叶的T’n-1.
在n-1个权(其中之一是w1+w2)时，也有其最优二叉树Tn-1，然后将w1+w2分支展开后又得到有n个权的二叉树T’n。 CLAIM. T’n-1和T’n都是最优树。 当算法执行到n=2时，自然是一棵最优树。再与分支收缩的过程相反进行展开，最后得到的T’n一定是最优二叉树

25 定理3.6.1-证明(续) CLAIM. T’n-1和T’n都是最优树。 因为，Tn和Tn-1分别是最优树，所以
WPL(Tn)≤WPL(T’n)， WPL(Tn-1)≤WPL(T’n-1) 由于， WPL(T’n-1)=WPL(Tn)-(W1+W2)， WPL(Tn-1) =WPL(T’n)-(W1+W2) 所以有WPL(T’n-1)≤WPL(Tn-1) 同理有WPL(T’n)≤WPL(Tn)

26 定理3.6.1-证明(续) W1 W2 Tn W1+W2 T’n-1  W1 W2 W1+W2  Tn-1 T’n

27 最佳前缀码－哈夫曼编码 哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应 用之一。在电讯通信业务中，通常用二进制编码来表示字母或其 他字符，并用这样的编码来表示字符序列。 例：如果需传送的电文为 ‘A B A C C D A’，它只用到四种字符， 用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00， 01，10，11，则上述电文便为 ‘ ’（共 14 位）， 译码员按两位进行分组译码，便可恢复原来的电文。 数据的最小冗余编码问题 在编码过程通常要考虑两个问题 译码的惟一性问题

28 利用最优二叉树可以很好地解决上述两个问题。
数据的最小冗余编码问题 在实际应用中，各个字符的出现频度是不尽相同的，有些字符 出现的频率较高，有些字符出现的频率较低。我们希望用较短的编 码来表示那些出现频率大的字符，用较长的编码来表示出现频率少 的字符，从而使得编码序列的总长度最小，使所需总空间量最少。 这就是最小冗余编码问题。 在上例中，若假设 A, B, C, D 的编码分别为 0，00，1，01， 则电文 ‘A B A C C D A’ 便为 ‘ ’（共 9 位）。 但此编码存在多义性：可译为 ‘A A A A C C A C A’、‘B B C C D A’、‘A B A C C D A’ 等。 译码的惟一性问题 要求任一字符的编码都不能是另一字符编码的前缀！ 这种编码称为最佳前缀码（其实是非前缀码）。 利用最优二叉树可以很好地解决上述两个问题。

29 最佳前缀码 定义 设=12…n-1n是长度为n的符号串, 12…k称作的长度为k的前缀, k=1,2,…,n1. 若非空字符串1, 2, …, m中任何两个互不为前缀, 则称{1, 2, …, m}为前缀码 只出现两个符号(如0与1)的前缀码称作二元前缀码 例如 { 0, 10, 110, 1111 }, { 10, 01, 001, 110 }是二元前缀码 { 0, 10, 010, 1010 } 不是前缀码

30 用二叉树设计二进制前缀码 以电文中的字符作为叶子结点构造二叉树。然后将二叉树中 结点引向其左孩子的分支标 ‘0’，引向其右孩子的分支标 ‘1’； 每 个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如 此得到的即为二进制前缀码。 例： A B C D 1 编码： A：0 B：10 C：110 D：111

31 由哈夫曼树得到的二进制前缀码称为哈夫曼编码。
用哈夫曼树设计总长最短的二进制前缀编码 假设各个字符在电文中出现的次数（或频率）为 wi ，其编码 长度为 li，电文中只有 n 种字符，则电文编码总长为： 从根到叶子的路径长度 叶子结点的权 设计电文总长最短的编码 设计哈夫曼树（以 n 种 字符出现的频率作权） 由哈夫曼树得到的二进制前缀码称为哈夫曼编码。

32 例：设 A, B, C, D 的频率（即权值）分别为 17％, 25％, 38％, 20％，
试设计哈夫曼编码（最佳前缀码）。 解： C 1 编码： C：0 B：10 A：110 D：111 B 38 A D 25 17 20

33 译码 从哈夫曼树根开始，对待译码电文逐位取码。若编码是“0”， 则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出 一个字符；再重新从根出发，直到电文结束。 1 T ; A C S 电文为 “ ” 译文只能是“CAT”

34 3.7 最短树 在赋权连通图中，计算该图总长最小的支撑树，即求最短树 两种算法 Kruskal算法 Prim算法

35 Kruskal算法 基本思想： 不断往T中加入当前的最短边e,如果此时会构成回路，那么它一定是这个回路中的最长边，删之。直至最后达到n-1条边为止。这时T中不包含任何回路，因此是树。 依据树的性质： 若T有n-1条边且无回路，则T是树

36 3.7.1 Kruskal算法 Kruskal算法的描述如下: T←Φ。 当|T| < n – 1且E≠Φ时, begin
e←E中最短边. E←E-e. 若T+e无回路,则T←T+e. end 若|T|<n-1打印”非连通”, 否则输出最短树

37 Kruskal算法实例 1 2 4 3 5 6 图G 1 3 1 3 4 2 6 2 5 3 4 6 1 1 2 4 3 5 6

38 最短树 定理 3.7.1 T=(V, E’)是赋权连通图G=(V, E)的最短树, 当且仅当对任意的余树边e∈E-E’, 回路Ce(CeE’+e), 满足其边权w(e)≥w(a), a∈Ce(a≠e)． 证明:必要性. 如果存在一条余树边e,满足w(e)<w(a), a∈Ce, 则T(a, e)得到新树T’比T更加短,与T是最短树矛盾. 1 2 4 3 5 6 图G 1 5 3 1 2 5 3 4 4 3 2 5 6 T

39 最短树 充分性.即证明：设T=(V, E’)是G=(V, E)的一棵树，如果对任意的余树边e∈E-E’, 回路Ce(CeE’+e), 满足其边权w(e)≥w(a), a∈Ce(a≠e)，那么T是最短树。 反证。若存在比T还短的树T’, 则T’-T≠, 设e∈T’-T, 则T+e构成唯一回路Ce. 根据已知，对任意的T’关于T的余树边e∈T’-T, 它与回路Ce里的树枝边a(a≠e)相比都有w(e)≥w(a), 则有w(T’)≥w(T), 与假设矛盾. 注：因为T和T’都是G的生成树，所以结点数和边数都相同，分别是n和n-1。

40 最短树 定理 3.7.2 Kruskal算法的计算复杂性是 O(m+p＊logm) 其中p是迭代次数．

41 Prim算法 Prim算法的基本思想是： 首先任选一结点v0构成集合U, 然后不断在V-U中选一条到U中某点(比如v)最短的边(u,v)进入树T, 并且U=U+v, 直到U=V

42 最短树 Prim算法的描述如下: t←v1, T←, U←{t} While U≠V do begin
W(t, u)=minv∈V-U{w(t, v)} T←T+e(t, u) U←U+u For vV-U do W(t, v)←min{w(t, v), w(u, v)} end

43 U 1 2 4 3 5 6 U 1 2 4 3 5 6 1 2 4 3 5 6 1 U 1 2 4 3 5 6 U 1 2 4 3 5 6 U 1 2 4 3 5 6

44 Prim算法实例 注意：每当新的结点并入 U 之后，则调整仍在 V - U 集合中的结点直接至 U 中结点的边中的最小边的距离 U 1 2
4 3 5 6 U 1 2 4 3 5 6 注意：每当新的结点并入 U 之后，则调整仍在 V - U 集合中的结点直接至 U 中结点的边中的最小边的距离

45 最短树 定理 3.7.3 设V’是赋权连通图G=(V,E)的结点真子集，e是二端点分跨在V’和V-V’的最短边，则G中一定存在包含e的最短树T． 证明: 设T0是G的一棵最短树, 若eT0, 则T0+e 构成唯一回路. 该回路一定包含e和e’(u, v), 其中uV’, vV-V’. 由已知条件w(e)≤w(e’), 作T0(e, e’)得到的仍是最短树.

46 最短树 定理 3.7.4 Prim算法的结果是: 得到赋权连通图G的一棵最短树． 证明: 首先证明它是一棵支撑树. 采用归纳法.
初始U={v1}, T=, 它是由U导出的树. 设|U|=i, T是U导出的树.则下一次迭代时, U中增加一新结点u, T中也加入一条与u相连的边, 因此T是连通的, 则有|U|-1条边,它是由U导出的一棵树. 因此最终T是G的支撑树.

47 最短树 以下再证T是一棵最短树 设T0是G的一棵最短树, T≠T0, 由定理3.7.3, 对任意的eT-T0, 一定有最短树T’=T0(e, e’), 其中e’Ce∩T0. 继续对T’如此处理,直到最终T’=T, 它仍然是最短树. 注：根据T的构造过程，对于T中的每条边e，都是二端点分跨在某个V’和V-V’的最短边

48 作业 习题三 P66 1，2 14，16

49 考核范围 《数理逻辑与集合论》 《图论与代数结构》 第１章： 第２章：（不含2.10 归结推理法） 第４章：
第５章：（不含存在前束范式，5.6） 《图论与代数结构》 第１章：（不含1.2.4，1.2.5，1.2.6） 第２章： ２．１，２．３，２．４ 第３章： ３．１，３．６．３．７

50 哈密顿图 彼得森图(同构)：哈密顿道路 前束范式

51 离散数学题型示例 考试时间 2017-06-20第18周 星期二10:30－12:30 东上院203 答疑时间
2017年6月19日 下午9:30-15:30 电院3-519