- PDF Free Download

Size: px

Start display at page:

Download ""

娱昝
5 years ago
Views:

1 树的基本概念离散数学树南京大学计算机科学与技术系

3 内容提要树的定义树的性质根树有序根树的遍历

4 树的定义定义 : 不包含简单回路的连通无向图称为树森林连通分支为树 ) 树叶 / 分支点度为 1?) 互不同构的 6 个顶点的树

5 树中的通路设是树, 则 u,v V, 中存在唯一的 uv- 简单通路证明 : 是连通图, u,v V, 中存在 uv- 简单通路假设中有两条不同的 uv- 简单通路 P 1,P 2 不失一般性, 存在 e=,y) 满足 :e P 1 但 e P 2, 且在路径 P 1 上比 y 靠近 u 令 *=-{e}, 则 * 中包含 P 2, 于是 P 1 中的 u- 段 )+P 2 + P 1 中的 vy- 段 ) 是 * 中的 y- 通路, * 中含 y- 简单通路记为 P ), 则 P +e 是中的简单回路, 与树的定义矛盾 u P 1 y v P 2

6 有关树的几个等价命题设是简单无向图, 下列四个命题等价 : 1) 是不包含简单回路的连通图 // 树的定义 2) 中任意两点之间有唯一简单通路 3) 连通, 但删除任意一条边则不再连通 4) 不包含简单回路, 但在任意不相邻的顶点对之间加一条边则产生唯一的简单回路备注 : 树是边最少的连通图树是边最多的无简单回路的图

7 树中边和点的数量关系设是树, 令 n= V, m= E, 则 m=n-1 证明. 对 n 进行归纳证明当 n=1, 是平凡树, 结论显然成立假设当 n k 是结论成立若 n=k+1 因为中每条边都是割边, 任取 e E, -{e} 含两个连通分支, 设其为 1, 2, 并设它们边数分别是 m 1, m 2, 顶点数分别是 n 1, n 2, 根据归纳假设 :m 1 =n 1-1, m 2 =n 2-1 注意 :n 1 +n 2 =n, m 1 +m 2 =m-1 m= m 1 +m 2 +1=n-1

8 连通图边数的下限顶点数为 n n 2) 的连通图, 其边数 m n-1 对于树,m=n-1, 树是边最少的连通图 ) 证明 : 对 n 进行归纳证明当 n=2 时结论显然成立设 G 是边数为 m 的连通图, 且 V G =n>2 任取 v V G, 令 G =G-v, 设 G 有 ωω 1) 个连通分支 G 1,G 2,,G ω, 且 G i 的边数和顶点数分别是 m i 和 n i 我们有 n=n 1 +n 2 + +n ω +1, m m 1 +m 2 + +m ω +ω 每个连通分支中至少有一个顶点在 G 中与删除的 v 相邻 ) 由归纳假设,m i n i -1i=1,2, ω) 所以 :m m 1 +m 2 + +m ω +ω n 1 +n 2 + +n ω -ω+ω=n-1

9 与边点数量关系有关的等价命题设是简单无向图, 下列三个命题等价 : 1) 是树 2) 不含简单回路, 且 m=n-1 3) 连通, 且 m=n-1 1) 2), 已证 2) 3), 若不连通, 分支数 ω 2, 各分支为树无简单回路连通 ), 则 m=n-ω<n-1, 矛盾 3) 1), 设 e 是中任意一条边, 令 =-e, 且其边数和顶点数分别是 m 和 n, 则 m =m-1=n-2<n-1, 是非连通图因此,G 的任意边均不在简单回路中, G 中无简单回路

10 根树的定义定义 : 底图为树的有向图称为有向树定义 : 若有向树恰含一个入度为 0 的顶点, 其它顶点入度均为 1, 则该有向树称为根树, 那个入度为 0 的顶点称为根

11 根树中的有向通路若 v 0 是根树的根, 则对中任意其它顶点 v n, 存在唯一的有向 v 0 v n - 通路, 但不存在 v n v 0 - 通路 v 0 假设 v 0 v n - 通路 p 多于 1 条 v 0 v 0 v n v k 入度 >1 a) w 1 v i b) v n v n c) 假设从 v n 到 v 0 也有通路

