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