树的基本概念

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

1、树的基本概念离散数学─树南京大学计算机科学与技术系内容提要树的定义树的性质根树有序根树的遍历树的定义定义：不包含简单回路的连通无向图称为树。森林（连通分支为树）树叶/分支点（度为1？）互不同构的6个顶点的树树中的通路设T是树，则u,vV,T中存在唯一的uv-简单通路。T证明：T是连通图，u,vV,T中存在uv-简单通路。T假设T中有两条不同的uv-简单通路P,P。不失一般性，存在12e=(x,y)满足：eP但eP，且在路径P上x比y靠近u。令121T*=T-{e}，则T*中包含P,于是(P中的xu-

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

3、V

4、,m=

5、E

6、,

7、则m=n-1。TT证明.对n进行归纳证明。当n=1,T是平凡树，结论显然成立。假设当nk是结论成立。若n=k+1。因为T中每条边都是割边，任取eE,T-{e}含两T个连通分支，设其为T,T,并设它们边数分别是m,m,1212顶点数分别是n,n,根据归纳假设：m=n-1,m=n-1。121122注意：n+n=n,m+m=m-1。1212m=m+m+1=n-1。12连通图边数的下限顶点数为n（n2）的连通图，其边数mn-1。(对于树，m=n-1,“树是边最少的连通图”)证明：对n进行一般归纳。当n=2时结论显然成立。设

8、G是边数为m的连通图，且

9、V

10、=n>2。任取vV，令GGG’=G-v,设G’有(1)个连通分支G,G,…,G，且G的边数12i和顶点数分别是m和n。ii我们有n=n+n+…+n+1,mm+m+…+m+(每个连通分1212支中至少有一个顶点在G中与删除的v相邻)。由归纳假设，mn-1(i=1,2,…)。ii所以：mm+m+…+m+n+n+…+n-+=n-1。1212与边点数量关系有关的等价命题设T是简单无向图，下列三个命题等价：(1)T是树。(2)T不含简单回路，且m=n-1。(3)T连通，且m

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

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

13、John'sdescendants根树的几个术语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)个