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.

I'm about to read the proof of the max-flow min-cut theorem that helps solve the maximum network flow problem. Could someone please suggest an intuitive way to understand the theorem?

share|improve this question
    
Max-flow min-cut is part of a family of theorems all of which assert that some obvious necessary condition is in fact sufficient, and all of which are somehow equivalent. It is worth studying all of these theorems as well as proofs of their equivalences to get a feel for the underlying result: en.wikipedia.org/wiki/… –  Qiaochu Yuan Jun 22 '12 at 22:35

2 Answers 2

up vote 6 down vote accepted

Imagine a complex pipeline with a common source and common sink. You start to pump the water up, but you can't exceed some maximum flow. Why is that? Because there is some kind of bottleneck, i.e. a subset of pipes that transfer the fluid at their maximum capacity--you can't push more through. This bottleneck will be precisely the minimum cut, i.e. the set of edges that block the flow. Please note, that there may be more that one minimum cut. If you find one, the you know the maximum flow; knowing the maximum flow you know the capacity of the cut.

Hope that explains something ;-)

share|improve this answer

A cut is a bottleneck: any total flow through the network must all pass through the bottleneck at once.

The bottle might have a wide part and a narrow part. The total flow must pass through the wide part and the narrow part. It is limited by the narrow part, not by the wide part, because the wide part is wide and can accommodate the flow into or out of the narrow part.

Overall, total flow through the bottle will be constrained by the total flow that can pass through the narrowest bottleneck.

So to find the maximum possible flow, you find the narrowest bottleneck in the bottle, which is the minimum cut.

share|improve this answer

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.