树的基本概念

回顾 二部图 二部图中完备匹配（Hall定理） 二部图中的最大匹配 二部图中的稳定匹配

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

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

树中的通路  设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

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

树中边和点的数量关系 设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。

连通图边数的下限 顶点数为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。

与边点数量关系有关的等价命题 设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中无简单回路。

根树的定义 定义：底图为树的有向图称为有向树。 定义：若有向树恰含一个入度为0的顶点，其它顶 点入度均为1，则该有向树称为根树，那个入度为 0的顶点称为根。 若v0是根树T的根,则对T中任意其它顶点vn ,存在唯一 的有向v0vn-通路,但不存在vnv0-通路。

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

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

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

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

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

完全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 （顶点分为内点和树叶）

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

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

有序根树的遍历 前序遍历 （preorder） 后序遍历 （postorder） 中序遍历 （postorder）

作业 见课程网站