12 根树的图形表示边上的方向用约定的位置关系表示根也是内点, 除非它是图中唯一顶点第 0 层第 1 层第 2 层根内点有子女 ) 树叶无子女 ) 树高 =3 最大的通路长度 ) 第 3 层

13 根树与家族关系用根树容易描述家族关系, 反之, 家族关系术语被用于描述根树中顶点之间的关系 John's parent John's ancestors John John s siblings John's child John's descendants

14 根树的几个术语 m 元树 : 每个内点至多有 m 个子女 2 元树也称为二叉树完全 m 元树 ull m-ary tree) 每个内点恰好有 m 个子女平衡 : 树叶都在 h 层或 h-1) 层, h 为树高有序 : 同层中每个顶点排定次序有序二叉树通常也简称为二叉树

15 根树的几个术语续 ) 定义 : 设是根树, 中任一顶点 v 及其所有后代的导出子图显然也是根树以 v 为根 ), 称为的根子树有序二叉树的子树分为左子树和右子树即使不是完全二叉数, 也可以分左右, 必须注意顶点位置左子树右子树

16 根树举例 ) 树的高度各顶点所处的层数完全平衡

17 完全 m 元树的顶点数设是完全 m 元树, 若有 n 个顶点, 则有 i=n-1)/m 个内点和 l=[m-1)n+1]/m 个树叶. 若有 i 个内点, 则有 n=mi+1 顶点和 l=m-1)i+1 个树叶. 若有 l 个树叶, 则有 n=ml-1)/m-1) 个顶点和 i=l-1) )/m-1) 个内点. n-1 = m i 入度总数 = 出度总数 ) n = i + l 顶点分为内点和树叶 )

18 高度为 h 的 m 元树的顶点数高度为 h 的 m 元树最多有个 m h 个树叶按照高度 h 进行归纳证明第 1 层顶点最多为 m 个 ) 若高度为 h 的 m 元树有 l 个树叶, 则 h log m l. 如果这棵树是完全的且平衡的, 则有 h= log m l. m h-1 < l m h

19 有序根树的遍历前序遍历 preorder) 只包含根 r, 则为 r; 的子树为 1,, n, 则为 r, preorder 1 ),, preorder n ) r 1 n

20 有序根树的遍历前序遍历 preorder) a b c d e g h i j k

21 有序根树的遍历后序遍历 postorder) a b c d e g h i j k

22 有序根树的遍历中序遍历 inorder)// 先访问第一棵子树 a b c d e g h i j k

23 作业教材 [10.1, 10.3] p.539: 4, 21, 26, 38, 43 p.564: 9, 25, 29

24 树的应用离散数学树南京大学计算机科学与技术系

25 内容提要表达式的逆 ) 波兰记法二叉搜索树决策树前缀码 Human 编码算法 )

26 表达式的根树表示用根树表示表达式 : 内点对应于运算符, 树叶对应于运算分量举例 :+y)2+ -4)/3) y y 2 4 / y /

27 表达式的逆 ) 波兰表示法 +y)2+ -4)/3) + 前缀形式波兰表示法 ) ++y2/-4 3 / 后缀形式逆波兰表示法 ) y+2 4-3/+ 中缀形式 y 4 +y2+ -4/3

28 中缀表示法的缺陷中缀形式 :+y/+3 有 3 种解释 : + / + +y)/+3) y 3 +y/+3 +y/+3) / 不同的根树有相同的中缀形式 y / y + 3 前缀与后缀则有一定的唯一性 p. 565: 26-27)

29 前缀表示法波兰表示法 ) +y)/+3) /+y+3 + / + +y/+3 y 3 ++/y y/+3) +/y+3 + / 3 y / + 从右向左, 遇到运算符, 对右边紧接着的 2 个运算对象进行运算 y 3

30 后缀表示法逆波兰表示法 ) +y)/+3) y+3+/ + / + +y/+3 y 3 y/ y/+3) y3+/+ + / 3 y / + 从左向右, 遇到运算符, 对左边紧接着的 2 个运算对象进行运算 y 3

31 后缀表示法逆波兰表示法 ) a*b+c)+d*e*))/g+h-i)*j) 逆波兰表示 abc+*de**+ghi-j*+/ 从左往右, 遇到运算符, 根据运算符所需运算分量个数确定前面的元素作为运算分量不需要括弧唯一地表示计算顺序 a * * g * b / d * - c e h i j

