Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
@Garry Myerson Shame on me... I forgot to accept most of them. –  Libor Sep 18 '12 at 14:03

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks for explanation. I overlooked the fact that flow cannot be manipulated on individual edges - it can be decreased on whole path only, thus making it an augmenting path again. –  Libor Sep 18 '12 at 14:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.