图的连通性
§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在同一圈上。归纳法完成。证毕。



图的连通性离散数学 第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.1 无向图的连通分量和生成树 ?连通:顶点v至v’之间有路径存在 ?连通图:无向图图 G 的任意两点之间都是连通的,则称 G 是 连通...
求图的连通性,8_数学_自然科学_专业资料。“离散数学”实验报告(求图的连通性) 专业班级学号姓名 网络工程 1202 班 12407442 张敏慧 2013.12.14 目录一.实验...
《通信网理论基础》 实 验 指 导 书适用专业—信息工程 实验三:图的连通性判断一、实验目的 本次实验要求用计算机语言编写图的连通性判断算法,可输入图的邻接矩...
热门文档