第二章图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图,其连通的程度 也有高有低。例如,下列三个图都是连通图。对于图G1,删除一条边或一个顶点便可使其 变得不连通;而对于图G2,至少需要删除两条边才能使其不连通,也可以删除一个顶点使 其不连通;对于图G,要破坏其连通性,则至少需要删除三条边或三个顶点 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性 程度。通过研究割边和割点来刻画1连通图的特性:定义连通度和边连通度来度量连通图连 通程度的高低;通过不交路结构和元素的共圈性质来反映图的2连通和k连通性。 §2.1割点和割边 定义211设v∈V(G),如果w(G-v)>w(G),则称v为G的一个割点。 (注:该定义与某些著作中的定义有所不同,主要是在环边的顶点是否算作割点上有区别)。 例如,下图中t,y两点是其割点。 定理211如果点v是简单图G的一个割点,则边集E(G)可划分为两个非空子集E1和E2, 使得G[E1]和G[E2]恰好有一个公共顶点v 证明留作习题。 推论211对连通图G,顶点v是G的割点当且仅当G一v不连通。 定理212设是树T的顶点,则v是T的割点当且仅当d(v)>1 证明:必要性:设v是T的割点,下面用反证法证明d(v)> 若d(v)=0,则T≡K1,显然v不是割点 若d(v)=1,则T-v是有v(T-v)-1条边的无圈图,故是树。从而w(T-v)=1=w(7)。 因此v不是割点 以上均与条件矛盾。 充分性:设d(v)>1,则v至少有两个邻点uw。路uw是T中一条(u,w)路。因T是树, n是T中唯一的(u,w)路,从而w(T-v)>1=w(T)。故v是割点。证毕
1 第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度 也有高有低。例如，下列三个图都是连通图。对于图 G1，删除一条边或一个顶点便可使其 变得不连通；而对于图 G2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使 其不连通；对于图 G3，要破坏其连通性，则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性 程度。通过研究割边和割点来刻画 1 连通图的特性；定义连通度和边连通度来度量连通图连 通程度的高低；通过不交路结构和元素的共圈性质来反映图的 2 连通和 k 连通性。 §2.1 割点和割边 定义 2.1.1 设v ∈V (G) ，如果 w(G − v) > w(G) ，则称 v 为 G 的一个割点。 （注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。 例如，下图中 u, v 两点是其割点。 定理 2.1.1 如果点 v 是简单图 G 的一个割点，则边集 E(G)可划分为两个非空子集 E1和 E2 ， 使得 [ ] G E1 和 [ ] G E2 恰好有一个公共顶点 v。 证明留作习题。 推论 2.1.1 对连通图 G，顶点 v 是 G 的割点当且仅当G − v 不连通。 定理 2.1.2 设 v 是树 T 的顶点，则 v 是 T 的割点当且仅当d(v) > 1。 证明：必要性：设 v 是 T 的割点，下面用反证法证明d(v) > 1。 若d(v) = 0 ，则T ≅ K1，显然v 不是割点。 若d(v) = 1，则T − v 是有ν (T − v) −1条边的无圈图，故是树。从而 w(T − v) = 1 = w(T ) 。 因此v 不是割点。 以上均与条件矛盾。 充分性：设d(v) > 1，则 v 至少有两个邻点 u,w。路 uvw 是 T 中一条(u,w) 路。因 T 是树， uvw 是 T 中唯一的(u,w) 路，从而 w(T − v) > 1 = w(T ) 。故v 是割点。证毕。 G1 G2 G3 u v
推论212每个非平凡无环连通图至少有两个顶点不是割点 证明:设T是G的生成树,则T至少有两个叶子u,v,由上一定理知,uv都不是T的割点, 即v(T-a)=w(T)=1。由于T-是图G-u的生成树,故 (G-)=v(7-)=w(T)=1=w(G), 因此u不是G的割点。同理v也不是G的割点。证毕。 定理213设γ是连通图G的一个顶点,则下列命题等价 (1)v是G的割点; (2)存在u,∈V(G),使得u,w≠v且v在每条(,w)路上 (3)存在V(G){v}的一个划分:(G){v}=U∪W,U∩W=φ,使得对vu∈U 和vw∈W,v在每条(u,w)路上。 证明:(1)→(3)因v是割点,故G-ν至少有两个连通分支G、G2。令U=F(G1)而 W=(G)\((G1)U{v}),则对Vu∈U和w∈W,、w分别属于G-v的不同的连 通分支。可见G中所有的(u,)路必经过v(否则G-v中仍有(u,)路,这与a、w分别 属于G-v的不同的连通分支矛盾)。 (3)→(2)显然。 (2)→(1)若v在每条(,w)路上,则G-v中不存在(l,w)路,即G-v不连通,故 v是G的割点。 证毕 定义212设e∈E(G),如果w(G-e)>w(G),则称e为G的一条割边 例如下图中,边w,边wu都是其割边 定理2.14边e是G的割边当且仅当e不在G的任何圈中。 证明:证其逆否命题:e不是割边当且仅当e含在G的某个圈中。 必要性:设e=x不是割边。假定e位于G的某个连通分支G1中,则G1-e仍连通。故在 G1-e中有(x,y)路P,P+e便构成G1中一个含有e的圈。 充分性:设e含在G的某个圈C中,而C含于某连通分支G1中,则G1-e仍连通。故 v(G-e)=w(G),这说明e不是割边。证毕。 定理215一个连通图是树当且仅当它的每条边都是割边。 证明:连通图G是树G无圈◇任何边e不含在圈中分任何边e是G的割边。证毕
2 推论 2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。 证明：设 T 是 G 的生成树，则 T 至少有两个叶子 u,v，由上一定理知，u,v 都不是 T 的割点， 即 w(T − u) = w(T ) = 1。由于T − u 是图G − u 的生成树，故 w(G − u) = w(T − u) = w(T ) = 1 = w(G) ， 因此 u 不是 G 的割点。同理 v 也不是 G 的割点。证毕。 定理 2.1.3 设 v 是连通图 G 的一个顶点，则下列命题等价： （1） v 是 G 的割点； （2） 存在u,w∈V(G) ，使得u,w ≠ v 且 v 在每条(u,w) 路上； （3） 存在V (G) \ {v}的一个划分：V (G) \ {v} = U ∪W ，U ∩W = φ ，使得对∀u ∈U 和∀w ∈W ，v 在每条(u,w) 路上。 证明：（1）⇒（3）因 v 是割点，故G − v 至少有两个连通分支G1 、G2 。令 ( ) U = V G1 而 ( ) \ ( ( ) { }) 1 W = V G V G ∪ v ，则对∀u ∈U 和∀w ∈W ，u、w 分别属于G − v 的不同的连 通分支。可见 G 中所有的(u,w) 路必经过 v（否则G − v 中仍有(u,w) 路，这与 u、w 分别 属于G − v 的不同的连通分支矛盾）。 （3）⇒（2）显然。 （2）⇒（1）若 v 在每条(u,w) 路上，则G − v 中不存在(u,w) 路，即G − v 不连通，故 v 是 G 的割点。 证毕。 定义 2.1.2 设e ∈ E(G)，如果 w(G − e) > w(G) ，则称 e 为 G 的一条割边。 例如下图中，边 uv，边 wu 都是其割边。 定理 2.1.4 边 e 是 G 的割边当且仅当 e 不在 G 的任何圈中。 证明：证其逆否命题：e 不是割边当且仅当 e 含在 G 的某个圈中。 必要性：设 e = xy 不是割边。假定 e 位于 G 的某个连通分支G1 中，则G − e 1 仍连通。故在 G − e 1 中有(x, y)路 P，P + e 便构成G1 中一个含有 e 的圈。 充分性：设 e 含在 G 的某个圈 C 中，而 C 含于某连通分支G1 中，则G − e 1 仍连通。故 w(G − e) = w(G) ，这说明 e 不是割边。证毕。 定理 2.1.5 一个连通图是树当且仅当它的每条边都是割边。 证明：连通图 G 是树⇔G 无圈⇔任何边 e 不含在圈中⇔任何边 e 是 G 的割边。证毕。 u v w
定理2.1.6设e是连通图G的一条边,则下列命题等价 (1)e是G的割边 (2)e不在G的任何圈上 (3)存在u,v∈V(G),使得e在每条(,v)路上 (4)存在V(G)的一个划分:(G)=UUW,U∩W=p,使得对∈U和vw∈W e在每条(ln,w)路上 证明:(1)◇(2)定理2.14已证。(1)→(4)→(3)→(1)的证明与定理2.13的 证明类似。 §22连通度和边连通度 定义22.1对图G,若V(G)的子集V使得w(G-)>w(G),则称V为图G的一个顶点 割集。含有k个顶点的顶点割集称为k一顶点割集 注:(1)割点是1一顶点割集。 (2)完全图没有顶点割集 定义2.2图G的连通度定义为x(G)=min{'‖v是连通图G的顶点割集}。特别地, 完全图的连通度定义为x(K,)=v-1,空图的连通度定义为0,不连通图的连通度定义为0 注:(1)若G是平凡图,则K(G)=0。 (2)使得|V"F=x(G)的顶点割集V称为G的最小顶点割集。 (3)若k(G)≥k,则称G为k连通的。 (4)按上述定义,图G是k连通的,当且仅当G的最小点割集至少含k个顶点,当且仅 当G中没有k-1点割集,当且仅当从G中任意去掉k-1个顶点后,所剩图仍连通 (5)按照k连通的定义,若图G是k连通的,则它也是k-1连通、k-2连通、…、1连 通的。因此,所有非平凡连通图都是1连通的 定义22.3对图G,若E(G)的子集E使得v(G-E)>w(G),则称E为图G的一个边割 集。含有k条边的边割集称为k-边割集 注:(1)对非平凡图G,若E’是一个边割集,则G\E’不连通 (2)一条割边构成一个1—边割集 (3)设ScF(G),S'cV(G),S,S'≠φ,记号[S,S表示一端在S中另一端在S"中 的所有边的集合。对图G的每个边割集E’,必存在非空的ScV(G),使得[S,S]是G的 个边割集,其中S=\S 定义224图G的边连通度定义为k(G)=min{E"‖E是连通图G的边割集}。完全图的 边连通度定义为x‘(K)=V-1,空图的边连通度定义为0,不连通图的边连通度定义为0 注:(1)对平凡图G,K(G)=0 (2)是含有割边的连通图,则k'(G)=1
3 定理 2.1.6 设 e 是连通图 G 的一条边，则下列命题等价： （1） e 是 G 的割边； （2） e 不在 G 的任何圈上； （3） 存在u, v ∈V (G) ，使得 e 在每条(u, v)路上； （4） 存在V (G) 的一个划分：V(G) = U ∪W ，U ∩W = φ ，使得对∀u ∈U 和∀w ∈W ， e 在每条(u,w) 路上。 证明：（1）⇔（2）定理 2.1.4 已证。（1）⇒（4）⇒（3）⇒（1）的证明与定理 2.1.3 的 证明类似。 §2.2 连通度和边连通度 定义 2.2.1 对图 G，若 V(G)的子集V ′使得 w(G −V ′) > w(G) ，则称V ′为图 G 的一个顶点 割集。含有 k 个顶点的顶点割集称为 k－顶点割集。 注：（1）割点是 1－顶点割集。 （2）完全图没有顶点割集。 定义 2.2.2 图 G 的连通度定义为κ ( ) min{| || G VV = ′ ′是连通图 G 的顶点割集}。特别地， 完全图的连通度定义为κ(Kν ) =ν −1, 空图的连通度定义为 0, 不连通图的连通度定义为 0。 注：(1) 若 G 是平凡图，则κ (G) = 0。 (2) 使得|V ′ |= κ (G) 的顶点割集V ′称为 G 的最小顶点割集。 (3) 若κ (G) ≥ k ，则称 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′使得 w(G − E′) > w(G) ，则称 E′为图 G 的一个边割 集。含有 k 条边的边割集称为 k－边割集。 注：(1) 对非平凡图 G，若 E′是一个边割集，则G \ E′ 不连通。 (2) 一条割边构成一个 1－边割集。 (3) 设 S ⊂ V(G) ，S′ ⊂ V(G) ，S, S′ ≠ φ ，记号[S, S′] 表示一端在 S 中另一端在 S′ 中 的所有边的集合。对图 G 的每个边割集 E′，必存在非空的 S ⊂ V (G) ，使得[S, S ] 是 G 的 一个边割集，其中 S = V \ S 。 定义 2.2.4 图 G 的边连通度定义为κ′( ) min{| || G EE = ′ ′是连通图 G 的边割集}。完全图的 边连通度定义为κ′(Kν ) =ν −1，空图的边连通度定义为 0，不连通图的边连通度定义为 0。 注：(1) 对平凡图 G，κ′(G) = 0。 (2) 是含有割边的连通图，则κ′(G) = 1
(3)使得|E"Fκ(G)的边割集E’称为G的最小边割集 (4)若K(G)≥k,则称G为k边连通的。 (5)按上述定义,图G是k边连通的,当且仅当G的最小边割集至少含k条边,当且仅 当G中没有k-1边割集,当且仅当从G中任意去掉k-1条边后,所剩图仍连通 (6)按照k边连通的定义,若图G是k边连通的,则它也是k-1边连通、k-2边连通、…、 1边连通的。因此,所有非平凡连通图都是1边连通的。 例如,下列图中,G1是连通的且有割点和割边,因此是1连通的和1边连通的;G2的 最小点割集含1个点,最小边割集含2条边,故它是1连通的和2边连通的;G3的最小点 割集和最小边割集分别含2个点和2条边,因此是2连通的和2边连通的;G4的最小点割 集和最小边割集分别含3个点和3条边,因此是3连通的和3边连通的。 !!:! G 定理22.1K(G)≤k'(G)≤δ(G)。 证明:先证k(G)≤k'(G) 对图的边连通度(G)作数学归纳法。 对(G)=1的图G,若G=K2,则显然'(G)=b-1=1;若G≠K2,则G至少 含三个点。设e=是G的一条割边,则a或v必是割点,故K(G)=1。 总之,此时x(G)=k(G) 假设对所有x=k的图,都有k'≤K,则对x'(G)=k+1的图G,设E是它的一个k+1 边割集。任取边e=∈E(G),则E-e是G-e的最小边割集,故k(G-e)=k。由归 纳假设,k(G-e)≤k(G-e)。取G-e的最小点割集T,则 T=K(G-e)≤k(G-e)=k 且TU{l构成G的最小点割集。故k(G)=TU{}图T+1≤k+1=k'(G)。归纳完成。 再证k(G)≤(G)。 设d(v)=。删去与v关联的δ条边后,G变成不连通图,故这δ条边构成G的一个 边割集。因此k(G)≤o(G)。证毕 下图G1是一个=2,K’=3和δ=4的图,G2是一个K=1,K’=2和δ=3的图。 区
4 (3) 使得| E′ |= κ ′(G) 的边割集 E′称为 G 的最小边割集。 (4) 若κ′(G) ≥ k ，则称 G 为 k 边连通的。 (5) 按上述定义，图 G 是 k 边连通的，当且仅当 G 的最小边割集至少含 k 条边，当且仅 当 G 中没有 k−1 边割集，当且仅当从 G 中任意去掉 k−1 条边后，所剩图仍连通。 (6) 按照 k 边连通的定义，若图 G 是 k 边连通的，则它也是 k−1 边连通、k−2 边连通、…、 1 边连通的。因此，所有非平凡连通图都是 1 边连通的。 例如，下列图中，G1 是连通的且有割点和割边，因此是 1 连通的和 1 边连通的；G2的 最小点割集含 1 个点，最小边割集含 2 条边，故它是 1 连通的和 2 边连通的；G3的最小点 割集和最小边割集分别含 2 个点和 2 条边，因此是 2 连通的和 2 边连通的；G4的最小点割 集和最小边割集分别含 3 个点和 3 条边，因此是 3 连通的和 3 边连通的。 定理 2.2.1 κ (G) ≤ κ ′(G) ≤ δ (G) 。 证明：先证κ (G) ≤ κ′(G) 。 对图的边连通度κ ′( ) G 作数学归纳法。 对κ′( ) G ＝1 的图 G，若G K = 2 ，则显然κ′() 11 G = υ − = ；若G K ≠ 2 ，则 G 至少 含三个点。设 e = uv 是 G 的一条割边，则 u 或 v 必是割点，故κ ( ) G =1。 总之，此时κ ( ) G =κ′( ) G ＝1。 假设对所有κ ′ = k 的图，都有κ κ ′ ≤ ，则对κ ′() 1 G k = + 的图G，设E是它的一个k + 1 边割集。任取边e uv E G = ∈ ( ) ，则 E e − 是G e − 的最小边割集，故κ′( ) Ge k − = 。由归 纳假设，κ κ ( )( ) Ge Ge −≤ − ′ 。取G e − 的最小点割集 T，则 || ( ) ( ) T Ge Ge k = −≤ −= κ κ′ ， 且T u ∪{ }构成 G 的最小点割集。故κ ( ) | { }| | | 1 1 ( ) GTuT k G = ∪ ≤ +≤ + = κ′ 。归纳完成。 再证κ′(G) ≤ δ (G) 。 设d(v) = δ 。删去与 v 关联的δ 条边后，G 变成不连通图，故这δ 条边构成 G 的一个 边割集。因此κ′(G) ≤ δ (G) 。证毕。 下图 G1 是一个κ = = 2, 3 κ′ 和δ = 4 的图，G2 是一个κ = 1, 2 κ′ = 和δ = 3的图。 G1 G2 G3 G4 G1 G2
定理2.22对具有D个顶点E条边的连通图9,有(G)≤ 证明:因2E=∑d()≥b,故δ≤,由定理221,k≤δ≤2。由于K是整数, lE/(G) 因此K≤ 证毕 定理23设G是一个简单图,k是一个自然数,若(G)≥+k-2 ,则G是k连通的。 证明:用反证法。假如G不是k连通的,则G的连通度K<k,即存在G的点割集S,使 得|Skk,且G-S不连通。因G-S有U-|S|个顶点,且至少有两个连通分支,故必有G-S 的某个连通分支G含有不超过/S 个顶点。注意到G’中任一个顶点只可能与G内的点 2 及S中的点相邻,因而其在G中的顶点度=15|-1+1S=2+5S12.结合|Skk 这意味着6(G)≤+1S-2<”+k-2,与定理条件矛盾。证毕 推论221设G是一个简单图,若(G)≥,则G是连通的 定理224设G是一个直径为2的简单图,则x(G)=o(G)。 证明:设S是G的一个最小边割集,则G-S有多于一个连通分支,取其中顶点数最少的一 个记为G1,GS的其余部分记为G2 如果G1中存在顶点a,它在G中不与G2的顶点相邻,则对,由d(l,v)=2知,在G 中v有属于G1的邻点。由此可知,在G中来看,要么G1中每个点都在G2中有邻点,要么 G2中每个点都在G1中有邻点。在前一种情况下,|SpU(G1),在后一种情况下, SEU(G2)。总之,K'=Smin{b(G1,D(G2)}=D(G1)。 (1) 对va∈G1,用d1(u)和d1()分别表示在G中u与G1和G2连的边数。则 (G)≤d0(u)=d1(l)+d2(u)≤D(G1)-1+d2(l)。 根据定理22.1, K'≤(G)≤U(G1)-1+d2(un) 结合(1)式可得d2()≥1。任取l0∈V(G1),由于 k'=SF∑d2()=∑d2(l)+d2(l)≥U(G)-1+d2(a), 结合(2)式得
5 定理 2.2.2 对具有υ 个顶点ε 条边的连通图 G，有 2 ( ) G ε κ ν ⎢ ⎥ ≤ ⎢ ⎥ ⎣ ⎦ 。 证明：因 ( ) 2 () vVG ε d v δυ ∈ = ≥ ∑ ，故 2ε δ υ ≤ ，由定理 2.2.1， 2ε κ δ υ ≤ ≤ 。由于κ 是整数， 因此 2ε κ ν ⎢ ⎥ ≤ ⎢ ⎥ ⎣ ⎦ 。证毕。 定理 2.2.3 设 G 是一个简单图，k 是一个自然数，若 2 ( ) 2 k 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| 2 1| | 2 2 S S υ− υ+ − ≤ −+ = 。结合| | S k < ， 这意味着δ (G) ≤ | |2 2 2 2 υ+ S k − +− υ < ，与定理条件矛盾。证毕。 推论 2.2.1 设 G 是一个简单图，若 1 ( ) 2 G υ δ − ≥ ，则 G 是连通的。 定理 2.2.4 设 G 是一个直径为 2 的简单图，则κ′(G) (G) = δ 。 证明：设 S 是 G 的一个最小边割集，则 G−S 有多于一个连通分支，取其中顶点数最少的一 个记为 G1，G−S 的其余部分记为 G2。 如果 G1 中存在顶点 u，它在 G 中不与 G2 的顶点相邻，则对，由 (,) 2 G d uv = 知，在 G 中 v 有属于 G1 的邻点。由此可知，在 G 中来看，要么 G1 中每个点都在 G2 中有邻点，要么 G2 中每个点都在 G1 中有邻点。在前一种情况下， 1 | S | (G ) ≥ υ ，在后一种情况下， 2 | S | (G ) ≥ υ 。总之， 12 1 κ υυ υ ′ =≥ = | S | min{ (G ), (G )} (G ) 。 （1） 对 1 ∀ ∈u G ，用 1 d u( ) 和 1 d u( ) 分别表示在 G 中 u 与 G1和 G2 连的边数。则 12 1 2 ( ) () () () ( ) 1 () G d u du du G du G δ ≤ = + ≤ −+ υ 。 根据定理 2.2.1， κ δ ′ ≤ ≤ (G) 1 2 υ( ) 1 () G du − + 。 （2） 结合（1）式可得 2 d u() 1 ≥ 。 任取 0 1 u VG ∈ ( ) ，由于 1 10 2 2 20 1 20 | | () () ( ) ( ) 1 ( ) uG uG u κ υ S du du du G du ∈ ∈− ′ = = = + ≥ −+ ∑ ∑ ， 结合（2）式得
U(G1)-1+d2(l)≤k’≤d(G)≤U(G1)-1+d2(l) 可见x'=δ(G)。证毕。 推论222设非空简单图G中任二不相邻顶点和v都满足d(a)+d(v)≥b-1,则 k(G)=o(G)。 证明:若G中任意两点都相邻,则G是完全图,k(G)=U-1=6(G),结论成立。若G 中有不相邻顶点,则 diam G≥2但由于任二不相邻顶点和v都满足d(a)+d(v)≥b-1, 即任二不相邻顶点u和y都有公共的邻点。因此又有 diam G≤2。从而 diam C=2。由定 理224便得'(G)=6(G)。证毕 按照推论222,下面的结论是显然的。 推论223设G是一个简单图,若O(G)≥ 2,则x'(G)=(G)。 虽然直径为2的图能使得边连通度达到上界,但其点连通度仍然可能很小。例如下图的 直径为2,其连通度只有1。 §232连通图的性质 定义231无割点的连通图称为一个块bock)设G是一个图,H是G的一个子图,若H 本身是一个块且它是G中具有此性质的极大子图,则称H是图G的一个块 下面是块及图的块的例子。 块 含4个块的图 注:至少有三个顶点的图是块当且仅当它是2一连通图。(若只有两个顶点,则有反例,例 如K2是个块,但不是2连通的。) 关于2连通图(块),有下列重要结论 定理23.1( Whitney,1932)v≥3的图G是2一连通图(块)当且仅当G中任二顶点共圈。 证明:充分性:设G中任二顶点在同一圈上,欲证G是2一连通的。 对vw∈(G),任取u,v∈V(G-w)。由条件,u,v在G中共处于某个圈C上。若 v∈C,则在G\w中u,v仍在圈C上:若w∈C,则G-w中t,v在路C-w上。总之 u,y在G-w中有路相连。由,v的任意性,G-w是连通图,故w不是G的割点。再由w 的任意性知,G无割点,即G是2一连通的
6 1 20 υ( )1 () G du −+ ≤ κ′ ≤ δ (G) ≤ 1 20 υ( )1 () G du − + 可见κ δ ′ = (G) 。证毕。 推论 2.2.2 设非空简单图 G 中任二不相邻顶点 u 和 v 都满足 du dv () () 1 + ≥ − υ ，则 κ δ ′(G) (G) = 。 证明：若 G 中任意两点都相邻，则 G 是完全图，κ′(G) 1 (G) = υ δ − = ，结论成立。若 G 中有不相邻顶点，则diam 2 G ≥ 。但由于任二不相邻顶点u和v都满足 du dv () () 1 + ≥− υ ， 即任二不相邻顶点 u 和 v 都有公共的邻点。因此又有diam 2 G ≤ 。从而diam 2 G = 。由定 理 2.2.4 便得κ δ ′(G) (G) = 。证毕。 按照推论 2.2.2，下面的结论是显然的。 推论 2.2.3 设 G 是一个简单图，若 1 ( ) 2 G υ δ − ≥ ，则κ ′(G) (G) = δ 。 虽然直径为 2 的图能使得边连通度达到上界，但其点连通度仍然可能很小。例如下图的 直径为 2，其连通度只有 1。 §2.3 2-连通图的性质 定义 2.3.1 无割点的连通图称为一个块(block)。设 G 是一个图，H 是 G 的一个子图，若 H 本身是一个块且它是 G 中具有此性质的极大子图，则称 H 是图 G 的一个块。 下面是块及图的块的例子。 块 含 4 个块的图 注：至少有三个顶点的图是块当且仅当它是 2－连通图。（若只有两个顶点，则有反例，例 如 K2 是个块，但不是 2 连通的。） 关于 2 连通图（块），有下列重要结论。 定理 2.3.1 (Whitney,1932) ν ≥ 3的图 G 是 2－连通图（块）当且仅当 G 中任二顶点共圈。 证明：充分性：设 G 中任二顶点在同一圈上，欲证 G 是 2－连通的。 对∀w∈V(G) ，任取u, v ∈V(G − w) 。由条件，u, v 在 G 中共处于某个圈 C 上。若 w ∉C ，则在G \ w 中 u, v 仍在圈 C 上；若 w ∈C ，则G − w中 u, v 在路C − w 上。总之 u, v 在G − w中有路相连。由 u, v 的任意性，G − w是连通图，故 w 不是 G 的割点。再由 w 的任意性知，G 无割点，即 G 是 2－连通的
必要性:设G是2一连通图,欲证任二顶点L,v都在同一圈上。 对距离d(l,v)作归纳法。 d(l,)=1时,因x≥K≥2,故G中无割边,G-仍连通。因此G-中存在 条(u,v)路P。这表明在G中a,v都在圈P+上。 假定d(l,v)<k时,结论成立。下证d(u,v)=k时结论也成立。 当d(l,v)=k时,设f=l…wv是长为k的一条(u,v)路,则d(l,)=k-1。由归 纳法假设,l,w在同一圈上,故在t,w间有两条无公共内部顶点的路P和Q。因G是2连 通图,故G-仍连通。在G-中存在(,v)路P。令x是P上最后一个与PUQ的公 共顶点(因l∈P∪Q,这样的x存在)。不妨设x∈P,则P上(,x)段+P'上(x,v)段 与Q+w是两条内部无公共点的(,v)路。故,v在同一圈上。归纳法完成。证毕 推论23.1v≥3的图G是2连通图(块)当且仅当G中任二顶点被至少两条内部无公共顶 点的路所连 推论23.,2若v≥3的图G是2连通图(块),则G的任二边都位于同一圈上。 证明:设G是v≥3的2连通图,且e1e2∈E(G),在e1和e2上各添加一个新的顶点v1和 V2,构成一个新图G’。G’仍是2连通的。由 Whitney定理,v1和v2在G中位于同一个圈 上。故e1和e2在G中位于同一个圈上。证毕。 关于块的部分等价命题总结在下一个定理中。 定理23.2设G是v≥3的连通图,则下列命题等价 (1)G是2连通的(块) (2)G的任二顶点共圈 (3)G的任一顶点与任一边共圈 (4)G的任二边共圈; (5)对vu,v∈(G)及ve∈E(G),存在(u,v)路含有边e; (6)对vu,v,w∈F(G),存在(l,v)路含有顶点w (7)对vu,v,w∈F(G),存在(l,v)路不含有顶点v。 证明:(1)→(2)见 Whitney定理 (2)→(3)设G中任二顶点共圈。对veV(G)及ve=xy∈E(G),若x=或y=l, 则结论显然。以下假定x,y≠l。设C是含u与x的圈。若y∈C,则C上含有u的(x,y)
7 必要性：设 G 是 2－连通图，欲证任二顶点 u, v 都在同一圈上。 对距离d(u, v) 作归纳法。 d(u, v) = 1时，因κ ′ ≥ κ ≥ 2 ，故 G 中无割边，G − uv 仍连通。因此G − uv 中存在 一条(u, v) 路 P1 。这表明在 G 中 u, v 都在圈 P + uv 1 上。 假定d(u, v) < k 时，结论成立。下证d(u, v) = k 时结论也成立。 当d(u, v) = k 时，设 P = u"wv 0 是长为 k 的一条(u, v) 路，则d(u,w) = k −1。由归 纳法假设，u, w 在同一圈上，故在 u, w 间有两条无公共内部顶点的路 P 和 Q。因 G 是 2 连 通图，故G − w仍连通。在G − w中存在(u, v) 路 P′ 。令 x 是 P′ 上最后一个与 P ∪ Q 的公 共顶点（因u ∈ P ∪ Q ，这样的 x 存在）。不妨设 x ∈ P ，则 P 上(u, x)段＋ P′ 上(x, v) 段 与Q + wv 是两条内部无公共点的(u, v) 路。故 u, v 在同一圈上。归纳法完成。证毕。 推论 2.3.1 ν ≥ 3的图 G 是 2 连通图（块）当且仅当 G 中任二顶点被至少两条内部无公共顶 点的路所连。 推论 2.3.2 若ν ≥ 3的图 G 是 2 连通图（块），则 G 的任二边都位于同一圈上。 证明：设 G 是ν ≥ 3的 2 连通图，且 , ( ) e1 e2 ∈ E G ，在 1 e 和 2 e 上各添加一个新的顶点 1 v 和 2 v ，构成一个新图G′。G′仍是 2 连通的。由 Whitney 定理， 1 v 和 2 v 在G′中位于同一个圈 上。故 1 e 和 2 e 在 G 中位于同一个圈上。证毕。 关于块的部分等价命题总结在下一个定理中。 定理 2.3.2 设 G 是ν ≥ 3的连通图，则下列命题等价： （1） G 是 2 连通的（块）； （2） G 的任二顶点共圈； （3） G 的任一顶点与任一边共圈； （4） G 的任二边共圈； （5） 对∀u, v ∈V(G) 及∀e ∈ E(G) ，存在(u, v)路含有边 e； （6） 对∀u, v,w∈V(G) ，存在(u, v)路含有顶点 w; （7） 对∀u, v,w∈V(G) ，存在(u, v)路不含有顶点 w。 证明：（1）⇒（2）见 Whitney 定理。 （2）⇒（3）设 G 中任二顶点共圈。对∀u ∈V(G) 及∀e = xy ∈ E(G)，若 x = u 或 y = u ， 则结论显然。以下假定 x, y ≠ u 。设 C 是含 u 与 x 的圈。若 y ∈C ，则 C 上含有 u 的(x, y) P P0 u P´ v Q x w
路与边xy形成一个圈,它含有u及边 设ygC。由 Whitney定理,x不是割点。故存在不含x的(u,y)路P,令w是P上从y 出发第一个与C公共的顶点,则C上x段+P上(,y)段+xy构成一个含u和e=x 的圈 (3)→(4):与(2)→(3)类似可证。 (4)→(5):设G中任二边共圈。对V,v∈V(G)及ve∈E(G),如果e=u,结论显 然成立;如果或v之一是e的端点,比如u是e的端点而v的一个邻点是w,则e与边 wv共圈,故显然有(u,v)路含有边e 下面假定u和v都不是e的端点。 因任二边共圈显然任二点共圈,故由(2)→(3)知u与e共圈,v也与e共圈。设这 圈分别是C1和C2。若l∈C2或v∈C1,则结论成立;若u∈C2且v∈C1,则如下构作 含e的(u,v)路:从u出发沿C1到达C1与C2的第一个公共顶点w,再从w出发沿C2含e 的部分到达v,即可 (5)→(6):对Vu,v,w∈I(G),设与w相关联的一条边为e。由(5),存在(l,v)路含 有边e,于是含有w
8 路与边 x y 形成一个圈，它含有 u 及边 e； 设 y ∉C 。由 Whitney 定理, x 不是割点。故存在不含 x 的(u, y) 路 P，令 w 是 P 上从 y 出发第一个与 C 公共的顶点，则 C 上 x-u-w 段＋P 上(w, y) 段＋xy 构成一个含 u 和 e = xy 的圈。 （3）⇒（4）：与（2）⇒（3）类似可证。 （4）⇒（5）：设 G 中任二边共圈。对∀u, v ∈V(G) 及∀e∈ E(G) ，如果e = uv ，结论显 然成立；如果 u 或 v 之一是 e 的端点，比如 u 是 e 的端点而 v 的一个邻点是 w，则 e 与边 wv 共圈，故显然有(u, v)路含有边 e。 下面假定 u 和 v 都不是 e 的端点。 因任二边共圈显然任二点共圈，故由（2）⇒（3）知 u 与 e 共圈，v 也与 e 共圈。设这 二圈分别是C1和C2 。若 C2 u ∈ 或 C1 v ∈ ，则结论成立；若 C2 u ∉ 且 C1 v ∉ ，则如下构作 含 e 的(u, v)路：从 u 出发沿C1到达C1与C2的第一个公共顶点 w，再从 w 出发沿C2含 e 的部分到达 v，即可。 （5）⇒（6）：对∀u, v,w∈V(G) ，设与 w 相关联的一条边为 e。由（5），存在(u, v)路含 有边 e，于是含有 w。 x u y u w v e w C1 e v u C2 w x u y
(6)→(7):对V,v,w∈V(G),存在(u,)路P含有顶点v,则P的从u到v的一段 不含有w (7)→(1):因为对vw∈(G)及va,v∈F(G),存在(u,v)路不含有顶点w,故w不 是割点。由w的任意性,G无割点。从而G是块。 证毕 §24 Menger定理 上节的 Whitney定理表明,对一个图G,G的最小点割集含至少2个点当且仅当G 中任意两点间都有至少2条内部点不交的路,即“分离”G中任意两点所需删除的最少顶点 数和这两点间内部点不交路的最大条数要么都大于等于2,要么都不超过2。这涉及到图的 连通性能的两个度量:删除顶点时图保持连通的能力和顶点间不交路径的重数。 Whitney定 理说明对2连通图这两种连通性度量是等价的。下列 Menger定理显示,这一结论对任意k 连通图都成立。 设G是一个简单图,x,y是G中任二不同顶点。如果从G中删去一组顶点后不再有 (x,y)路则称这组顶点分离x和y,而称这组顶点为一个(x,y)分离集。G中含点数最少的(x,y) 分离集称为最小x,y)分高集,其顶点数称为G的(x,y分高数,记为s(x,y)。此外,将G中 两两内部点不交的(x,y)路的最大条数记为r(x,y) 定理241( Menger,1927)对任意图G,设x,y是G中两个不相邻顶点,则G中分离x,y 所需的最少顶点数等于G中两两内部点不交的(x,y)路的最大条数,即s(x,y)=r(x,y) 证明:首先,对任意图G和G中任意两个不相邻顶点x,y,显然有sx,y)≥r(x,y)。下面用 反证法证明对任意图G和G中任意两个不相邻顶点x,y,s(x,y)≤r(x,y) 假设结论不真。则存在图G和G中两个不相邻顶点x,y,使得s(x,y)>r(x,y)。取G为 具有这种性质的所有图中顶点数最少并且边数最少的一个,即:对具有上述性质的任何一个 图H,要么D(G)rx,y)≥0,可知G是连通图。如果s(x,y)=1,则必 须r(x,y)=0,这与G是连通图矛盾。因此sx,y)>1。 (2)对G的任二异于x,y的相邻顶点u和v,存在G的顶点子集U,满足|U=s(x,y)-1 且UU{础}和UU{v}都是G的(x,y)分离集。 事实上,设e=l,H=G-e。H的(x,y)分离数 SH(x,y)≥s(x,y)-1,(* (否则存在H的(x,y)分离集R使得|Rsx,y)-2,则RU{}是G的(x,y)分离集,且只含 s(x,y)-1个点,这与G的(x,y)分离数为sx,y)矛盾)。另一方面,由于s(x,y)>r(x,y),H中 两两内部点不交的(x,y)路的条数 n(x,y)≤r(x,y)≤s(x,y)-1。(*)
9 （6）⇒（7）：对∀u, v,w∈V(G) ，存在(u,w) 路 P 含有顶点 v，则 P 的从 u 到 v 的一段 不含有 w。 （7）⇒（1）：因为对∀w∈V(G) 及∀u, v ∈V(G) ，存在(u, v)路不含有顶点 w，故 w 不 是割点。由 w 的任意性，G 无割点。从而 G 是块。 证毕。 §2.4 Menger 定理 上节的 Whitney 定理表明，对一个图 G，G 的最小点割集含至少 2 个点当且仅当 G 中任意两点间都有至少 2 条内部点不交的路，即“分离”G 中任意两点所需删除的最少顶点 数和这两点间内部点不交路的最大条数要么都大于等于 2，要么都不超过 2。这涉及到图的 连通性能的两个度量：删除顶点时图保持连通的能力和顶点间不交路径的重数。Whitney 定 理说明对 2 连通图这两种连通性度量是等价的。下列 Menger 定理显示，这一结论对任意 k 连通图都成立。 设 G 是一个简单图，x, y 是 G 中任二不同顶点。如果从 G 中删去一组顶点后不再有 (x, y)路则称这组顶点分离 x 和 y，而称这组顶点为一个(x, y)分离集。G 中含点数最少的(x, y) 分离集称为最小(x, y)分离集，其顶点数称为 G 的(x, y)分离数，记为 s(x, y)。此外，将 G 中 两两内部点不交的(x, y)路的最大条数记为 r(x, y)。 定理 2.4.1（Menger, 1927）对任意图 G，设 x, y 是 G 中两个不相邻顶点，则 G 中分离 x, y 所需的最少顶点数等于 G 中两两内部点不交的(x, y)路的最大条数，即 s(x, y) = r(x, y)。 证明：首先，对任意图 G 和 G 中任意两个不相邻顶点 x, y，显然有 s(x, y)≥ r(x, y) 。下面用 反证法证明对任意图 G 和 G 中任意两个不相邻顶点 x, y，s(x, y) ≤ r(x, y)。 假设结论不真。则存在图 G 和 G 中两个不相邻顶点 x, y，使得 s(x, y) > r(x, y)。取 G 为 具有这种性质的所有图中顶点数最少并且边数最少的一个，即：对具有上述性质的任何一个 图 H，要么υ(G) (H) r(x, y) ≥ 0，可知 G 是连通图。如果 s(x, y)=1，则必 须 r(x, y)=0,这与 G 是连通图矛盾。因此 s(x, y) > 1。 （2）对G的任二异于x, y的相邻顶点u和v，存在G的顶点子集U，满足|U| ( , ) 1 = − sxy 且 U {} ∪ u 和 U {} ∪ v 都是 G 的(x, y)分离集。 事实上，设 e = uv，H = G − e。H 的(x, y)分离数 sH (x, y) ≥ s(x, y) −1， (∗) （否则存在 H 的(x, y)分离集 R 使得|R|≤ s(x, y) −2，则 R {} ∪ u 是 G 的(x, y)分离集，且只含 s(x, y) −1 个点，这与 G 的(x, y)分离数为 s(x, y)矛盾）。另一方面，由于 s(x, y) > r (x, y)，H 中 两两内部点不交的(x, y)路的条数 (, ) Hr xy ≤ r (x, y)≤ s(x, y) −1。(∗∗)
由G的最小性可知,H中的(x,y)分离数等于H中两两内部点不交的(x,y)路的最大条数,即 sH(x,yl2(x,y)。结合(*)式和(**)式,知s(x,y)h1(x,y)=(x,y)-1。设U是H的 个最小(x,y)分离集,由于H与G只相差一条边e=,易见UU{和UU{v}都是G的(x y)分离集。 (3)用NG(x),Nc(y)表示x和y在G中邻点的集合,则N(x)∩Na(y)=φ。 事实上,假如N(x)∩N(y)≠φ,则彐∈N(x)∩N(y)。设H=G-l。由G 的最小性,H中(x,y)分离数等于H中两两内部点不交的(x,y)路的最大条数。与上述(2)的 证明类似可知,图H的(x,y)分离数sH(x,y)=s(x,y)-1,故H中存在sx,y)-1条两两内部点 不交的(x,y)路。显然它们和路xy一起形成G的s(x,y)条两两内部点不交的x,y)路。这与G 的取法矛盾。 (4)记k=s(x,y)。如果W={v1,w2,…,W}是G的一个最小(x,y)分离集,则 WsN(x)或者WsN(y)。 事实上,设GG为图G-W中分别包含x和y的连通分支,用G1表示由v(G2)∪W 在G中导出的子图,G2表示由(G,)儿∪W在G中导出的子图。显然(G1)∩H(G2)=W 如果D(G1)=k+1,则(G)={x},此时结论显然成立。同理,D(G2)=k+1时结论成 立。下面假设U(G1)≥k+2,且D(G2)≥k+2。给G1添加一个新顶点v*,将它与G1中 属于W的每个顶点都连新边,这样获得的图记为G1。若G1中存在(x,v*)分离集S满足|S 1,故U≠ψ。由结论(4),UUw}N(x) 或者UU{v}三N(y),但由于xV1∈E(G)及结论(3),可知UN(x),且 UgN(y);同样,由结论(4),UU{v2}∈N(x)或者UU{"2}≌N(y),但上面已 知U∈N(x),由结论(3)可知必定UU{v2}N(x),从而V2∈N(x)。这与P是 G的最短(x,y)路矛盾。证毕 由 Menger定理可得到 Whitney定理的如下推广
10 由 G 的最小性可知，H 中的(x, y)分离数等于 H 中两两内部点不交的(x, y)路的最大条数，即 sH (x, y)= (, ) Hr xy 。结合(∗)式和(∗∗)式，知 sH (x, y)= (, ) Hr xy = s(x, y) −1。设 U 是 H 的一 个最小(x, y)分离集，由于 H 与 G 只相差一条边 e = uv，易见 U {} ∪ u 和 U {} ∪ v 都是 G 的(x, y)分离集。 （3）用 ( ), ( ) NxNy G G 表示 x 和 y 在 G 中邻点的集合，则 () () Nx Ny G G ∩ = φ 。 事实上，假如 () () Nx Ny G G ∩ ≠ φ ，则∃u ∈ () () Nx Ny G G ∩ 。设 H Gu = − 。由 G 的最小性，H 中(x, y)分离数等于 H 中两两内部点不交的(x, y)路的最大条数。与上述（2）的 证明类似可知，图 H 的(x, y)分离数 sH (x, y) = s(x, y) −1，故 H 中存在 s(x, y) −1 条两两内部点 不交的(x, y)路。显然它们和路 xuy 一起形成 G 的 s(x, y)条两两内部点不交的(x, y)路。这与 G 的取法矛盾。 （4）记 k = s(x, y)。如果 1 2 {, , , } W ww w = " k 是 G 的一个最小(x, y)分离集，则 ( ) W Nx ⊆ G 或者 ( ) W Ny ⊆ G 。 事实上，设 Gx、Gy为图G −W 中分别包含 x 和 y 的连通分支，用G1表示由 (G ) V W x ∪ 在 G 中导出的子图，G2 表示由 (G ) V W y ∪ 在 G 中导出的子图。显然 1 2 VV W (G ) (G ) ∩ = 。 如果 1 υ(G ) 1 = + k ，则 (G ) { } V x x = ，此时结论显然成立。同理， 2 υ(G ) 1 = + k 时结论成 立。下面假设 1 υ(G ) 2 ≥ + k ，且 2 υ(G ) 2 ≥ + k 。给G1添加一个新顶点 v*，将它与G1中 属于 W 的每个顶点都连新边，这样获得的图记为G1 ∗ 。若G1 ∗ 中存在(x, v* )分离集 S 满足 | S | 1，故 U ≠ φ 。由结论（4），U {}1 ∪ v ( ) ⊆ N x G 或者 U {}1 ∪ v ( ) ⊆ N y G ，但由于 1 xv EG ∈ ( ) 及结论（３）， 可知 U () ⊆ N x G ，且 U ⊆ ( ) N y G ；同样，由结论（4），U {}2 ∪ v ( ) ⊆ N x G 或者 U {}2 ∪ v ( ) ⊆ N y G ，但上面已 知 U () ⊆ N x G ，由结论（３）可知必定 U {}2 ∪ v ( ) ⊆ N x G ，从而 2 ( ) G v Nx ∈ 。这与 P 是 G 的最短(x, y)路矛盾。证毕。 由 Menger 定理可得到 Whitney 定理的如下推广
