文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 图的连通性
侵权投诉

图的连通性

图的连通性

§2.2连通图的性质-whitney定理

1. 块(block):无割点的连通图。 2. 图的块:若满足下列三条:

(1) H是图G的子图;(2)H本身是一个块;(3)H是具有此性质的极大子图。 则称H是图G的一个块。 例:

块 含4个块的图

注:至少有三个顶点的图是块当且仅当它是2-连通图。(若只有两个顶点,则有反例,例如K2是个块,但不是2连通的。)

3.Whitney定理

定理2.2.1 (Whitney,1932) 3的图G是2-连通图(块)当且仅当G中任二顶点共圈。 证明:充分性:设G中任二顶点在同一圈上,欲证G是2-连通的。

对 w V(G),任取u,v V(G w)。由条件,u,v在G中共处于某个圈C上。若

w C,则在G\w中u,v仍在圈C上;若w C,则G w中u,v在路C w上。总之u,v

在G w中有路相连。由u,v的任意性,G w是连通图,故w不是G的割点。再由w的任意性知,G无割点,即G是2-连通的。

必要性:设G是2-连通图,欲证任二顶点u,v都在同一圈上。

对距离d(u,v)作归纳法。

d(u,v) 1时,因 2,故边uv不是割边,G uv仍连通。因此G uv中存在一条(u,v)路P1 uv上。 1。这表明在G中u, v都在圈P

假定d(u,v) k时,结论成立。下证d(u,v) k时结论也成立。

当d(u,v) k时,设P0 u wv是长为k的一条(u,v)路,则d(u,w) k 1。由归纳法假设,u,w在同一圈上,故在u,w间有两条无公共内部顶点的路P和Q。因G是2连通图,故G w仍连通。在G w中存在(u,v)路P 。令x是P 上最后一个与P Q的公共顶点(因u P Q,这样的x存在)。不妨设x P,则P上(u,x)段+P 上(x,v)段与

Q wv是两条内部无公共点的(u,v)路。故u,v在同一圈上。归纳法完成。证毕。

图的连通性

图的连通性

图的连通性

上一页第4页

你可能喜欢

热门文档

相关文档

  • 图的连通性

    图的连通性离散数学 第22讲 上一讲内容的回顾通路与回路 连通与连通图 扩大路径证明法 最短通路问题与Dijstra算法 图的连通性割点 割边(桥) (点)连通度 ( ...

  • 图论课件第三章 图的连通性

    图论课件第三章 图的连通性_数学_自然科学_专业资料。图论课件1 0 .5 n 0 ? 0 .5 ?1 2 1 .5 t 1 0 .5 0 0 0 .4 0 .2 x 0 .8 0 .6...

  • 图的连通性总结

    图的连通性总结_IT/计算机_专业资料。强连通分量图的连通性总结 boboo 目录 1. 图的遍历及应用 1.1. DFS 遍历 1.2. DFS 树的边分类 1.3. DFS 树的...

  • 图的连通性问题

    图的连通性问题 £7.4 图的连通性问题£7.4.1 无向图的连通分量和生成树(1)连通图 在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发, 进行深度...

  • 图的连通性

    图的连通性 //割点 割点 vector<int>map[Max]; //邻接表 int n, root, times; int dfn[Max], low[Max]; int flag[Max]; int Min( int a,int b...

  • 图的连通性判断

    图的连通性判断_工学_高等教育_教育专区。可以明确找出图中各个分支,并确定各节点的归属。基于MATLAB 的实现,此方法可以知道有几个连通域,并且知道各个顶点的...

  • 7.4 图的连通性问题

    7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 ?连通:顶点v至v’之间有路径存在 ?连通图:无向图图 G 的任意两点之间都是连通的,则称 G 是 连通...

  • 求图的连通性,8

    求图的连通性,8_数学_自然科学_专业资料。“离散数学”实验报告(求图的连通性) 专业班级学号姓名 网络工程 1202 班 12407442 张敏慧 2013.12.14 目录一.实验...

  • 3-图的连通性

    《通信网理论基础》 实 验 指 导 书适用专业—信息工程 实验三:图的连通性判断一、实验目的 本次实验要求用计算机语言编写图的连通性判断算法,可输入图的邻接矩...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email