algorithm - 在图中查找割集

Question

可能重复：
算法：对于G =（V，E），如何确定边集（e属于E）是否是图的有效割集

图 G = (V,E) 的边的子集 S，如何检查它是否是图的有效割集？注意：割是将图的顶点划分为两个不相交的子集。因此，割的割集是其端点在分区的不同子集中的边的集合。我有兴趣找到解决这个问题的算法

Answer 1

换句话说，您要确定是否存在标签 V -> {0, 1} 使得 S 中的边具有不同标签的端点，而 E - S 中的边具有相同标签的端点。如果存在这样的标签，则始终可以通过以下过程构建。

遍历 G（比如说深度优先，但这并不重要）。任意标记遍历根。每次处理从标记节点 u 到其他节点 v 的边 e 时，如果 e 不在 S 中，则用 u 的标签标记 v，如果 e 在 S 中，则用 u 的标签标记 v。如果 v 已经有不同的标签，则 S 是不是割集。否则，如果遍历没有发生任何事件，则 S 是割集。