点割集(举例) + G: a, e, c)g, k,j], (b, e, f, k, hh +G2: a, e,cg, k,j,b, e,t, k, hy ae G 《集合论与图论》第16讲
《集合论与图论》第16讲 6 点割集(举例) G1: {f},{a,e,c},{g,k,j},{b,e,f,k,h} G2: {f},{a,e,c},{g,k,j},{b,e,f,k,h} a b c d f e g h k j i a b c e f d j i g h k G1 G2
割点( ut-point/ cut-vertex) 割点:V是割点台→{是割集 例:G中缇是割点,G2中无割点 a 《集合论与图论》第16讲
《集合论与图论》第16讲 7 割点(cut-point / cut-vertex) 割点: v是割点 ⇔ {v}是割集 例: G1中f是割点, G2中无割点 a b c d f e g h k j i a b c e f d j i g h k G1 G2
边割集( edge cutset) 婚边割集:无向图G=<V,E>,≠ECE,满足 (1)p(GE)>p(G; 2)极小性:VEcE,p(GE")=p(G, 则称E’为边割集 癱说明:“极小性”是为了保证边割集概念的 非平凡性 《集合论与图论》第16讲
《集合论与图论》第16讲 8 边割集(edge cutset) 边割集: 无向图G=<V,E>, ∅≠E’⊂E, 满足 (1) p(G-E’)>p(G); (2) 极小性: ∀E’’⊂E’, p(G-E’’)=p(G), 则称E’为边割集. 说明: “极小性”是为了保证边割集概念的 非平凡性
边割集(举例) 秦G1:{(af,(e,f,(d,,{f:g),(,k),.k),j,)} {a,;e,);(,(,9),(,1),(,{(,d丹 G2:{(b,a),6,),b,c a e G 《集合论与图论》第16讲
《集合论与图论》第16讲 9 边割集(举例) G1: {(a,f),(e,f),(d,f)}, {(f,g),(f,k),(j,k),(j,i)} {(a,f),(e,f),(d,f),(f,g),(f,k),(f,j)}, {(c,d)} G2: {(b,a),(b,e),(b,c)} a b c d f e g h k j i a b c e f d j i g h k G1 G2
割边( cut-edge)(桥) 割边:(V是割边台{u是边割集 例:G1中(g)是桥,G2中无桥 e 《集合论与图论》第16讲
《集合论与图论》第16讲 10 割边(cut-edge)(桥) 割边: (u,v)是割边 ⇔ {(u,v)}是边割集 例: G1中(f,g)是桥, G2中无桥 a b c d f e l h k j i a b c e f d j i g h k G1 G2 g