32 后缀表达式求值 723*-4 93/ /+ 1493/+ 193/

33 复合命题的根树表示命题 :pq)) pq) p q p q 后缀形式 :pqpq

34 二叉搜索树二叉搜索树满足下列条件二叉树, 各顶点的子女非左即右, 左或右都不超过一个每个顶点有一个唯一的标号, 该标号取自一个全序集若 u 是树中任意的顶点, 则 : u 的左子树中任意顶点的标号小于 u 的标号 u 的右子树中任意顶点的标号大于 u 的标号

35 构造二叉搜索树举例 ) mathematics, physics, geography, zoology, meteorology, geology, psychology, chemistry Mathematics Geography Physics Zoology Chemistry Geology Meteorology Psychology

36 构造二叉搜索树举例 ) mathematics, physics, geography, zoology, Mathematics Mathematics Physics Mathematics Mathematics Physics Physics Geography Geography Zoology

37 二叉搜索树算法 Procedure insertion: binary search tree, :item) // 定位或添加 v:=root o //v 可能为 null i v=null then add a verte to the tree and label it with while v!=null and labelv)!= { i < labelv) then i let child o v!=null then v:= let child o v else add new verte as a let child o v and set v:=null else i right child o v!=null then v:= right child o v else add new verte as a right child o v and set v:=null } i v is null then label new verte with and let v be this new verte return v

38 决策树这样的根树, 每个内点对应一次决策, 子树对应于该决策的后果根到树叶的通路为一个解举例 :8 枚硬币, 其中 7 个等重, 一个重量较轻的是伪币, 使用天平找出伪币, 至少多少次称重? 3 元树, 至少 2 次称重才能确保找到

39 决策树以决策树为模型, 排序算法最坏情形复杂性的下界基于二叉比较的排序算法至少需要 log n! 次比较 n! 个树叶, 其二叉树的高度至少为 log n! n log n)

40 编码如何从信号流中识别字符等长度编码 vs. 不等长度编码例子 : 对包含 {a45),b13),c12),d16),e9),5)}6 个字符的 10 万个字符的数据文件编码, 每个字符后面的数字表示该字符出现的频率 %) 编码方案一 :a000), b001), c010), d011), e100), 101); 则文件总长度 30 万字位编码方案二 :a0), b101), c100), d111), e1101), 1100); 则文件总长度 22.4 万字位, 空间节省四分之一

41 不等长编码的分隔如何从信号流中识别不等长编码表示的字符显式表示长度 : 专用位或特定结束信号匹配的唯一性比如, 前缀码 ) 如果符号串可以表示成符号串 1 和 2 的并置, 则 1 称为的一个前缀注意 : 1 和 2 可以是空串 ) 设 A={ 1, 2,, m } 是符号串的集合, 且对任意 i, j A, 若 ij, i 与 j 互不为前缀, 则称 A 为前缀码若 A 中的任意串 i 只含符号 0, 1, 则称 A 是二元前缀码

42 用二叉树生成二元前缀码生成方法给边标号 : 对内点, 对其出边标上号, 左为 0, 右为 1 给叶编号 : 从根到每个树叶存在唯一的通路, 构成该通路的边的标号依次并置, 所得作为该树叶的编号给定一棵完全二叉树, 可以产生唯一的二元前缀码

43 最优前缀码问题 : 二进前缀码 A={ 1, 2,, m } 表示 m 个不同的字母, 如果各字母使用频率不同, 如何设计编码方案可以使总传输量最少基本思想 : 使用频率高的字母用尽量短的符号串表示问题的解 : 若用频率相对值 ) 作为树叶的权, 最佳二元前缀码对应的二叉树应该是最优二叉树

44 最优二叉树若是二叉树, 且每个叶 v 1,v 2,,v t 带数值权 w 1,w 2, w t, 则二叉树的权 W) 定义为 : t i=1 w i lv i ), 其中 :lv i ) 表示 v i 的层数具有相同权序列的二叉树中权最小的一棵树称为最优二叉树 W)=38 W)=47 W)= W)=34 注意 : 最优二叉树一定是完全二叉树 t2)

