第三章树 3.1 树的有关定义

Size: px

Start display at page:

Download "第三章树 3.1 树的有关定义"

堪口伍
7 years ago
Views:

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

2 有关度的若干术语孤立点 : 度为 0 的顶点悬点 : 度为的顶点悬边 : 与悬点关联的边奇点 : 度为奇数的顶点偶点 : 度为偶数的顶点正则图 : 各顶点度相同若度为 k, 称为 k- 正则图. 例如 :K n 是 (n )- 正则图

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

4 树的有关定义定理 3.. 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 的一个回路. 矛盾.

5 树的有关定义定理 3..2 设 T 是结点数为 n 2 的树, 则下列性质等价 :. T 连通且无回路 2. T 连通且每条都是割边 3. T 连通且有 n- 条边 4. T 有 n- 条边且无回路. T 的任意两结点间有唯一道路. T 无回路, 但在任两结点间加上一条边后恰有一个回路

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

7 3. T 连通且有 n- 条边 4. T 有 n- 条边且无回路 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-)-k<n-k. 矛盾.

8 4. T 有 n- 条边且无回路. T 的任意两结点间有唯一道路 4 : 设 u,v 是 T 的任意两结点, 先证道路 P(u,v) 的存在性, 即证明 T 是连通的反证法如果 T 不是连通的, 则至少有两个连通分支 T, T 2. 由已知 T 中无回路可知,T, T 2 也没有回路根据 2 3 的证明, 再由 T 和 T 2 是连通的且无回路可得,m(T )=n(t )-, m(t 2 )=n(t 2 )-, 则有 : m(t)=m(t )+m(t 2 )=(n(t )+n(t2))-2=n-2<n- 与已知 m(t)=n- 矛盾. 再证唯一性若存在两条不同的道路 P(u,v), P (u,v), 则其对称差 P(u,v) P (u,v) 至少含有一个回路注 :G G 2 =(V,E), 其中 V=V V 2,E=E E 2 ;

9 . T 的任意两结点间有唯一道路. T 无回路, 但在任两结点间加上一条边后恰有一个回路. T 连通且无回路 : 显然成立 : 只要证明 T 是连通的反证法假设 T 不连通, 设 T,T 2 为 T 中的两个连通分支 v 为 T 中的一个顶点,v 2 为 T 2 中的一个顶点在 T 中加边 (v,v 2 ) 不形成回路 v 矛盾 v 2 v 3 v 4 v v

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

11 树的有关定义定理 3..3 树 T 中一定存在树叶结点. 证明 : 由于 T 是连通图, 所以任一结点 v i V(T), 都有 d(v i ). 若无树叶, 则 d(v i ) 2. 这样矛盾. n m d( vi ) 2 n

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

13 生成树定理 : 任何无向连通图 G 都存在生成树证明 : 如果 G 无回路, 则 G 本身就是它的生成树如 G 有回路, 则在回路上任取一条边去掉仍是连通的, 如 G 仍有回路, 则继续在该回路上去掉一条边, 直到图中无回路为止, 此时, 该图就是 G 的一棵生成树

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

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

16 作业 P,2

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

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

19 如果二叉树 T 的每个树叶结点 v i 都分别赋以一个正实数 w i, 则称 T 是赋权二叉树路径 : 从树中一个结点到另一个结点之间的边构成这两个结点间的路径从根到树叶 v i 的路径 P(v 0, v i ) 所包含的边数计为该路径的长度 l, 这样二叉树 T 带权的路径总长度为 : v 0 WPL liwi, i vi 是树叶 v v 2 b v 3 c v 4 2 a v 2

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

21 例 : 有 4 个结点 a, b, c, d, 权值分别为 7,, 2, 4, 试构造以此 4 个结点为叶子结点的二叉树 c 2 7 a b c 2 d 4 WPL= = 3 4 d 7 a b WPL= = 4 7 a 7 a b b 2 c d 4 WPL= = 3 2 c d 4 WPL= = 3

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

23 Huffman 树哈夫曼算法 :. 对 n( 2) 个权值进行排序, 满足 w i w i2 w in 2. 计算 w i =w i +w i2 作为中间结点 v i 的权, v i 的左儿子是 v i, 右儿子是 v i2. 在权序列中删去 w i 和 w i2, 加入 w i, n n-. 若 n=, 结束. 否则转.

24 例 : 有个结点 a, b, c, d, e, 权值分别为 7,,, 2, 4, 构造哈夫曼树 0 7 a b c 2 d 4 e 7 a b c b c 7 a 2 d e 4 2 d e b c 7 a d e 4 b c 7 a 2 d e 4

25 Huffman 树定理 3.. 由 Huffman 算法得到的二叉树是最优二叉树证明 : 假定 n 3, w w 2 w n, 并设 T 是最优树则一定有 w 离根最远, 即 l =max{l, l 2,, l n } 否则, 假设 w k >w 而 l k >l, 则有 w k l +w l k <w k l k +w l. 所以将 w k 和 w 对调可得到 T, 其满足 WPL(T )<WPL(T), 与 T 最优矛盾同时立即可知,w 必有兄弟否则让 w 赋值给该树叶的父亲结点, 就可得到路径总长更小的树由于 w 2 是序列中次最小的权, 故可令 w 的兄弟是 w 2 因此分支 w +w 2 可以是最优树 T 的子图 W +W 2 W W 2

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

27 定理 3..- 证明 ( 续 ) CLAIM. T n- 和 T n 都是最优树因为,T n 和 T n- 分别是最优树, 所以 WPL(T n ) WPL(T n ), WPL(T n- ) WPL(T n- ) 由于, WPL(T n- )=WPL(T n )-(W +W 2 ), WPL(T n- ) =WPL(T n )-(W +W 2 ) 所以有 WPL(T n- ) WPL(T n- ) 同理有 WPL(T n ) WPL(T n )

