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

图的连通性

图的连通性

五、边割集

定义2.1.4对图G,若E(G)的子集E 使得w(G E ) w(G),则称E 为图G的一个边割集。含有k条边的边割集称为k-边割集。

注:(1) 对非平凡图G,若E 是一个边割集,则G\E 不连通。

(2) 一条割边构成一个1-边割集。

(3) 设S V(G),S V(G),S,S ,记号[S,S ]表示一端在S中另一端在S 中的所有边的集合。对图G的每个边割集E ,必存在非空的S V(G),使得[S,]是G的一个边割集,其中 V\S。

六、边连通度: (G) min{|[S,]|| S V(G),S }。完全图的边连通度定义为 (K ) 1。空图的边连通度定义为0。

注:(1)对平凡图或不连通图G, (G) 0。 (2)若图G是含有割边的连通图,则 (G) 1。 (3)若 (G) k,则称G为k-边连通的。 (5)所有非平凡连通图都是1-边连通的。

(6)使得|E | (G)的边割集E 称为G的最小边割集。 定理2.1.5 (G) (G) (G)。 证明:先证 (G) (G)。

若G不连通,则 (G) (G) 0。 若G是完全图,则 (G) (G) 1。

下设G连通但不是完全图。则G有边割集含有 (1 1)条边。设这个边割集为E 。对E 中每条边,选取一个端点,去掉这些端点(至多 个)后,G便成为不连通图,故这些端点构成一个点割集V ,|V | 。因此 (G) |V | (G)。

再证 (G) (G)。

设d(v) 。删去与v关联的 条边后,G变成不连通图,故这 条边构成G的一个边割集。因此 (G) (G)。证毕。

上一页第3页

你可能喜欢

热门文档

相关文档

  • 图的连通性

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