扇形割集( fan cutset) Ic()不一定是边割集(不一定极小) I6()不是边割集V是割点 扇形割集:E是边割集∧EIe(V) 例:{(a9),b)号(9,a),(g,b)、9,C}{(cd) {(d,e)、(,{(a,b),yb,(g,c) a e 《集合论与图论》第16讲
《集合论与图论》第16讲 11 扇形割集(fan cutset) IG(v)不一定是边割集(不一定极小) IG(v)不是边割集 ⇔ v是割点 扇形割集: E’是边割集∧E’⊆IG(v) 例: {(a,g),(a,b)},{(g,a),(g,b),(g,c)},{(c,d)}, {(d,e),(d,f)}, {(a,b),(g,b),(g,c)} a b c g d f e
连通度( ertex-connectivity) 婚点连通度:G是无向连通非完全图, K(G)=mnN|是G的点割集} 鲁规定:K(K)=n-1,G非连通:K(G)=0 例:K(G=1,K(H)=2,K(F)=3,K(K5)=4 H 《集合论与图论》第16讲
《集合论与图论》第16讲 12 点连通度(vertex-connectivity) 点连通度: G是无向连通非完全图, κ(G) = min{ |V’| | V’是G的点割集 } 规定: κ(Kn) = n-1, G非连通: κ(G)=0 例: κ(G)=1, κ(H)=2, κ(F)=3, κ(K5)=4 GHF
边连通度( edge-connectivity) 边连通度:G是无向连通图, λ(G)=min《E"E是G的边割集} 规定:G非连通:(G=0 例:入(G)=1,2(+)=2,()=3,2(K<)=4 H 《集合论与图论》第16讲 13
《集合论与图论》第16讲 13 边连通度(edge-connectivity) 边连通度: G是无向连通图, λ(G) = min{ |E’| | E’是G的边割集 } 规定: G非连通: λ(G)=0 例: λ(G)=1, λ(H)=2, λ(F)=3, λ(K5)=4 GHF
k-连通图,k边连通图 k连通图( k-connected):K(G≥k k-边连通图( k-edge-connected:(G≥}k 例:彼得森图κ=3,^=3;它是1连通图, 2连通图,3-连通图,但不是4连通图; 是1-边连通图,2边连通图,3边连通图,但 不是4边连通图 《集合论与图论》第16讲
《集合论与图论》第16讲 14 k-连通图, k-边连通图 k-连通图(k-connected): κ(G)≥k k-边连通图(k-edge-connected): λ(G)≥k 例: 彼得森图 κ=3, λ=3; 它是1-连通图, 2-连通图,3-连通图, 但不是4-连通图; 它 是1-边连通图, 2-边连通图,3-边连通图,但 不是4-边连通图
Whitney定理 定理10:K入≤6 证明:不妨设G是3阶以上连通简单非完 全图 ≤8)设d(0=8,则()16,1)中一定 有边割集E,所以≤Ee()=8 (K≤)设E是边割集,E|=入,从V∈E)中找出 点割集V,使得≤3λ,所以K≤NV|sλ 《集合论与图论》第16讲 15
《集合论与图论》第16讲 15 Whitney定理 定理10: κ≤λ≤δ. 证明: 不妨设G是3阶以上连通简单非完 全图. (λ≤δ) 设d(v)=δ, 则|IG(v)|=δ, IG(v)中一定 有边割集E’, 所以λ≤|E’|≤|IG(v)|=δ. (κ≤λ) 设E’是边割集,|E’|=λ,从V(E’)中找出 点割集V’,使得|V’|≤λ, 所以κ≤|V’|≤λ.