图论讲义第2章-连通性

第二章 图的连通性在第一章中已经定义连通图是任二顶点间都有路相连的图。

对于连通图，其连通的程度也有高有低。

例如，下列三个图都是连通图。

对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。

本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。

通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。

§2.1 割点和割边定义2.1.1 设)(G V v ∈，如果)()(G w v G w >−，则称v 为G 的一个割点。

（注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。

例如，下图中u , v 两点是其割点。

定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。

证明留作习题。

推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G −不连通。

定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。

证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。

若0)(=v d ，则1K T ≅，显然v 不是割点。

若1)(=v d ，则v T −是有1)(−−v T ν条边的无圈图，故是树。

从而)(1)(T w v T w ==−。

因此v 不是割点。

以上均与条件矛盾。

充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。

路uvw 是T 中一条),(w u 路。

因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>−。

故v 是割点。

证毕。

推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。

证明：设T 是G 的生成树，则T 至少有两个叶子u ,v ，由上一定理知，u ,v 都不是T 的割点，即1)()(==−T w u T w 。

由于u T −是图u G −的生成树，故)(1)()()(G w T w u T w u G w ===−=−，因此u 不是G 的割点。

同理v 也不是G 的割点。

证毕。

定理2.1.3 设v 是连通图G 的一个顶点，则下列命题等价： （1） v 是G 的割点；（2） 存在)(,G V w u ∈，使得v w u ≠,且v 在每条),(w u 路上；（3） 存在}{\)(v G V 的一个划分：}{\)(v G V W U ∪=，φ=W U ∩，使得对Uu ∈∀和W w ∈∀，v 在每条),(w u 路上。

证明：（1）⇒（3）因v 是割点，故v G −至少有两个连通分支1G 、2G 。

令)(1G V U =而}){)((\)(1v G V G V W ∪=，则对U u ∈∀和W w ∈∀，u 、w 分别属于v G −的不同的连通分支。

可见G 中所有的),(w u 路必经过v （否则v G −中仍有),(w u 路，这与u 、w 分别属于v G −的不同的连通分支矛盾）。

（3）⇒（2）显然。

（2）⇒（1）若v 在每条),(w u 路上，则v G −中不存在),(w u 路，即v G −不连通，故v 是G 的割点。

证毕。

定义2.1.2 设)(G E e ∈，如果)()(G w e G w >−，则称e 为G 的一条割边。

例如下图中，边uv ，边wu 都是其割边。

定理2.1.4 边e 是G 的割边当且仅当e 不在G 的任何圈中。

证明：证其逆否命题：e 不是割边当且仅当e 含在G 的某个圈中。

必要性：设e = xy 不是割边。

假定e 位于G 的某个连通分支1G 中，则e G −1仍连通。

故在e G −1中有),(y x 路P ，P + e 便构成1G 中一个含有e 的圈。

充分性：设e 含在G 的某个圈C 中，而C 含于某连通分支1G 中，则e G −1仍连通。

故)()(G w e G w =−，这说明e 不是割边。

证毕。

定理2.1.5 一个连通图是树当且仅当它的每条边都是割边。

证明：连通图G 是树⇔G 无圈⇔任何边e 不含在圈中⇔任何边e 是G 的割边。

证毕。

定理2.1.6 设e 是连通图G 的一条边，则下列命题等价： （1） e 是G 的割边； （2） e 不在G 的任何圈上；（3） 存在)(,G V v u ∈，使得e 在每条),(v u 路上；（4） 存在)(G V 的一个划分：)(G V W U ∪=，φ=W U ∩，使得对U u ∈∀和W w ∈∀，e 在每条),(w u 路上。

证明：（1）⇔（2）定理2.1.4已证。

（1）⇒（4）⇒（3）⇒（1）的证明与定理2.1.3的证明类似。

§2.2连通度和边连通度定义2.2.1 对图G ，若V(G)的子集V ′使得)()(G w V G w >′−，则称V ′为图G 的一个顶点割集。

含有k 个顶点的顶点割集称为k －顶点割集。

注：（1）割点是1－顶点割集。

（2）完全图没有顶点割集。

定义2.2.2图G 的连通度定义为()min{|||G V V κ′′=是连通图G 的顶点割集}。

特别地，完全图的连通度定义为1)(−=νκνK , 空图的连通度定义为0, 不连通图的连通度定义为0。

注：(1) 若G 是平凡图，则0)(=G κ。

(2) 使得)(||G V κ=′的顶点割集V ′称为G 的最小顶点割集。

(3) 若k G ≥)(κ，则称G 为k 连通的。

(4) 按上述定义，图G 是k 连通的，当且仅当G 的最小点割集至少含k 个顶点，当且仅当G 中没有k −1点割集，当且仅当从G 中任意去掉k −1个顶点后，所剩图仍连通。

(5) 按照k 连通的定义，若图G 是k 连通的，则它也是k −1连通、k −2连通、 (1)通的。

因此，所有非平凡连通图都是1连通的。

定义2.2.3对图G ，若E(G)的子集E ′使得)()(G w E G w >′−，则称E ′为图G 的一个边割集。

含有k 条边的边割集称为k －边割集。

注：(1) 对非平凡图G ，若E ′是一个边割集，则E G ′\不连通。

(2) 一条割边构成一个1－边割集。

(3) 设)(G V S ⊂，)(G V S ⊂′，φ≠′S S ,，记号],[S S ′表示一端在S 中另一端在S ′中的所有边的集合。

对图G 的每个边割集E ′，必存在非空的)(G V S ⊂，使得],[S S 是G 的一个边割集，其中S V S \=。

定义2.2.4图G 的边连通度定义为()min{|||G E E κ′′′=是连通图G 的边割集}。

完全图的边连通度定义为1)(−=′νκνK ，空图的边连通度定义为0，不连通图的边连通度定义为0。

注：(1) 对平凡图G ，0)(=′G κ。

(2) 是含有割边的连通图，则1)(=′G κ。

(3) 使得)(||G E κ′=′的边割集E ′称为G 的最小边割集。

(4) 若k G ≥′)(κ，则称G 为k 边连通的。

(5) 按上述定义，图G 是k 边连通的，当且仅当G 的最小边割集至少含k 条边，当且仅当G 中没有k −1边割集，当且仅当从G 中任意去掉k −1条边后，所剩图仍连通。

(6) 按照k 边连通的定义，若图G 是k 边连通的，则它也是k −1边连通、k −2边连通、…、1边连通的。

因此，所有非平凡连通图都是1边连通的。

例如，下列图中，G 1是连通的且有割点和割边，因此是1连通的和1边连通的；G 2的最小点割集含1个点，最小边割集含2条边，故它是1连通的和2边连通的；G 3的最小点割集和最小边割集分别含2个点和2条边，因此是2连通的和2边连通的；G 4的最小点割集和最小边割集分别含3个点和3条边，因此是3连通的和3边连通的。

定理2.2.1)()()(G G G δκκ≤′≤。

证明：先证)()(G G κκ′≤。

对图的边连通度()G κ′作数学归纳法。

对()G κ′＝1的图G ，若2G K =，则显然()11G κυ′=−=；若2G K ≠，则G 至少含三个点。

设e = uv 是G 的一条割边，则u 或v 必是割点，故()G κ=1。

总之，此时()G κ=()G κ′＝1。

假设对所有k κ′=的图，都有κκ′≤，则对()1G k κ′=+的图G ，设E 是它的一个1k +边割集。

任取边()e uv E G =∈，则E e −是G e −的最小边割集，故()G e k κ′−=。

由归纳假设，()()G e G e κκ′−≤−。

取G e −的最小点割集T ，则||()()T G e G e k κκ′=−≤−=，且{}T u ∪构成G 的最小点割集。

故()|{}|||11()G T u T k G κκ′=≤+≤+=∪。

归纳完成。

再证)()(G G δκ≤′。

设δ=)(v d 。

删去与v 关联的δ条边后，G 变成不连通图，故这δ条边构成G 的一个边割集。

因此)()(G G δκ≤′。

证毕。

下图G 1是一个2,3κκ′==和4δ=的图，G 2是一个1,2κκ′==和3δ=的图。

G 2G3G 1G 2定理2.2.2 对具有υ个顶点ε条边的连通图G ，有2()G εκν⎢⎥≤⎢⎥⎣⎦。

证明：因()2()v V G d v εδυ∈=≥∑，故2εδυ≤，由定理2.2.1，2εκδυ≤≤。

由于κ是整数，因此2εκν⎢⎥≤⎢⎥⎣⎦。

证毕。

定理2.2.3 设G 是一个简单图，k 是一个自然数，若2()2k G υδ+−≥，则G 是k 连通的。

证明：用反证法。

假如G 不是k 连通的，则G 的连通度k κ<，即存在G 的点割集S ，使得||S k <，且G −S 不连通。

因G −S 有|S |υ−个顶点，且至少有两个连通分支，故必有G −S 的某个连通分支G ′含有不超过|S |2υ−个顶点。

注意到G ′中任一个顶点只可能与G ′内的点及S 中的点相邻，因而其在G 中的顶点度|||S |21||22S S υυ−+−≤−+=。

结合||S k <，这意味着(G)δ≤||2222S k υυ+−+−<，与定理条件矛盾。

证毕。

推论2.2.1设G 是一个简单图，若1()2G υδ−≥，则G 是连通的。

定理2.2.4 设G 是一个直径为2的简单图，则(G)(G)κδ′=。

证明：设S 是G 的一个最小边割集，则G −S 有多于一个连通分支，取其中顶点数最少的一个记为G 1，G −S 的其余部分记为G 2。