(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