1 第二章 图的连通性 连通图 :任二顶点间有路相连。 例 可见在连通图中,连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 § 2.1 割边、割点与连通度 一、割点 : 定义 2.1.1 设 )(GVv∈ ,如果 )()( GwvGw >? ,则称 v 为 G 的一个割点。 (该定义与某些 著作有所不同,主要是在有环边的顶点是否算作割点上有区别) 。 例 定理 2.1.1 如果点 v 是图 G 的一个割点,则边集 E(G)可划分为两个非空子集 1 E 和 2 E ,使 得 ][ 1 EG 和 ][ 2 EG 恰好有一个公共顶点 v。 推论 2.1.1 对连通图 G,顶点 v 是 G 的割点当且仅当 vG ? 不连通。 以上两个结论的证明留作习题。 定理 2.1.2 设 v 是树 T 的顶点,则 v 是 T 的割点当且仅当 1)( >vd 。 证明:必要性:设 v 是 T 的割点,下面用反证法证明 1)( >vd 。 若 0)( =vd ,则 1 KT ? ,显然 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 的某个连通分支 1 G 中,则 eG ? 1 仍连通。故在 eG ? 1 中有 ),( yx 路 P, P + e 便构成 1 G 中一个含有 e 的圈。 充分性:设 e 含在 G 的某个圈 C 中,而 C 含于某连通分支 1 G 中,则 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-连通图。 (若只有两个顶点,则有反例,例 如 2 K 是个块,但不是 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 路 1 P 。这表明在 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 ∈ ,在 1 e 和 2 e 上各添加一个新的顶点 1 v 和 2 v ,构成一个新图 G′。 G′仍是 2 连通的。由 Whitney 定理, 1 v 和 2 v 在 G′中位于同一个圈 上。故 1 e 和 2 e 在 G 中位于同一个圈上。证毕。 注: Whitney 定理可推广到 k 连通图,得到 Menger 型定理: Menger 定理 1 1+≥ kν 的图 G 是 k 连通图当且仅当 G 中任二顶点至少被 k 条内部无公共 顶点的路所连。 Menger 定理 2 图 G 是 k 边连通图当且仅当 G 中任二顶点至少被 k 条无公共边的路所连。 P P 0 u P′ v Q x w 5 § 2.3 关于割点、割边和块的其它结论 定理 2.3.1 设 v 是连通图 G 的一个顶点,则下列命题等价: ( 1) v 是 G 的割点; ( 2) 存在 )(, GVwu ∈ ,使得 vwu ≠, 且 v 在每条 ),( wu 路上; ( 3) 存在 }{\)( vGV 的一个划分: }{\)( vGVWU U= , φ=WU I ,使得对 Uu∈? 和 Ww∈? , v 在每条 ),( wu 路上。 证明: ( 1) ?( 3)因 v 是割点,故 vG ? 至少有两个连通分支 1 G 、 2 G 。令 )( 1 GVU = 而 }){)((\)( 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 共圈。设这 二圈分别是 1 C 和 2 C 。若 2 Cu∈ 或 1 Cv∈ ,则结论成立;若 2 Cu? 且 1 Cv? ,则如下构作 含 e 的 ),( vu 路:从 u 出发沿 1 C 到达 1 C 与 2 C 的第一个公共顶点 w,再从 w 出发沿 2 C 含 e 的部分到达 v,即可。 ( 5) ?( 6) :对 )(,, GVwvu ∈? ,设与 w 相关联的一条边为 e。由( 5) ,存在 ),( vu 路含 有边 e,于是含有 w。 ( 6) ?( 7) :对 )(,, GVwvu ∈? ,存在 ),( wu 路 P 含有顶点 v,则 P 的从 u 到 v 的一段 不含有 w。 x u y w x u y u vw e w C 1 e v u C 2 7 ( 7) ?( 1) :因为对 )(GVw∈? 及 )(, GVvu ∈? ,存在 ),( vu 路不含有顶点 w,故 w 不 是割点。由 w 的任意性, G 无割点。从而 G 是块。 证毕。 § 2.4 可靠通信网络的设计 可靠网络设计问题: 给定赋权图 G 和正整数 m,求 G 的具有最小权的 m 连通生成子图。 当 1=m 时,就是求最小生成树问题。 当 1>m 时,问题尚未解决。 当 n KG = 且每边权皆为 1 时,问题成为:求 n K 中边数最少的 m-连通生成子图。这一 问题于 1962 年由 Harary 所解决。 令 ),( nmf 表示有 n 个顶点的 m 连通图所能具有的最少边数( nm < ) 。设 G 是一个具 有这种性质且有 ),( nmf 条边的图。因 ∑ ∈ = )( )(2 GVv vdε ,而 δκκ ≤′≤ 。故 ),( nmf ? ? ? ? ? ? ≥≥ 22 mnnδ 。 Harary 找到了具有 n 个顶点、 ? ? ? ? ? ? 2 mn 条边的 m 连通图。这种图记为 nm H , ,构造如下: 记 nm H , 的顶点集为 }1,,2,1,0{ ?nL 。 ( 1) 若 m 为偶数,设 rm 2= 。当且仅当 )(mod20 nrrij ≤+?≤ 时,顶点 i 与 j 连边; ( 2) 若 m 为奇数(设 12 += rm ) ,而 n 是偶数,则先构作 nr H ,2 ,然后对 2 1 n i ≤≤ 的 i, 在顶点 i 与 2 n i + 间加上一条边; ( 3) 若 m 为奇数 (设 12 += rm ) , 且 n 也是奇数, 则先构作 nr H ,2 , 然后对 2 1 1 ? <≤ n i 的 i,在顶点 i 与 2 1+ + n i 间加上一条边,再在顶点 0 与 2 1?n 、 0 与 2 1+n 之间各加 上一边。 H 4,8 (m=4, r=2, n=8) H 5,8 (m=5, r=2, n=8) H 5,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 nm H , 是 m 连通的。 证明:只证 rm 2= 的情况。 12 += rm 的情况类似可证。 我们用反证法来证明 nm H , 中没有少于 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≤ 的序列。但由 nr H ,2 的构成( 1) ,这样的序 列中相邻项之间存在边。因此这个序列构成了 VH nr ′,2 中一条 ),( ji 路。这与 i,j 的取法矛 盾。证毕。 推论 2.4.1 ),( nmf = ? ? ? ? ? ? 2 mn 。 证明:容易检查 )( ,nm Hε = ? ? ? ? ? ? 2 mn 。由上一定理, nm H , 是 m 连通的,故 ≤),( nmf =)( ,nm Hε ? ? ? ? ? ? 2 mn 。 另一方面,前已述及 ≥),( nmf ? ? ? ? ? ? 2 mn 。故 ),( nmf = ? ? ? ? ? ? 2 mn 。证毕。 注:因 κκ ′≤ ,故 nm H , 也是 m 边连通的。若 ),( nmg 表示 n 个顶点的 m 边连通图可能的最 少边数,则 ),( nmg = ? ? ? ? ? ? 2 mn 。