树的基本概念.ppt
《树的基本概念.ppt》由会员分享,可在线阅读,更多相关《树的基本概念.ppt(23页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、树的基本概念,离散数学树 南京大学计算机科学与技术系,内容提要,树的定义 树的性质 根树 有序根树的遍历,树的定义,定义:不包含简单回路的连通无向图称为树。 森林(连通分支为树) 树叶/分支点(度为1?),互不同构的6个顶点的树,树中的通路,设T是树,则u,vVT, T中存在唯一的 uv-简单通路。 证明:T是连通图,u,vVT, T中存在uv-简单通路。 假设T中有两条不同的uv-简单通路P1,P2。不失一般性,存在e=(x,y)满足:eP1但eP2,且在路径P1上x比y靠近u。令T*=T-e,则T*中包含P2, 于是(P1中的xu-段)+P2+( P1中的vy-段)是T*中的xy-通路,T
2、*中含xy-简单通路(记为P),则P+e是T中的简单回路,与树的定义矛盾。,有关树的几个等价命题,设T是简单无向图,下列四个命题等价: (1) T是不包含简单回路的连通图。/树的定义 (2) T中任意两点之间有唯一简单通路。 (3) T连通,但删除任意一条边则不再连通。 (4) T不包含简单回路,但在任意不相邻的顶点对之间加一条边则产生唯一的简单回路。 备注: 树是边最少的连通图 树是边最多的无简单回路的图,树中边和点的数量关系,设T是树,令n=|VT|, m=|ET|, 则m=n-1。 证明. 对n进行归纳证明。当n=1, T是平凡树,结论显然成立。 假设当nk是结论成立。 若n=k+1。因
3、为T中每条边都是割边,任取eET, 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( n2)的连通图,其边数mn-1。 (对于树,m=n-1, “树是边最少的连通图”) 证明:对n进行归纳证明。当n=2时结论显然成立。 设G是边数为m的连通图,且|VG|=n2。任取vVG,令G=G-v,设G有(1)个连通分支G1,G2,G,且Gi的边数和顶点数分别是mi和ni。 我们有n=n1+n2
4、+n+1, mm1+m2+m+ (每个连通分支中至少有一个顶点在G中与删除的v相邻)。 由归纳假设,mini-1(i=1,2,)。 所以:m m1+m2+m+n1+n2+n-+=n-1。,与边点数量关系有关的等价命题,设T是简单无向图,下列三个命题等价: (1) T是树。 (2) T不含简单回路,且m=n-1。 (3) 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-2n-1, T是非连通图。因此,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本概念
限制150内