algorithm - 在图中查找割集

Question

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

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

Answer 1

是的。

{ab, bc}是一个割集，因为它引发了一个割。由{ab, bc}引起的切割是( {a,c} , {b} )。

我将澄清定义：

• 割是图顶点的分区。例如，( {a,c} , {b} )是一个割，因为图中的每个顶点恰好属于两个集合中的一个。
• 割( S,T) 的割集是以下边集：u 在 S 和 v 在 T}。例如，( {a,c} , {b} )的割集是{ab, bc}。
• 一个边集 E 是一个割集当且仅当存在一个 E 是它的割集的割。在您的示例中，集合{ab}不是割集，因为您无法确定顶点 c 属于 S 还是 T。集合{ab,bc,ca}不是割集，因为您可以轻松证明矛盾的是，没有{ab,bc,ca}是它的割集的割。