定理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)=13 定理 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