28 定理 3..- 证明 ( 续 ) W W 2 T n W +W 2 T n- W +W 2 T n- T n W W 2

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

数据的最小冗余编码问题在实际应用中, 各个字符的出现频度是不尽相同的, 有些字符出现的频率较高, 有些字符出现的频率较低我们希望用较短的编码来表示那些出现频率大的字符, 用较长的编码来表示出现频率少的字符, 从而使得编码序列的总长度最小, 使所需总空间量最少这就是最小冗余编码问题在上例中, 若假设 A, B, C, D 的编码分别为

30 数据的最小冗余编码问题在实际应用中, 各个字符的出现频度是不尽相同的, 有些字符出现的频率较高, 有些字符出现的频率较低我们希望用较短的编码来表示那些出现频率大的字符, 用较长的编码来表示出现频率少的字符, 从而使得编码序列的总长度最小, 使所需总空间量最少这就是最小冗余编码问题在上例中, 若假设 A, B, C, D 的编码分别为 0,00,,0, 则电文 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 等译码的惟一性问题要求任一字符的编码都不能是另一字符编码的前缀! 这种编码称为最佳前缀码 ( 其实是非前缀码 ) 利用最优二叉树可以很好地解决上述两个问题

31 最佳前缀码定义设 = 2 n- n 是长度为 n 的符号串, 2 k 称作的长度为 k 的前缀, k=,2,,n. 若非空字符串, 2,, m 中任何两个互不为前缀, 则称 {, 2,, m } 为前缀码只出现两个符号 ( 如 0 与 ) 的前缀码称作二元前缀码例如 { 0, 0, 0, }, { 0, 0, 00, 0 } 是二元前缀码 { 0, 0, 00, 00 } 不是前缀码

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

33 用哈夫曼树设计总长最短的二进制前缀编码假设各个字符在电文中出现的次数 ( 或频率 ) 为 w i, 其编码长度为 l i, 电文中只有 n 种字符, 则电文编码总长为 : WPL n i w i l i 从根到叶子的路径长度叶子结点的权设计电文总长最短的编码设计哈夫曼树 ( 以 n 种字符出现的频率作权 ) 由哈夫曼树得到的二进制前缀码称为哈夫曼编码

34 例 : 设 A, B, C, D 的频率 ( 即权值 ) 分别为 7%, 2%, 38%, 20%, 试设计哈夫曼编码 ( 最佳前缀码 ) 解 : 0 编码 : C:0 C 38 B 2 0 A 0 D 7 20 B:0 A:0 D:

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

36 3.7 最短树 ( 最小生成树 ) 在赋权连通图中, 计算该图总长最小的支撑树, 即求最短树两种算法 Kruskal 算法 Prim 算法

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

38 3.7. Kruskal 算法 Kruskal 算法的描述如下 : T Φ 当 T < n 且 E Φ 时, begin. e E 中最短边. 2. E E-e. 3. 若 T+e 无回路, 则 T T+e. end 若 T <n- 打印非连通, 否则输出最短树

39 Kruskal 算法实例图 G

40 最短树定理 3.7. T=(V, E ) 是赋权连通图 G=(V, E) 的最短树, 当且仅当对任意的余树边 e E-E, 回路 C e (C e E +e), 满足其边权 w(e) w(a), a C e (a e). 证明 : 必要性. 如果存在一条余树边 e, 满足 w(e)<w(a), a C e, 则 T (a, e) 得到新树 T 比 T 更加短, 与 T 是最短树矛盾图 G T

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

42 最短树定理 Kruskal 算法的计算复杂性是 O(m+p*logm) 其中 p 是迭代次数.

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

44 最短树 Prim 算法的描述如下 :. t v, T, U {t} 2. While U V do begin 3. W(t, u)=min v V-U {w(t, v)} 4. T T+e(t, u). U U+u. For v V-U do W(t, v) min{w(t, v), w(u, v)} end

45 U U U U U

46 Prim 算法实例 U U 注意 : 每当新的结点并入 U 之后, 则调整仍在 V - U 集合中的结点直接至 U 中结点的边中的最小边的距离

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

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

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

50 作业 P 4,

51 考核范围数理逻辑与集合论第章 ; 第 2 章 ( 不含 2.0); 第 4 章 ; 第章 ( 不包括存在型前束范式与.) 归结法不考核图论与代数结构第章 : ( 不包括.2.4,.2.,.2.) 第 2 章 : 2., 2.3, 2.4 第 3 章 : 3., 3., 3.7

树的定义如图, a b a b a b a b c d c d c d c d e f e f e f e f (a) G 1 (b) G 2 (c) G 3 (d) G 4 G 1 和 G 2 是树, 它们都是没有回路的简单图 G 3 不是树, 因为结点 a, b, e, d 构成回路 G 4

树的定义如图, a b a b a b a b c d c d c d c d e f e f e f e f (a) G 1 (b) G 2 (c) G 3 (d) G 4 G 1 和 G 2 是树, 它们都是没有回路的简单图 G 3 不是树, 因为结点 a, b, e, d 构成回路 G 4 Chapter 7 树 Discrete Mathematics November 29, 2011 黄正华, 数学与统计学院, 武汉大学 71 Contents 1 树与生成树 1 2 根树及其应用 8 72 1 树与生成树树与生成树 1 树的定义 2 生成树 3 最小生成树 4 Kruskal 算法树是图论中重要的概念之一, 在计算机科学中有广泛的运用 73 树的定义 Definition 1

第三章 树 3.1 树的有关定义

第三章树 3.1 树的有关定义