algorithm - 在图中查找割集

Question

考虑 V = {a,b,c} 和 E = {ab,bc,ca} 的三角形图 G。如果边子集 S= {ab,bc} 被移除，那么我们得到左边的边 ac。我的问题S 是一个有效的割集(它将 G 划分为两个顶点子集 {b} 和 {a,c})

注意:割是将图的顶点划分为两个不相交的子集。割的割集是端点在划分的不同子集中的边的集合。

Answer 1

是的。

{ab, bc} 是割集，因为它会导致割集。由 {ab, bc} 引起的切割是 ( {a,c} , {b} )。

我将澄清定义:

• 割是图顶点的划分。例如，( {a,c} , {b} ) 是一个割，因为图中的每个顶点恰好属于两个集合中的一个。
• 切割 (S,T) 的切割集是以下边集:{uv | u 在 S 中，v 在 T 中。例如，( {a,c} , {b} ) 的割集是 {ab, bc}。
• 边的集合 E 是一个割集当且仅当存在一个割集 E 是它的割集。在您的示例中，集合 {ab} 不是割集，因为您无法确定顶点 c 属于 S 还是 T。集合 {ab,bc,ca} 不是割集，因为您可以很容易地通过矛盾证明不存在 {ab,bc,ca} 是其割集的割。