45 Human Coding 1952) 输入 : 正实数序列 w 1,w 2,,w t 输出 : 具有 t 个树叶, 其权序列为 w 1,w 2,,w t 的最优二叉树过程 : 棵根树森林 ), 其根的权分别是 w 1,w 2,,w t 选择根权最小的两棵树, 以它们为左右子树合并 ) 生成新的二叉树, 其根权等于 2 棵子树的根权之和重复第 2 步, 直至形成一棵树注意 : 结果可能不唯一如果当前权最小顶点对不唯一 )

46 霍夫曼编码 : 举例例子 : 开始序列 :2,2,3,3,5 1 步后 :4,3,3,5 2 步后 :4,6,5 3 步后 :9, W)=34

47 八个字符的传输问题一个应用示例假设八个字符的频率如下 : 0:25% 1: 20% 2: 15% 3: 10% 4: 10% 5: 10% 6: 5% 7: 5% 则对应的权为 : 5,5,10,10,10,15,20, 传送 1 个字符的加权平均长度 :2.85

48 作业教材 [10.2, 10.3] p.551: 5, 8, 24, 26 p.564: 22, 23, 24

49 Human 算法的正确性设 C 是字母表, 其中每个字符 c 的频率为 [c] 若,y 是两个频率最小的字符, 则必存在 C 的一种最优前缀码, 使得,y 的编码仅有最后一位不同 y y a b a a b b y 为任意最优前缀码在上图的变换中, 二叉树的权保持不变, 即 :W)W ) W ) W)

50 ") ') ) ) "); ') '); ) 0 )) ) ]) [ ] [ ) ] [ ) ] [ ) ] [ ) ] [ ) ] [ ) ] [ ) ] [ ) ] [ ) ) ) ) ') ) ] [ ] [ ], [ ] [ ]; [ ] [ ], [ ] [ ' ' ' W W W W W W W W d a d a d a a d a d a d a d a d a d a d c d c c d c W W b y a y b a C c C c 最小但同理, 于是不妨假设保持权不变的变换

51 Human 算法的正确性续 ) C 是字母表, [c] 为字符 c 的频率,,y 是两个频率最小的字符令 C =C-{,y}{z}, [z]= []+ [y], 若是 C 的最优二叉树, 则将顶点 z 替换为分支点, 并以,y 为其子女, 所得是 C 的一棵最优二叉树矛盾则 : 设得到的新树为并令, 连同它们的父结点替换为一叶结点将中为不失一般性, 与在, 满足如果存在于是因此 ), ' ] [ ] [ ) ] [ ] [ ") '") '", ], [ ] [ ] [, siblings. " ) ") " ]) [ ] [ ) ' ) W, ]) [ ] [ ) ] [ 1) ) ]) [ ] [ ) ] [ ) ] [, 1, ) ) ) ' ' ' W y W y W W y z z y y W W y W y z d z z d y y d y d z d y d d

52 生成树离散数学树南京大学计算机科学与技术系

53 内容提要生成树深度优先搜索广度优先搜索有向图的深度优先搜索回溯最小生成树算法

54 生成树定义 : 若图 G 的生成子图是树, 则该子图称为 G 的生成树无向图 G 连通当且仅当 G 有生成树证明充分性显然 ): 注意 : 若 G 是有简单回路的连通图, 删除回路上的一条边,G 中的回路一定减少因此, 用破圈法总可以构造连通图的生成树 ) 简单无向图 G 是树当且仅当 G 有唯一的生成树注意 :G 中任一简单回路至少有三条不同的边

55 构造生成树 : 深度优先搜索 b e b e a c a c e d e d

56 深度优先搜索算法 Procedure DFSG: 带顶点 v 1,,v n 的连通图 ) := 只包含顶点 v 1 的树 ; visitv 1 ); Procedure visitv:g 的顶点 ) or v 每个邻居 w { } i w 不在中 then { 加入顶点 w 和边 {v, w} 到 ; visitw); }

57 depth-irst search tree Normal spanning trees are also called depth-irst search trees.

58 构造生成树 : 广度优先搜索 b e b e a c a c d e e d

59 广度优先搜索算法 Procedure BFSG: 带顶点 v 1,,v n 的连通图 ) := 只包含顶点 v 1 的树 ; L:= 空表 ; 把 v 1 放入表 L 中 While L 非空 { 删除 L 中的第一个顶点 v; or v 的每个邻居 w { i w 既不在 L 中也不在中 then { 加入 w 到 L 的末尾 ; 加入顶点 w 和边 {v, w} 到 ; } } }

