Presentation is loading. Please wait.

Presentation is loading. Please wait.

树的基本概念.

Similar presentations


Presentation on theme: "树的基本概念."— Presentation transcript:

1 树的基本概念

2 回顾 二部图 二部图中完备匹配(Hall定理) 二部图中的最大匹配 二部图中的稳定匹配

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

4 树的定义 定义:不包含简单回路的连通无向图称为树。 森林(连通分支为树) 树叶/分支点 互不同构的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是不包含简单回路的连通图。//树的定义
备注: 树是边最少的连通图 树是边最多的无简单回路的图 (3)说明每条边都是割边

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的顶点称为根。 若v0是根树T的根,则对T中任意其它顶点vn ,存在唯一 的有向v0vn-通路,但不存在vnv0-通路。

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

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

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

14 根树的几个术语(续) 定义:设T是根树,T中任一顶点v及其所有后代的导出子图显然也是根树(以v为根),称为T的根子树。
有序二叉树的子树分为左子树和右子树 左子树 右子树

15 树的高度、各顶点所处的层数 完全、平衡

16 完全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 (顶点分为内点和树叶)

17 高度为h的m元树的顶点数 高度为h的m元树最多有个mh个树叶。 若高度为h的m元树有l个树叶,则h logml.

18 有序根树的遍历 前序遍历 (preorder) T只包含根r,则为 r;
T的子树为T1, …, Tn, 则为 r, preorder(T1), …, preorder(Tn) r T1 Tn

19 有序根树的遍历 前序遍历 (preorder) 后序遍历 (postorder) 中序遍历 (postorder)

20 作业 见课程网站


Download ppt "树的基本概念."

Similar presentations


Ads by Google