1
第二章 图的连通性
连通图:任二顶点间有路相连。
例
可见在连通图中,连通的程度也是有高有低。
本章的目的就是定义一种参数来度量连通图连通程度的高低。
§2.1 割边、割点与连通度
一、割点:
定义 2.1.1 设 )(GVv∈ ,如果 )()( GwvGw >− ,则称 v 为 G 的一个割点。(该定义与某些
著作有所不同,主要是在有环边的顶点是否算作割点上有区别)。
例
定理 2.1.1 如果点 v 是图 G 的一个割点,则边集 E(G)可划分为两个非空子集 1E 和 2E ,使得
][ 1EG 和 ][ 2EG 恰好有一个公共顶点 v。
推论 2.1.1 对连通图 G,顶点 v 是 G 的割点当且仅当 vG − 不连通。
以上两个结论的证明留作习题。
定理 2.1.2 设 v 是树 T 的顶点,则 v 是 T 的割点当且仅当 1)( >vd 。
证明:必要性:设 v 是 T 的割点,下面用反证法证明 1)( >vd 。
若 0)( =vd ,则 1KT ≅ ,显然 v不是割点。
若 1)( =vd ,则 vT − 是有 1)( −− vTν 条边的无圈图,故是树。从而 )(1)( TwvTw ==− 。
因此 v不是割点。
以上均与条件矛盾。
充分性:设 1)( >vd ,则 v 至少有两个邻点 u,w。路 uvw 是 T 中一条 ),( wu 路。因 T 是树,
uvw 是 T 中唯一的 ),( wu 路,从而 )(1)( TwvTw =>− 。故 v是割点。证毕。
推论 2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。
证明:设 T 是 G 的生成树,则 T 至少有两个叶子 u,v,由上一定理知,u,v 都不是 T 的割点,
即 1)()( ==− TwuTw 。由于 uT − 是图 uG − 的生成树,故
)(1)()()( GwTwuTwuGw ===−=− ,
2
因此 u 不是 G 的割点。同理 v 也不是 G 的割点。证毕。
二、顶点割集:
定义 2.1.2 对图 G,若 V(G)的子集V ′使得 )()( GwVGw >′− ,则称V ′为图 G 的一个顶点
割集。含有 k 个顶点的顶点割集称为 k-顶点割集。
注:(1)割点是 1-顶点割集。
(2)完全图没有顶点割集。
三、连通度: VVG ′′= ||min{|)(κ 是 G 的顶点割集 }。完全图的连通度定义为
1)( −=νκ νK 。空图的连通度定义为 0。
注:(1)使得 )(|| GV κ=′ 的顶点割集V ′称为 G 的最小顶点割集。
(2)若 kG ≥)(κ ,则称 G 为 k 连通的。
(3)若 G 不连通,则 0)( =Gκ 。
(4)若 G 是平凡图,则 0)( =Gκ 。
(4)所有非平凡连通图都是 1 连通的。
例:
四、割边
定义 2.1.3 设 )(GEe∈ ,如果 )()( GweGw >− ,则称 e 为 G 的一条割边。
定理 2.1.3 边 e 是 G 的割边当且仅当 e 不在 G 的任何圈中。
证明:证其逆否命题:e 不是割边当且仅当 e 含在 G 的某个圈中。
必要性:设 e = xy 不是割边。假定 e 含在 G 的某个连通分支 1G 中,则 eG −1 仍连通。故在
eG −1 中有 ),( yx 路 P,P + e 便构成 1G 中一个含有 e 的圈。
充分性:设 e 含在 G 的某个圈 C 中,而 C 含于某连通分支 1G 中,则 eG −1 仍连通。故
)()( GweGw =− ,这说明 e 不是割边。证毕。
定理 2.1.4 一个连通图是树当且仅当它的每条边都是割边。
证明:连通图 G 是树⇔G 无圈⇔任何边 e 不含在圈中⇔ e 是 G 的割边。证毕。
五、边割集
定义 2.1.4 对图 G,若 E(G)的子集 E ′使得 )()( GwEGw >′− ,则称 E ′为图 G 的一个边割
集。含有 k 条边的边割集称为 k-边割集。
注:(1) 对非平凡图 G,若 E ′是一个边割集,则 EG ′\ 不连通。
(2) 一条割边构成一个 1-边割集。
(3) 设 )(GVS ⊂ , )(GVS ⊂′ , φ≠′SS, ,记号 ],[ SS ′
示一端在 S 中另一端在 S ′中
3
的所有边的集合。对图 G 的每个边割集 E ′,必存在非空的 )(GVS ⊂ ,使得 ],[ SS 是 G 的
一个边割集,其中 SVS \= 。
六、边连通度: φκ ≠⊂∀=′ SGVSSSG ),(||],[min{|)( }。完全图的边连通度定义为
1)( −=′ νκ νK 。空图的边连通度定义为 0。
注:(1)对平凡图或不连通图 G, 0)( =′ Gκ 。
(2)若图 G 是含有割边的连通图,则 1)( =′ Gκ 。
(3)若 kG ≥′ )(κ ,则称 G 为 k-边连通的。
(5)所有非平凡连通图都是 1-边连通的。
(6)使得 )(|| GE κ ′=′ 的边割集 E ′称为 G 的最小边割集。
定理 2.1.5 )()()( GGG δκκ ≤′≤ 。
证明:先证 )()( GG κκ ′≤ 。
若 G 不连通,则 0)()( =′= GG κκ 。
若 G 是完全图,则 1)()( −=′= νκκ GG 。
下设 G 连通但不是完全图。则 G 有边割集含有κ ′( 11 −<′≤ νκ )条边。设这个边
割集为 E ′。对 E ′中每条边,选取一个端点,去掉这些端点(至多κ ′个)后,G 便成为不
连通图,故这些端点构成一个点割集V ′, κ ′≤′ ||V 。因此 )(||)( GVG κκ ′≤′≤ 。
再证 )()( GG δκ ≤′ 。
设 δ=)(vd 。删去与 v 关联的δ 条边后,G 变成不连通图,故这δ 条边构成 G 的一个
边割集。因此 )()( GG δκ ≤′ 。证毕。
§2. 2-连通图的性质-whitney 定理
1. 块(block):无割点的连通图。
2. 图的块:若满足下列三条:
(1) H 是图 G 的子图;(2)H 本身是一个块;(3)H 是具有此性质的极大子图。
则称 H 是图 G 的一个块。
例:
块 含 4 个块的图
注:至少有三个顶点的图是块当且仅当它是 2-连通图。(若只有两个顶点,则有反例,例
如 2K 是个块,但不是 2 连通的。)
4
3.Whitney 定理
定理 2.2.1 (Whitney,1932) 3≥ν 的图 G 是 2-连通图(块)当且仅当 G 中任二顶点共圈。
证明:充分性:设 G 中任二顶点在同一圈上,欲证 G 是 2-连通的。
对 )(GVw∈∀ ,任取 )(, wGVvu −∈ 。由条件,u,v 在 G 中共处于某个圈 C 上。若
Cw∉ ,则在 wG \ 中 u,v 仍在圈 C 上;若 Cw∈ ,则 wG − 中 u,v 在路 wC − 上。总之 u,v
在 wG − 中有路相连。由 u,v 的任意性, wG − 是连通图,故 w 不是 G 的割点。再由 w 的
任意性知,G 无割点,即 G 是 2-连通的。
必要性:设 G 是 2-连通图,欲证任二顶点 u,v 都在同一圈上。
对距离 ),( vud 作归纳法。
1),( =vud 时,因 2≥≥′ κκ ,故边 uv 不是割边, uvG − 仍连通。因此 uvG − 中存
在一条 ),( vu 路 1P 。这表明在 G 中 u,v 都在圈 uvP +1 上。
假定 kvud <),( 时,结论成立。下证 kvud =),( 时结论也成立。
当 kvud =),( 时,设 wvuP L=0 是长为 k 的一条 ),( vu 路,则 1),( −= kwud 。由归
纳法假设,u,w 在同一圈上,故在 u,w 间有两条无公共内部顶点的路 P 和 Q。因 G 是 2 连通
图,故 wG − 仍连通。在 wG − 中存在 ),( vu 路 P′。令 x 是 P′上最后一个与 QP U 的公共
顶点(因 QPu U∈ ,这样的 x 存在)。不妨设 Px∈ ,则 P 上 ),( xu 段+ P′上 ),( vx 段与
wvQ + 是两条内部无公共点的 ),( vu 路。故 u,v 在同一圈上。归纳法完成。证毕。
推论 2.2.1 3≥ν 的图 G 是 2 连通图(块)当且仅当 G 中任二顶点被至少两条内部无公共顶
点的路所连。
推论 2.2.2 若 3≥ν 的图 G 是 2 连通图(块),则 G 的任二边都位于同一圈上。
证明:设 G 是 3≥ν 的 2 连通图,且 )(, 21 GEee ∈ ,在 1e 和 2e 上各添加一个新的顶点 1v 和
2v ,构成一个新图G′。G′仍是 2 连通的。由 Whitney 定理, 1v 和 2v 在G′中位于同一个圈
上。故 1e 和 2e 在 G 中位于同一个圈上。证毕。
注:Whitney 定理可推广到 k 连通图,得到 Menger 型定理:
Menger 定理 1 1+≥ kν 的图 G 是 k 连通图当且仅当 G 中任二顶点至少被 k 条内部无公共
顶点的路所连。
Menger 定理 2 图 G 是 k 边连通图当且仅当 G 中任二顶点至少被 k 条无公共边的路所连。
P
P0u P´
v
Q
x
w
5
§2.3 关于割点、割边和块的其它结论
定理 2.3.1 设 v 是连通图 G 的一个顶点,则下列命题等价:
(1) v 是 G 的割点;
(2) 存在 )(, GVwu ∈ ,使得 vwu ≠, 且 v 在每条 ),( wu 路上;
(3) 存在 }{\)( vGV 的一个划分: }{\)( vGV WU U= , φ=WU I ,使得对 Uu∈∀
和 Ww∈∀ ,v 在每条 ),( wu 路上。
证明:(1)⇒(3)因 v 是割点,故 vG − 至少有两个连通分支 1G 、 2G 。令 )( 1GVU = 而
}){)((\)( 1 vGVGVW U= ,则对 Uu∈∀ 和 Ww∈∀ ,u、w 分别属于 vG − 的不同的连
通分支。可见 G 中所有的 ),( wu 路必经过 v(否则 vG − 中仍有 ),( wu 路,这与 u、w 分别
属于 vG − 的不同的连通分支矛盾)。
(3)⇒(2)显然。
(2)⇒(1)若 v 在每条 ),( wu 路上,则 vG − 中不存在 ),( wu 路,即 vG − 不连通,故
v 是 G 的割点。
证毕。
定理 2.3.2 设 e 是连通图 G 的一条边,则下列命题等价:
(1) 是 G 的割边;
(2) e 不在 G 的任何圈上;
(3) 存在 )(, GVvu ∈ ,使得 e 在每条 ),( vu 路上;
(4) 存在 )(GV 的一个划分: )(GV WU U= , φ=WU I ,使得对 Uu∈∀ 和 Ww∈∀ ,
e 在每条 ),( wu 路上。
证明:(1)⇔(2)定理 2.1.1 已证。(1)⇒(4)⇒(3)⇒(1)的证明与上一定理的
证明类似。
定理 2.3.3 设 G 是 3≥ν 的连通图,则下列命题等价:
(1) G 是 2 连通的(块);
(2) G 的任二顶点共圈;
(3) G 的任一顶点与任一边共圈;
(4) G 的任二边共圈;
(5) 对 )(, GVvu ∈∀ 及 )(GEe∈∀ ,存在 ),( vu 路含有边 e;
(6) 对 )(,, GVwvu ∈∀ ,存在 ),( vu 路含有顶点 w;
(7) 对 )(,, GVwvu ∈∀ ,存在 ),( vu 路不含有顶点 w。
证明:(1)⇒(2)见 Whitney 定理。
(2)⇒(3)设 G 中任二顶点共圈。对 )(GVu∈∀ 及 )(GExye ∈=∀ ,若 ux = 或 uy = ,
6
则结论显然。以下假定 uyx ≠, 。设 C 是含 u 与 x 的圈。若 Cy∈ ,则 C 上含有 u 的 ),( yx
路与边 xy 形成一个圈,它含有 u 及边 e;
若 Cy∉ ,则因 x 不是割点,按定理 2.3.2,存在不含 x 的 ),( yu 路 P,令 w 是 P 上从 y 出发
第一个与 C 公共的顶点,则 C 上 x-u-w 段+P 上 ),( yw 段+xy 构成一个含 u 和 e = xy 的圈。
(3)⇒(4):与(2)⇒(3)类似可证。
(4)⇒(5):设 G 中任二边共圈。对 )(, GVvu ∈∀ 及 )(GEe∈∀ ,如果 uve = ,结论显
然成立;如果 u 或 v 之一是 e 的端点,比如 u 是 e 的端点而 v 的一个零点是 w,则 e 与边
wv 共圈,故显然有 ),( vu 路含有边 e。
下面假定 u 和 v 都不是 e 的端点。
因任二边共圈显然任二点共圈,故由(2)⇒(3)知 u 与 e 共圈,v 也与 e 共圈。设这
二圈分别是 1C 和 2C 。若 2Cu∈ 或 1Cv∈ ,则结论成立;若 2Cu∉ 且 1Cv∉ ,则如下构作
含 e 的 ),( vu 路:从 u 出发沿 1C 到达 1C 与 2C 的第一个公共顶点 w,再从 w 出发沿 2C 含 e
的部分到达 v,即可。
(5)⇒(6):对 )(,, GVwvu ∈∀ ,设与 w 相关联的一条边为 e。由(5),存在 ),( vu 路含
有边 e,于是含有 w。
(6)⇒(7):对 )(,, GVwvu ∈∀ ,存在 ),( wu 路 P 含有顶点 v,则 P 的从 u 到 v 的一段
不含有 w。
xu
y
w
x
u y
u
vw
e
w
C1
e
v
u
C2
7
(7)⇒(1):因为对 )(GVw∈∀ 及 )(, GVvu ∈∀ ,存在 ),( vu 路不含有顶点 w,故 w 不
是割点。由 w 的任意性,G 无割点。从而 G 是块。
证毕。
§2.4 可靠通信网络的
可靠网络设计问题:给定赋权图 G 和正整数 m,求 G 的具有最小权的 m 连通生成子图。
当 1=m 时,就是求最小生成树问题。
当 1>m 时,问题尚未解决。
当 nKG = 且每边权皆为 1 时,问题成为:求 nK 中边数最少的 m-连通生成子图。这一
问题于 1962 年由 Harary 所解决。
令 ),( nmf 表示有 n 个顶点的 m 连通图所能具有的最少边数( nm < )。设 G 是一个具
有这种性质且有 ),( nmf 条边的图。因 ∑
∈
=
)(
)(2
GVv
vdε ,而 δκκ ≤′≤ 。故
),( nmf ⎥⎥
⎤⎢⎢
⎡≥≥
22
mnnδ 。
Harary 找到了具有 n 个顶点、 ⎥⎥
⎤⎢⎢
⎡
2
mn 条边的 m 连通图。这种图记为 nmH , ,构造如下:
记 nmH , 的顶点集为 }1,,2,1,0{ −nL 。
(1) 若 m 为偶数,设 rm 2= 。当且仅当 )(mod20 nrrij ≤+−≤ 时,顶点 i 与 j 连边;
(2) 若 m 为奇数(设 12 += rm ),而 n 是偶数,则先构作 nrH ,2 ,然后对 21
ni ≤≤ 的 i,
在顶点 i 与
2
ni + 间加上一条边;
(3) 若 m 为奇数(设 12 += rm ),且 n 也是奇数,则先构作 nrH ,2 ,然后对 2
11 −<≤ ni
的 i,在顶点 i 与
2
1++ ni 间加上一条边,再在顶点 0 与
2
1−n 、0 与
2
1+n 之间各加
上一边。
H4,8 (m=4, r=2, n=8) H5,8 (m=5, r=2, n=8) H5,9 (m=5, r=2, n=9)
3
2
1
0
5
4
7
6
3
2
1
0
5
4
7
6
5
2
1
0
4
3
7
6
8
8
定理 2.4.1 nmH , 是 m 连通的。
证明:只证 rm 2= 的情况。 12 += rm 的情况类似可证。
我们用反证法来证明 nmH , 中没有少于 rm 2= 个顶点的点割集。
若不然,设V ′是一个点割集且 rV 2|| <′ 。又设 i 与 j 是 VH nr ′−,2 中属于不同连通分支
的两个顶点。考察顶点集
}1,,1,{ −+= jiiS L 和 },1,,1,{ iijjT −+= L 。
这里加法取模 n。因 rV 2|| <′ 且 Vji ′∉, ,不失一般性,设 rVS <′ || I 。则在 VS ′\ 中必
存在一个始于 i 而终于 j,且任二相继项之差 r≤ 的序列。但由 nrH ,2 的构成(1),这样的序
列中相邻项之间存在边。因此这个序列构成了 VH nr ′\,2 中一条 ),( ji 路。这与 i,j 的取法矛
盾。证毕。
推论 2.4.1 ),( nmf = ⎥⎥
⎤⎢⎢
⎡
2
mn 。
证明:容易检查 )( ,nmHε = ⎥⎥
⎤⎢⎢
⎡
2
mn 。由上一定理, nmH , 是 m 连通的,故
≤),( nmf =)( ,nmHε ⎥⎥
⎤⎢⎢
⎡
2
mn 。
另一方面,前已述及 ≥),( nmf ⎥⎥
⎤⎢⎢
⎡
2
mn 。故 ),( nmf = ⎥⎥
⎤⎢⎢
⎡
2
mn 。证毕。
注:因 κκ ′≤ ,故 nmH , 也是 m 边连通的。若 ),( nmg 表示 n 个顶点的 m 边连通图可能的最
少边数,则 ),( nmg = ⎥⎥
⎤⎢⎢
⎡
2
mn 。