求图中的割集
可能的重复：
算法：对于G = (V,E)，如何判断边的集合（e属于E）是否是图的有效割集
边的子集S G = (V,E ）， 如何可以检查它是否是图的有效割集吗？ 注意：切割是将图的顶点划分为两个不相交的子集。因此，割集的割集是其端点位于分区的不同子集中的边的集合。我有兴趣找到解决这个问题的算法
Possible Duplicate:
Algorithm: for G = (V,E), how to determine if the set of edges(e belong to E) is a valid cut set of a graph
A subset S, of edges of a graph G = (V,E), how can one check whether it is a valid cut-set of the graph or not?
Note: A cut is a partition of the vertices of a graph into two disjoint subsets. So, cut-set of the cut is the set of edges whose end points are in different subsets of the partition. I am interested to find an algorithm for this problem
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
也就是说，你要判断是否存在一个标签V -> 。 {0, 1} 使得 S 中的边具有具有不同标签的端点，并且 E - S 中的边具有具有相同标签的端点。这样的标签，如果存在的话，总是可以通过以下过程来构造。
遍历G（说是深度优先，但这并不重要）。任意标记遍历根。每次处理从标记节点 u 到其他节点 v 的边 e 时，如果 e 不在 S 中，则用 u 的标签标记 v，如果 e 在 S 中，则用 u 的标签相反的标记。如果 v 已经有不同的标签，则 S 是不是割集。否则，如果遍历顺利完成，则 S 是割集。
In other words, you want to determine whether there exists a labeling V -> {0, 1} such that edges in S have endpoints with different labels, and edges in E - S have endpoints with identical labels. Such a labeling, if it exists, always can be constructed by the following procedure.
Traverse G (say depth-first, but it doesn't really matter). Label traversal roots arbitrarily. Every time you process an edge e from a labeled node u to some other node v, label v with u's label if e not in S and the opposite of u's label if e in S. If v already has a different label, then S is not a cut-set. Otherwise, if the traversal finishes without incident, then S is a cut-set.