ch3连通度1
需积分: 0 194 浏览量
2022-08-04
00:22:26
上传
评论
收藏 937KB PDF 举报
2012/10/29
1
第三章
连通度问题
第三章
连通度问题
3.1 连通度
3.2 块
33
可靠通信网的建设
3
.
3
可靠通信网的建设
31
连通度
3
.
1
连通度
B ⊆ E(G)为图G的k-边割 ⇔|B| = k 。
图G的边连通度（edge connectivity）
= 使G变成不连通或平凡图所需去
⎩
⎨
⎧
−
=
为平凡图当
为非平凡图当边割有
G
GkGk
G
0
} min{
)( '
κ
掉的最少边数。
(易见，当G为非平凡连通图时， κ′ = G的最小
键的边数。)
例
′
0
G
平凡或不连通
κ
=
κ′
=2
κ
=1,
κ′
=2
κ
=1,
κ′
=2
κ
=
κ′
=0
κ
=
κ′
=0
例
: κ
′
=
0
⇔
G
平凡或不连通
。
κ′ = 1 ⇔ G连通且含割边。
κ′(K
n
)= n-1 ( n > 0 )。
当G为简单图时，
κ′ = ν -1 ⇔ G ≅ K
ν
。
κ
=2,
κ′
=3
称图G为 k-
边连通的
（k-edge connected）
⇔κ′(G) ≥ k
⇔ 至少去掉k条边才能使G变成不连通或
平凡图。
例如，所有非平凡连通图都是 1-边连通的。
评论0