图论第三章.pdf

文档介绍：: .
图论及其应用第三章
3
v2
v2 v5
v6
v4
v9 v
v v v7 v 6
1 5 3 v1
v
8 v7
v4 v3 G
G1 2 v8
1、分别找G1和G2两个顶点割；
2、给出它们的连通度。
-9-图论及其应用第三章
2. 边连通度的有关概念
（1）边割：G 中形如  , SS 的 E 的子集称为G 的边
割，其中 S 是V 的非空真子集，且 S  V \ S 。

注：1） 平凡图无边割。
2）若E′为G 的边割，则G - E′不连通；但反

之不成立。
a
E={a,b,c}不是边割
b
c 存在真子集为边割
-10- : .
图论及其应用第三章
第三章第三章 连通度连通度

连通度
块
应用：可靠通讯网络的构造
-1- : .
图论及其应用第三章
第三章第三章 连通度连通度

连通度