北京大学：《离散数学》系列课程之一《集合论与图论》第16讲 连通度

第16讲连通度 1.点(边割集,点连通度K,边连通度入 2. Whitney定理,简单连通图,。之间的 关系 秦3.2连通,2-边连通的充要条件 4.割点,桥,块的充要条件 《集合论与图论》第16讲

《集合论与图论》第16讲 1 第16讲 连通度 1. 点(边)割集,点连通度κ,边连通度λ 2. Whitney定理, 简单连通图κ,λ,δ之间的 关系 3. 2-连通, 2-边连通的充要条件 4. 割点, 桥, 块的充要条件

如何定义连通度 问题:如何定量比较无向图连通性的强与 揭? 《集合论与图论》第16讲

《集合论与图论》第16讲 2 如何定义连通度 问题: 如何定量比较无向图连通性的强与 弱?

如何定义连通度 癱点连通度:为了破坏连通性至少需要删 除多少个顶点? 癱边连通度:为了破坏连通性,至少需要删 除多少条边? 说明:“破坏连通性?指p(GV)>p(G,或 p(GE)>p(G,即“变得更加不连通” 《集合论与图论》第16讲

《集合论与图论》第16讲 3 如何定义连通度 点连通度: 为了破坏连通性,至少需要删 除多少个顶点? 边连通度: 为了破坏连通性,至少需要删 除多少条边? 说明: “破坏连通性”指 p(G-V’)>p(G), 或 p(G-E’)>p(G),即“变得更加不连通”

割集( utset 点割集( ertex cut) 边割集 edge cut) 点 cut vertex) 割边( cut edge)(桥)( bridge) 《集合论与图论》第16讲

《集合论与图论》第16讲 4 割集(cutset) 点割集(vertex cut) 边割集(edge cut) 割点(cut vertex) 割边(cut edge)(桥)(bridge)

点割集( ertex cutset) 婚点割集:无向图G=,≠VcV,满足 (1)p(G-V)>p(G; 2)极小性:V"<V,p(GV")=p(G), 则称V为点割集. 癱说明:“极小性”是为了保证点割集概念的 非平凡性 《集合论与图论》第16讲

《集合论与图论》第16讲 5 点割集(vertex cutset) 点割集: 无向图G=, ∅≠V’⊂V, 满足 (1) p(G-V’)>p(G); (2) 极小性: ∀ V’’⊂V’, p(G-V’’)=p(G), 则称V’为点割集. 说明: “极小性”是为了保证点割集概念的 非平凡性

点割集(举例) + 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=,≠ECE,满足 (1)p(GE)>p(G; 2)极小性:VEcE,p(GE")=p(G, 则称E’为边割集 癱说明:“极小性”是为了保证边割集概念的 非平凡性 《集合论与图论》第16讲

《集合论与图论》第16讲 8 边割集(edge cutset) 边割集: 无向图G=, ∅≠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