北大离散数学7.4.pdf

第16讲 连通度 1. 点(边)割集,点连通度κ,边连通度λ 2. Whitney定理, 简单连通图κ,λ,δ之间的 关系 3. 2-连通, 2-边连通的充要条件 4. 割点, 桥, 块的充要条件 《集合论与图论》第16讲 1 如何定义连通度 问题: 如何定量比较无向图连通性的强与 弱? 《集合论与图论》第16讲 2 如何定义连通度 点连通度: 为了破坏连通性,至少需要删 除多少个顶点? 边连通度: 为了破坏连通性,至少需要删 除多少条边? 说明: “破坏连通性”指p(G-V’)p(G), 或 p(G-E’)p(G),即“变得更加不连通” 《集合论与图论》第16讲 3 割集(cutset) 点割集(vertex cut) 边割集(edge cut) 割点(cut vertex) 割边(cut edge)(桥)(bridge) 《集合论与图论》第16讲 4 点割集(vertex cutset) 点割集: 无向图G=V,E, ∅≠V’⊂V, 满足 (1) p(G-V’)p(G); (2) 极小性: ∀V’’⊂V’, p(G-V’’)=p(G), 则称V’为点割集. 说明: “极小性”是为了保证点割集概念的 非平凡性 《集合论与图论》第16讲 5 点割集(举例) G : {f},{a,e,c},{g,k,j},{b,e,f,k,h} 1 G : {f},{a,e,c},{g,k,j},{b,e,f,k,h} 2 a g a g b e f k h b k h e f c d j i c d j i G1 G2 《集合论与图论》第16讲 6 割点(cut-point / cut-vertex) 割点: v是割点⇔{v}是割集 例: G 中f是割点, G 中无割点 1 2 a g a g b e f k h b k h e f c d j i c d j i G1 G2 《集合论与图论》第16讲 7 边割集(edge cutset) 边割集: 无向图G=V