Find cut set in a graph [duplicate]

This question already has answers here: 开发者_JS百科 Closed 11 years ago.

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

---

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.