树的基本概念.ppt

《树的基本概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树的基本概念离散数学─树南京大学计算机科学与技术系内容提要树的定义树的性质根树有序根树的遍历树的定义定义：不包含简单回路的连通无向图称为树。森林（连通分支为树）树叶/分支点（度为1？）互不同构的6个顶点的树树中的通路设T是树，则u,vVT,T中存在唯一的uv-简单通路。证明：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-

2、段)+P2+(P1中的vy-段)是T*中的xy-通路，T*中含xy-简单通路(记为P’)，则P’+e是T中的简单回路，与树的定义矛盾。uxyvP2P1有关树的几个等价命题设T是简单无向图，下列四个命题等价：(1)T是不包含简单回路的连通图。//树的定义(2)T中任意两点之间有唯一简单通路。(3)T连通，但删除任意一条边则不再连通。(4)T不包含简单回路，但在任意不相邻的顶点对之间加一条边则产生唯一的简单回路。备注：树是边最少的连通图树是边最多的无简单回路的图树中边和点的数量关系设T是树，令n=

3、VT

4、,m=

5、ET

6、

7、,则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,“树是边最少的连通图”)证明：对n进行归纳证明。当n=2时结论显然

8、成立。设G是边数为m的连通图，且

9、VG

10、=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

11、。(3)T连通，且m=n-1。(1)(2),已证。(2)(3),若不连通，分支数2，各分支为树（无简单回路、连通），则m=n-

12、中任意其它顶点vn,存在唯一的有向v0vn-通路,但不存在vnv0-通路。v0vip假设v0vn-通路多于１条(b)v0vn假设从vn到v0也有通路(c)v0vkw1入度>1(a)vnvn根树的图形表示边上的方向用约定的位置关系表示根内点（有子女）树叶（无子女）第0层第1层第2层第3层树高=3（最大的通路长度）根也是内点，除非它是图中唯一顶点。根树与家族关系用根树容易描述家族关系，反之，家族关系术语被用于描述根树中顶点之间的关系。JohnJohn'schildJohn'sparentJohn'sancestorsJo

13、hn'sdescendantsJohn’ssiblings根树的几个术语m元树：每个内点至多有m个子女2元树也称为二叉树完全m元树(fullm-arytree)每个内点恰好有m个子女平衡：树叶都在h层或(h-1)层,h为树高。有序：同层中每个顶点排定次序有序二叉树通常也简称为二叉树根树的几个术语（续）定义：设T是根树，T中任一顶点v及其所有后代的导出子图显然也是根树(以v为根)，称为T的根子树。有序二叉树的子树分为左子树和右子树即使不是完全二叉数，也可以分左、右，必须注意顶点位置左子树右子树根树（举例）树的高度、各顶

14、点所处的层数完全、平衡完全m元树的顶点数设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（