《集合论与图论》第16讲1
第16讲连通度
?1. 点(边)割集,点连通度κ,边连通度λ
?2. Whitney定理, 简单连通图κ,λ,δ之间的
关系
?3. 2-连通, 2-边连通的充要条件
?4. 割点, 桥, 块的充要条件
《集合论与图论》第16讲2
如何定义连通度
?问题: 如何定量比较无向图连通性的强与
弱?
《集合论与图论》第16讲3
如何定义连通度
?点连通度: 为了破坏连通性,至少需要删
除多少个顶点?
?边连通度: 为了破坏连通性,至少需要删
除多少条边?
?说明: “破坏连通性”指p(G-V’)>p(G), 或
p(G-E’)>p(G),即“变得更加不连通”
《集合论与图论》第16讲4
割集(cutset)
?点割集(vertex cut)
?边割集(edge cut)
?割点(cut vertex)
?割边(cut edge)(桥)(bridge)
《集合论与图论》第16讲5
点割集(vertex cutset)
?点割集: 无向图G=<V,E>, ?≠V’?V, 满足
(1) p(G-V’)>p(G);
(2) 极小性: ? V’’?V’, p(G-V’’)=p(G),
则称V’为点割集.
?说明: “极小性”是为了保证点割集概念的
非平凡性
《集合论与图论》第16讲6
点割集(举例)
?G
1
: {f},{a,e,c},{g,k,j},{b,e,f,k,h}
?G
2
: {f},{a,e,c},{g,k,j},{b,e,f,k,h}
a
b
cd
f
e
g
h
k
ji
a
b
c
ef
dj
i
g
h
k
G
1
G
2
《集合论与图论》第16讲7
割点(cut-point / cut-vertex)
?割点: v是割点? {v}是割集
?例: G
1
中f是割点, G
2
中无割点
a
b
cd
f
e
g
h
k
ji
a
b
c
ef
dj
i
g
h
k
G
1
G
2
《集合论与图论》第16讲8
边割集(edge cutset)
?边割集: 无向图G=<V,E>, ?≠E’?E, 满足
(1) p(G-E’)>p(G);
(2) 极小性: ?E’’?E’, p(G-E’’)=p(G),
则称E’为边割集.
?说明: “极小性”是为了保证边割集概念的
非平凡性
《集合论与图论》第16讲9
边割集(举例)
?G
1
: {(a,f),(e,f),(d,f)}, {(f,g),(f,k),(j,k),(j,i)}
{(a,f),(e,f),(d,f),(f,g),(f,k),(f,j)}, {(c,d)}
?G
2
: {(b,a),(b,e),(b,c)}
a
b
cd
f
e
g
h
k
ji
a
b
c
ef
dj
i
g
h
k
G
1
G
2
《集合论与图论》第16讲10
割边(cut-edge)(桥)
?割边: (u,v)是割边? {(u,v)}是边割集
?例: G
1
中(f,g)是桥, G
2
中无桥
a
b
cd
f
e
l
h
k
ji
a
b
c
ef
dj
i
g
h
k
G
1
G
2
g
《集合论与图论》第16讲11
扇形割集(fan cutset)
?I
G
(v)不一定是边割集(不一定极小)
?I
G
(v)不是边割集? v是割点
?扇形割集: E’是边割集∧E’?I
G
(v)
?例: {(a,g),(a,b)},{(g,a),(g,b),(g,c)},{(c,d)},
{(d,e),(d,f)}, {(a,b),(g,b),(g,c)}
a
b
c
gd
f
e
《集合论与图论》第16讲12
点连通度(vertex-connectivity)
?点连通度: G是无向连通非完全图,
κ(G) = min{ |V’| | V’是G的点割集}
?规定: κ(K
n
) = n-1, G非连通: κ(G)=0
?例: κ(G)=1, κ(H)=2, κ(F)=3, κ(K
5
)=4
GHF
《集合论与图论》第16讲13
边连通度(edge-connectivity)
?边连通度: G是无向连通图,
λ(G) = min{ |E’| | E’是G的边割集}
?规定: G非连通: λ(G)=0
?例: λ(G)=1, λ(H)=2, λ(F)=3, λ(K
5
)=4
GHF
《集合论与图论》第16讲14
k-连通图, k-边连通图
?k-连通图(k-connected): κ(G)≥k
?k-边连通图(k-edge-connected): λ(G)≥k
?例: 彼得森图κ=3, λ=3; 它是1-连通图,
2-连通图,3-连通图, 但不是4-连通图; 它
是1-边连通图, 2-边连通图,3-边连通图,但
不是4-边连通图
《集合论与图论》第16讲15
Whitney定理
?定理10: κ≤λ≤δ.
?证明: 不妨设G是3阶以上连通简单非完
全图.
(λ≤δ) 设d(v)=δ, 则|I
G
(v)|=δ, I
G
(v)中一定
有边割集E’, 所以λ≤|E’|≤|I
G
(v)|=δ.
(κ≤λ) 设E’是边割集,|E’|=λ,从V(E’)中找出
点割集V’,使得|V’|≤λ, 所以κ≤|V’|≤λ.
《集合论与图论》第16讲16
引理1
?引理1: 设E’是边割集,则p(G-E’)=p(G)+1.
?证明: 如果p(G-E’)>p(G)+1, 则E’不是边
割集, 因为不满足定义中的极小性. #
?说明: 点割集无此性质
《集合论与图论》第16讲17
引理2
?引理2:设E’是非完全图G的边割集,
λ(G)=|E’|,G-E’的2个连通分支是G
1
,G
2
,则
存在u∈V(G
1
),v∈V(G
2
),使得(u,v)?E(G)
?证明: (反证)否则λ(G)=|E’|
=|V(G
1
)|×|V(G
2
)|≥|V(G
1
)|+|V(G
2
)|-1=n-1,
与G非完全图相矛盾! #
?说明: a≥1∧b≥1?(a-1)(b-1)=ab-a-b+1≥0
? ab≥a+b-1.
《集合论与图论》第16讲18
Whitney定理(续)
?证明(续): (κ≤λ) 设G-E’的2个连通分支是
G
1
,G
2
. 设u∈V(G
1
),v∈V(G
2
),使得
(u,v)?E(G). 如下构造V’’:?e∈E’, 选择e的
异于u,v的一个端点放入V’’. |V’’|≤|E’|.
G-V’’?G-E’=G
1
∪G
2
, u和v在G-V’’中不连
通, 所以V’’中含有点割集V’.
所以κ≤|V’|≤|V’’|≤|E’|=λ.
#
u
v
《集合论与图论》第16讲19
推论
?推论: k-连通图一定是k-边连通图. #
《集合论与图论》第16讲20
Hassler Whitney(1907~1989)
?美国数学家,曾获得Wolf奖
?主要研究拓扑学. 20世纪30年代发表了
十几篇图论论文,定义了“对偶图”概念,推
动了四色定理的研究.
?一生的最后20年致力于数学教育,提倡应
当让年轻人用自己的直觉(intuition)来解
决问题,而不是教一些与他们的经验无关
的技巧和结果.
《集合论与图论》第16讲21
Whitney的看法
?应当让年轻人用自己的直觉(intuition)来
解决问题,而不是教一些与他们的经验无
关的技巧和结果.
?什么是直觉?------习惯成自然,熟能生巧
?骑自行车: “平衡感”
?游泳: “水感”
?学外语: “语感”
?如何取得经验?------自己动手
?练习! 不能只听不做.
《集合论与图论》第16讲22
简单连通图的κ,λ,δ
?定理14: n阶简单连通图的κ,λ,δ之间关系
有且仅有3种可能:
(1) κ = λ = δ = n-1
(2) 1 ≤ 2δ-n+2 ≤κ≤λ = δ ≤ n-2
(3) 0 ≤κ≤λ≤δ< ?n/2?
?证明: (有):构造出满足上述关系的图
(仅有):任意简单连通图G可以归入以上3类
《集合论与图论》第16讲23
定理14((有)(1))
?证明: (有): (1) κ = λ = δ = n-1.
令G = K
n
即可.
?注意: κ(K
1
)=λ(K
1
)=δ(K
1
)=0, 但是K
1
连通,
所以, 非连通?κ=λ=0, 反之不然
《集合论与图论》第16讲24
定理14((有)(2))
?证明: (有)(2)1≤2δ-n+2≤κ≤λ=δ≤n-2
令r=?(n-κ)/2?, s= ?(n-κ-1)/2?, 则r+s=n-κ-1.
令G’=K
κ
+(K
r
∪K
s
). 给G’增加顶点v, 使得
v与K
κ
中所有顶点相邻, 与K
s
中δ-κ个顶点
相邻, 就得到G.
K
κ
K
r
K
s
K
δ-κ
v
《集合论与图论》第16讲25
定理14((有)(2)(续))
?证明: (有)(2) (分析) δ(G)=δ:
K
κ
: d(u)=κ-1+r+s+1=n-1≥δ,
K
r
: d(u)=r-1+κ≥δ, K
s
: d(u)=s-1+κ≥δ,
v: d(v)=δ.
K
κ
K
r
K
s
K
δ-κ
v
《集合论与图论》第16讲26
定理14((有)(2)(续))
?证明: (有)(2) (分析)
κ(G)=κ: 删除K
κ
.
λ(G)=λ=δ: 删除I
G
(v).
K
κ
K
r
K
s
K
δ-κ
v
《集合论与图论》第16讲27
定理14((有)(3))
?证明: (有)(3) 0 ≤κ≤λ≤δ< ?n/2?
令G’=K
δ+1
∪K
n-δ-1
,设V(K
δ+1
)={u
1
,u
2
,…,u
δ+1
},
V(K
n-δ-1
)={v
1
,v
2
,…,v
n-δ-1
},
给G’增加边(u
i
,v
i
), i=1,2,…,κ,
以及(u
1
,v
i
), i=2,3,…,λ-κ+1, 就得到G.
K
n-δ-1
K
δ+1
1
2
κ
2
λ-κ+1
《集合论与图论》第16讲28
定理14((有)(3)(续))
?证明: (有)(3) (分析): δ(G)=δ:
K
δ+1
: d(u)≥δ, K
n-δ-1
: d(u)≥n-δ-2≥δ.
κ(G)=κ: 删除{ u
i
| i=1,2,…,κ },
λ(G)=λ: 删除{(u
i
,v
i
)|i=1,2,…,κ}∪{(u
1
,v
i
)|
i=2,3,…,λ-κ+1}
K
n-δ-1
K
δ+1
u
1
u
2
u
κ
v
2
v
λ-κ+1
《集合论与图论》第16讲29
定理14((仅有)(1))
?证明: (仅有): (1)如果G是完全图,则
G=K
n
, 所以κ = λ = δ = n-1.
《集合论与图论》第16讲30
定理11
?定理11: G是n阶简单无向连通图,
λ(G)<δ(G),则存在G*以G为生成子图,G*
由完全图K
n1
和K
n2
,以及它们之间的λ(G)
条边组成, λ(G)+2≤n
1
≤?n/2?.
K
n1 K
n2
《集合论与图论》第16讲31
定理11(证明)
?证明: 设E
1
是G的边割集,|E
1
|=λ(G).
设G-E
1
的2个连通分支是G
1
与G
2
,
|V(G
1
)|=n
1
, |V(G
2
)|=n
2
, 不妨设n
1
≤n
2
, 显
然n
1
+n
2
=n, n
1
≤?n/2?.
给G
1
加新边使它成为K
n1
,给G
2
加新
边使它成为K
n2
, 令G*=K
n1
∪E
1
∪K
n2
.
G
1 G
2
E
1
K
n1 K
n2
《集合论与图论》第16讲32
定理11(证明)
?证明(续):
λ(G)<δ(G)≤δ(G*)≤n
1
-1+?λ(G)/n
1
?
?λ(G)<n
1
-1+λ(G)/n
1
? (n
1
-1)(n
1
-λ(G))>0
?λ(G)<n
1
?λ(G) ≤ n
1
-1.
λ(G)=n
1
-1 ?λ(G)=n
1
-1+ ?λ(G)/n
1
?
?λ(G)<δ(G)≤δ(G*)≤λ(G) (矛盾!)
λ(G)<n
1
-1 ?λ(G) ≤ n
1
-2 ?λ(G)+2≤n
1
. #
《集合论与图论》第16讲33
推论
?推论: (1) δ(G)≤δ(G*)≤n
1
-1≤?n/2?-1
(2) G*中有不相邻顶点u,v,使得
d
G*
(u)+d
G*
(v)≤n-2
(3) d(G)≥d(G*)≥3
?证明: (2)u∈G
1
,v∈G
2
,在G中不相邻,则在
G*中仍然不相邻.
(3) d(G)=max d(u,v)
λ(G)≤n
1
-2 #
《集合论与图论》第16讲34
定理12(λ=δ的充分条件)
?定理12: G是6阶以上连通简单无向图.
(1) δ(G)≥?n/2??λ(G)=δ(G)
(2) 若任意一对不相邻顶点u,v都有
d(u)+d(v)≥n-1,
则λ(G)=δ(G).
(3) d(G)≤2 ?λ(G)=δ(G). #
《集合论与图论》第16讲35
定理13
?定理13: G是n阶简单连通无向非完全图,
则2δ(G)-n+2 ≤κ(G).
?证明: 设V
1
是G的点割集, |V
1
|=κ(G), 设G-
V
1
的连通分支是G
1
,G
2
,…,G
s
(s≥2), 设
|V(G
1
)|=n
1
, |V(G
2
)|+…+|V(G
s
)|=n
2
, 则n
1
+
n
2
+κ(G)=n.
G
1
G
2
G
s
《集合论与图论》第16讲36
定理13(续)
?证明(续): δ(G)≤n
1
-1+κ(G)=n
1
+κ(G)-1,
同理δ(G)≤n
2
+κ(G)-1, 所以
2δ(G) ≤ n
1
+κ(G)+n
2
+κ(G)-2 = n+κ(G)-2,
即κ(G) ≥ 2δ(G)-n+2. #
G
1
G
2
G
s
《集合论与图论》第16讲37
定理14((仅有)(2)(3))
?证明: (仅有): (2) δ≥?n/2?时, 定理12,13.
(3) δ<?n/2?时, 定理10. #
《集合论与图论》第16讲38
2-连通的充分必要条件
?定理15: 3阶以上无向简单连通图G是2-
连通图? G中任意两个顶点共圈
?独立(independent)路径: 两条除起点和终
点外无其他公共顶点的路径
?定理15’: 3阶以上无向简单连通图G是2-
连通图? G中任意两个顶点之间有两条
以上独立路径
《集合论与图论》第16讲39
定理15’(证明)
?定理15’: 3阶以上无向简单连通图G是2-
连通图? G中任意两个顶点之间有两条
以上独立路径
?证明: (?) 显然G是连通的,并且删除任何
一个顶点不破坏连通性, 所以κ≥2.
(?) 分情况讨论: 在两个顶点之间有
(1)1条路径(2)2条路径(3)3条路径
(4)4以上条路径
《集合论与图论》第16讲40
定理15’(证明)
?证明(续):(?) (1)一条路径: 不可能
(2)两条路径
(2a)独立: OK
(2b)非独立: 不可能
(3)3条路径: 假设两两非独立,否则同(2a)
《集合论与图论》第16讲41
定理15’(证明)
?证明(续):(?) 3条路径
(3a) 3路径有1个公共交点: 不可能
(3b) 有2个交点: 同(2a) 有2条独立路径
(3c) 有3个以上交点: 产生2条独立路径
(4) 4条以上路径: 同(3). #
《集合论与图论》第16讲42
2-边连通的充分必要条件
?定理16: 3阶以上无向图G是2-边连通图
? G中任意两个顶点共简单回路
?边不交(edge-disjoint)路径: 两条无公共
边(但可能有公共顶点)的路径
?定理16’: 3阶以上无向图G是2-边连通图
? G中任意两个顶点之间有两条以上边
不交路径
《集合论与图论》第16讲43
定理16’(证明)
?定理16’: 3阶以上无向简单连通图G是2-
边连通图? G中任意两个顶点之间有2
条以上边不交路径
?证明: (?) 显然G是连通的,并且删除任何
一条边不破坏连通性, 所以λ≥2.
(?) 分情况讨论: 在两个顶点之间有
(1)1条路径(2)2条路径(3)3条路径
(4)4以上条路径
《集合论与图论》第16讲44
定理16’(证明)
?证明(续):(?) (1)一条路径: 不可能
(2)两条路径
(2a)边不交: OK
(2b)有公共边: 不可能
(3)3条路径: 假设两两有公共边,否则同(2a)
《集合论与图论》第16讲45
定理16’(证明)
?证明(续):(?) 3条路径
(3a) 有1条公共边: 不可能
(3b) 有2条公共边: 同(2a)
(3c) 有3条以上公共边: 产生2条边不交路
径
(4) 4条以上路径: 同(3). #
《集合论与图论》第16讲46
定理16’(其他证明)
?证明: (?) 利用定理15’和“块”. #
?块(block): 极大无割点连通子图
《集合论与图论》第16讲47
k-(边)连通的充分必要条件
?定理: 3阶以上无向图G是k-连通图? G
中任意两个顶点之间有k条以上独立路径
?定理: 3阶以上无向图G是k-边连通图?
G中任意两个顶点之间有k条以上边不交
路径
《集合论与图论》第16讲48
割点的充分必要条件
?定理17: 无向连通图G中顶点v是割点?
可以把V(G)-{v}划分成V
1
与V
2
,使得从V
1
中任意顶点u到V
2
中任意顶点w的路径都
要经过v. #
v
uw
V
1
V
2
《集合论与图论》第16讲49
割点的充分必要条件
?推论: 无向连通图G中顶点v是割点?存
在与v不同的顶点u和w,使得从顶点u到w
的路径都要经过v. #
v
uw
《集合论与图论》第16讲50
桥的充分必要条件
?定理18:无向连通图G中边e是桥? G的
任何圈都不经过e. #
?定理19: 无向连通图G中边e是桥?可以
把V(G)划分成V
1
与V
2
,使得从V
1
中任意顶
点u到V
2
中任意顶点v的路径都要经过e. #
e
uv
V
1
V
2
《集合论与图论》第16讲51
块的充分必要条件
?定理20: G是3阶以上无向简单连通图.则
G是块? G中任意2顶点共圈? G中任
意1顶点与任意1边共圈? G中任意2边
共圈? G中任意2顶点与任意1边,有路径
连接这2顶点并经过这1边? G中任意3
顶点,有路径连接其中2顶点并经过第3点
? G中任意3顶点,有路径连接其中2顶点
并不经过第3点. #
《集合论与图论》第16讲52
比较
?块: 极大无割点连通子图
?2-连通图: κ≥2, 或连通无割点
?2-边连通图: λ≥2, 或连通无桥
?K
2
是块, 但不是2-(边)连通图
?2-连通图? 2-边连通图?块
《集合论与图论》第16讲53
总结
?点割集,边割集,割点,桥, 块
?点连通度,边连通度,Whitney定理
?连通简单图κ,λ,δ之间的关系
?2-连通, 2-边连通的充要条件
?割点, 桥, 块的充要条件
《集合论与图论》第16讲54
作业(#12)
?p214, 习题七, 17,18,22(n≥2,连通),23(图
族)