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

Presentation on theme: "树的基本概念 离散数学─树 南京大学计算机科学与技术系."— Presentation transcript:

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

2

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

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

5 树中的通路  设T是树，则u,vVT, T中存在唯一的 uv-简单通路。
假设T中有两条不同的uv-简单通路P1,P2。不失一般性，存在e=(x,y)满足：eP1但eP2，且在路径P1上x比y靠近u。令T*=T-{e}，则T*中包含P2, 于是(P1中的xu-段)+P2+( P1中的vy-段)是T*中的xy-通路，T*中含xy-简单通路(记为P’)，则P’+e是T中的简单回路，与树的定义矛盾。 u x y v  P2 P1

6 有关树的几个等价命题 设T是简单无向图，下列四个命题等价： (1) T是不包含简单回路的连通图。//树的定义
备注： 树是边最少的连通图 树是边最多的无简单回路的图

7 树中边和点的数量关系 设T是树，令n=|VT|, m=|ET|, 则m=n-1。
证明. 对n进行归纳证明。当n=1, T是平凡树，结论显然成立。 假设当nk是结论成立。 若n=k+1。因为T中每条边都是割边，任取eET, T-{e}含两个连通分支，设其为T1, T2, 并设它们边数分别是m1, m2, 顶点数分别是n1, n2, 根据归纳假设：m1=n1-1, m2=n2-1。注意：n1+n2=n, m1+m2=m-1。 m= m1+m2+1=n-1。

8 连通图边数的下限 顶点数为n（ n2）的连通图，其边数mn-1。 (对于树，m=n-1, “树是边最少的连通图”)
设G是边数为m的连通图，且|VG|=n>2。任取vVG，令G’=G-v,设G’有(1)个连通分支G1,G2,…,G，且Gi的边数和顶点数分别是mi和ni。 我们有n=n1+n2+…+n+1, mm1+m2+…+m+ (每个连通分支中至少有一个顶点在G中与删除的v相邻)。 由归纳假设，mini-1(i=1,2,…)。 所以：m m1+m2+…+m+n1+n2+…+n-+=n-1。

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

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

11 根树中的有向通路 若v0是根树T的根,则对T中任意其它顶点vn ,存在唯一的有向v0vn-通路,但不存在vnv0-通路。 v0 v0 v0
p vn vi vk 假设从 vn 到 v0　也有通路 vn 入度>1 vn w1 (a) (b) (c)

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

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

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

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

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

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

18 高度为h的m元树的顶点数 mh-1 l  mh 高度为h的m元树最多有个mh个树叶。
若高度为h的m元树有l个树叶，则h logml. 如果这棵树是完全的且平衡的，则有h= logml. mh-1 l  mh

19 有序根树的遍历 前序遍历 （preorder） T只包含根r，则为 r；
T的子树为T1, …, Tn, 则为 r, preorder(T1), …, preorder(Tn) r T1 … Tn

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

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

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

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