图论讲义2连通性

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 。