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

图的连通性

图的连通性

推论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)的证明与上一定理的证明类似。

上一页第5页

你可能喜欢

热门文档

相关文档

  • 图的连通性

    图的连通性离散数学 第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