60 有向图的深度优先搜索 a b c d e g h i j k l

61 有向图的深度优先搜索

62 回溯八皇后 ) 在 n n 格的棋盘上放置彼此不受攻击的 n 个皇后从空棋盘开始尝试第 1 列, 第 1 行, n 行 ; 尝试第 2 列, 第 1 行, n 行 ;. 尝试第 k+1 列, 第 1 行, n 行 ;

63 回溯子集和 ) 给定一组正整数 1,, n, 和为 M 的一个子集? 从空子集开始尝试添加一项, 和等于 M, 结束 ; 和不超过 M, 子集包含它 ; 没有合适添加项, 去掉和的最后一项,

64 回溯子集和 ) 举例 :{31, 27, 15, 11, 7, 5}, 和为 39 的子集? {31} {27} {31, 7} {31, 5} {27, 11} {27, 7} {27, 7, 5}

65 Prim 算法求最小生成树 ) 1: E={e}, e 是权最小的边 2: 从 E 以外选择与 E 里顶点关联, 又不会与 E 中的边构成回路的权最小的边加入 E 3: 重复第 2 步, 直到 E 中包含 n-1 条边算法结束

66 Prim 算法举例 ) 铺设一个连接各个城市的光纤通信网络单位 : 万元 ) 12 e a h g d b 60 c

67 Kruskal 算法求最小生成树 ) 1: E={ } 2: 从 E 以外选择不会与 E 中的边构成回路的权最小的边加入 E 3: 重复第 2 步, 直到 E 中包含 n-1 条边算法结束

68 Kruskal 算法举例 ) 铺设一个连接各个城市的光纤通信网络单位 : 万元 ) 12 e a h g d b 60 c

69 Kruskal 算法举例 ) B 269) ) A C ) 29 D I 183) 215) H 216) J 257) ) 53 E 161) F G 后面证明 :Kruskal 算法的正确性

70 引理更换生成树的边 ) 与均是图 G 的生成树, 若 ee 且 ee, 则必有 e'e, e'e, 且 -{e} {e'} 和 '-{e'} {e} 均是 G 的生成树设 e=uv, -{e} 必含两个连通分支, 设为 1, 2 因 ' 是连通图,' 中有 uv- 通路, 其中必有一边满足其两个端点,y 分别在 1, 2 中, 设其为 e', 显然 -{e} {e'} 是生成树而 -{e } 中,y 分属两个不同的连通分支, 但在 *= - {e } {e} 中,u- 通路 +e+vy 通路是一条 y- 通路, 因此 - {e } {e} 连通, 从而 '-{e'} {e} 是生成树 e u v 2 1 y e'

71 Kruskal 算法的正确性显然是生成树按在算法中加边顺序, 中边是 e 1,e 2, e k-1, e k, e n-1 假设不是最小生成树对于任意给定的一棵最小生成树, 存在唯一的 k, 使得 e k E, 且 e i E 1ik). 设是这样的一棵最小生成树, 使得上述的 k 达到最大根据前述引理, 中存在边 e,e 不属于, 使得 *= - {e } {e k } 也是生成树 e 与 e 1,e 2, e k-1 不会构成回路, 因此 we )we k ). 所以 w*)w ), 即 * 也是最小生成树但 * 包含 e 1,e 2, e k-1,e k, 矛盾

72 避圈法与破圈法上述算法都是贪心地增加不构成回路的边, 以求得最优树, 通常称为避圈法 ; 从另一个角度来考虑最优树问题, 在原连通带权图 G 中逐步删除构成回路中权最大的边, 最后剩下的无回路的子图为最优树我们把这种方法称为破圈法

73 作业教材 [10.4, 10.5] p.573:5, 14, 24, 29c), 39 p.580:4, 7, 13, 21

PowerPoint 演示文稿

PowerPoint 演示文稿图的连通性 1 回顾 2 图的定义用图建模图的表示图的运算图的同构提要 3 通路与回路无向图的连通性连通度 2- 连通图有向图的连通性无向图的定向通路的定义 4 定义 : 图 G 中从 v 0 到 v n 的长度为 n 的通路是 G 的 n 条边 e 1,, e n 的序列, 满足下列性质存在 v i V (0 i n), 使得 v i-1 和 v i 是 e i 的两个端点