第七章连通性_第1页
第七章连通性_第2页
第七章连通性_第3页
第七章连通性_第4页
第七章连通性_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

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

文档简介

第七章连通性连通图、连通分支、极大连通子图、最小连通子图连通程度的差别？7.1连通度和边连通度若V（G）的一个子集T，使得G-T不连通或是平凡图，则称T是G的一个顶点割。割点？联通程度？定义7.1.1设G是连通图，称数分别为G的（点）连通度和边连通度。衡量图的连通程度的两个重要参数:连通度和边连通度连通度规定：K(完全图)=顶点数-1；K(平凡图)=K(非连通图)=0边连通度规定：λ(完全图)=顶点数-1；λ(非连通图)=λ(平凡图)=0K=0λ=0K=1λ=2K=3λ=3K=4λ=4定理7.1.1对一个图G，有其中是图G的顶点的最小度。定理7.1.2对任何图G，有定理7.1.3设G为p阶图，若，则定义7.1.2如果，则称G是h-连通的；如果，则称G是f-边连通的。所有非平凡图都是1-连通的和1-边连通的。p阶完全图是p-1-连通的定理7.1.5设图G是h-连通的，v是G中的一个顶点，则G-v是（h-1）-连通的。定理7.1.4设图G是h-连通的，则G的每个顶点的度均≥h。7.22-连通图不可分图：没有割点的非平凡的连通图成为不可分图（nonseparablegraph）。不可分图的任一边至少在一个圈中。7.22-连通图定义7.2.1图的一个最大不可分子图称为图G的一个块。定理7.2.1图G是不可分的，当且仅当G是2-连通的。定理7.2.2设G是p>3图，G是2-连通的充要条件是G的任意两个顶点至少由两条内部不相交的道路所连通。定义7.2.2：设P,Q是图G的两条(u,v)的道路。如果除端点u，v外，P和Q没有其他的公共顶点，则称P和Q是内部不相交的。定理7.2.3若G是2-连通的，则G的任意两个顶点都位于同一个圈上。定理7.2.4若G是p≥3的一个2-连通的，则G的任意两条边都在同一个圈上。综上所述，对于一个无环且无孤立点的图G，下面的条件是等价的：（1）图是不

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论