图的连通性
推论2.2.1 3的图G是2连通图(块)当且仅当G中任二顶点被至少两条内部无公共顶点的路所连。
推论2.2.2 若 3的图G是2连通图(块),则G的任二边都位于同一圈上。
证明:设G是 3的2连通图,且e1,e2 E(G),在e1和e2上各添加一个新的顶点v1和
v2,构成一个新图G 。G 仍是2连通的。由Whitney定理,v1和v2在G 中位于同一个圈上。故e1和e2在G中位于同一个圈上。证毕。
注:Whitney定理可推广到k连通图,得到Menger型定理:
Menger定理1 k 1的图G是k连通图当且仅当G中任二顶点至少被k条内部无公共顶点的路所连。
Menger定理2 图G是k边连通图当且仅当G中任二顶点至少被k条无公共边的路所连。
§2.3 关于割点、割边和块的其它结论
定理2.3.1 设v是连通图G的一个顶点,则下列命题等价: (1) v是G的割点;
(2) 存在u,w V(G),使得u,w v且v在每条(u,w)路上;
(3) 存在V(G)\{v}的一个划分:V(G)\{v} U W,U W ,使得对 u U
和 w W,v在每条(u,w)路上。
证明:(1) (3)因v是割点,故G v至少有两个连通分支G1、G2。令U V(G1)而
W V(G)\(V(G1) {v}),则对 u U和 w W,u、w分别属于G v的不同的连通分支。可见G中所有的(u,w)路必经过v(否则G v中仍有(u,w)路,这与u、w分别属于G v的不同的连通分支矛盾)。
(3) (2)显然。
(2) (1)若v在每条(u,w)路上,则G v中不存在(u,w)路,即G v不连通,故v是G的割点。
证毕。
定理2.3.2 设e是连通图G的一条边,则下列命题等价: (1) 是G的割边; (2) e不在G的任何圈上;
(3) 存在u,v V(G),使得e在每条(u,v)路上;
V(G) U W,U W ,(4) 存在V(G)的一个划分:使得对 u U和 w W,
e在每条(u,w)路上。
证明:(1) (2)定理2.1.1已证。(1) (4) (3) (1)的证明与上一定理的证明类似。
图的连通性离散数学 第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 目录一.实验...
《通信网理论基础》 实 验 指 导 书适用专业—信息工程 实验三:图的连通性判断一、实验目的 本次实验要求用计算机语言编写图的连通性判断算法,可输入图的邻接矩...
热门文档