第二章图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图,其连通的程度 也有高有低。例如,下列三个图都是连通图。对于图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）式得