Suppose we have an oriented graph and max-flow has been determined.
I found that to determine min-cut or minimum s-t cut can then be found by labeling graph nodes such that nodes belonging to source are those which can be reached from source by unsaturated edges. On the contrary: Nodes belonging to sink are all the other, i.e. nodes reachable from sink by saturated edges.
My question is – why? I am unable to grasp this "phenomenon" intuitively.
In other words: Why the minimum cut cannot go through any other egdes, but those who connect nodes label as "belonging to the source" and those "belonging to the sink". Why the min-cut does not go through any other nodes?
Best Answer
I will try to show you why this is intuitive using counter example. Let us call the set reachable by unsaturated paths A, and the other set B. so s is in A, and t is in B. We know that by definition, each edge from A to B is in the minimum cut. Now suppose A were some other set such that it had a node v such that v was not reachable by an unsaturated path. This means that there is an edge such that the path from s to v is saturated, and let its capacity be x and its endpoints be x1 and x2. Also, let the minimum capacity of the edge from v to B be y. If we move x2 to B, and all vertices on x2-v path to B, then we will have a more minimal cut than earlier, since the capacity of our cut is now reduced by y and increased by x (y-x>=0). Therefore it couldnt have been a minimum cut in the first place. The other case is that some edge from A to B is not saturated. This implies that there is a node in B which is reachable from A by an augmenting path, which again leads to a contradiction.