中国社会科学院：图论与网络流理论（一）：图论讲义2连通性

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 。