无向树没有回路的连通图_第1页
无向树没有回路的连通图_第2页
无向树没有回路的连通图_第3页
无向树没有回路的连通图_第4页
无向树没有回路的连通图_第5页
已阅读5页，还剩2页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、第六章,树,无向）树,没有回路的连通图,根树,是计算机科学最常用的概念之一,根树以（无向）树为基础,6.1,树,定义,1,无向）树,无简单回路的连通图,树叶,树中度为,1,的顶点,森林,无简单回路的图（多棵树,树必定不是多重图、伪图,森林的每个连通分支都是树,例,定理,1,无向图是树,每对顶点之间存在唯一的基本通路,证明,首先假定,T,是树。则,T,是没有简单回路的连通图,设,x,和,y,是,T,的两个顶点。因为,T,是连通的，根据连通性定理,1,在,x,和,y,之间存在一条简单通路。另外，这两条通路必,然是唯一的，因为假如存在第二条这样的通路，则组合从,x,到,y,的第一条这样的通路以及经过

2、倒转从,x,到,y,的第二条通,路的顺序所得到的从,y,到,x,的通路，就形成了回路。利用,5.4,节习题,5,这蕴含着在,T,中存在简单回路。因此，在树,的任何两个顶点之间存在唯一简单通路,现在假定在图,T,的任何两个点顶点之间存在唯一简单,通路。则,T,是连通的，因为在它的任何两个顶点之间存在,通路。另外,T,没有简单回路。为了看出这句话是真的,假定,T,有包含顶点,x,和,y,的简单回路。则在,x,和,y,之间就有两,条简单通路，因为这条简单回路包含一条从,x,到,y,的简单通,路和一条从,y,到,x,的简单通路。因此，在任何两个顶点之间,存在唯一简单通路的图是树,定理,2,n,阶无向图

3、是树,无向图连通，且,n-1,有条边,证明,用数学归纳法。在归纳步骤中，删除,1,边,成为两棵树,用反证法。若非树，则有回路，去掉回路中,的,1,条边仍然保持连通性。如此重复，直到成为树，有,n,1X=n-1,条边，与条件矛盾,例,1,一棵树有,2,个,4,度顶点,3,个,3,度顶点，其余都是树叶,问该树有几片树叶,解,设该树有,n,1,片树叶，有,m,条边,n,个顶点,根据树的性质,由握手定理得,该树有,9,片树叶,4,1,3,2,1,1,1,n,n,n,m,9,8,2,17,4,2,3,3,4,2,1,1,1,1,1,n,n,n,n,n,定理,树中任意加一条边就形成回路,证明,若在连通图,G,中两个不相邻的结点,vi,和,vj,之间添,加一条边,v,i,v,j,因为,G,中原来存在,vi,到,vj,的通路，故此时,形成一条经过,v,i,和,v,j,的回路,习题,证明：简单图是树，当且仅当它是连通的，但是删除它的,任何一条边就产生不连通的图,6.2,根树,定义,有向树,有向图，底图是有向树,根树,有一个顶点（称为,根,的入度为,0,其余顶点,的入度均为,1,例,定理,根树中，从根到其余每个顶点有且仅有一条通路,证明,因为,T,是根树，则作为无向图而言，根结点到任何,结点均有通路，若无有向通路，则一定存在某个结点，其

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论