0
$\begingroup$

What is the intuition behind the max-flow min-cut theorem?

I know that the min-cut is the dual of max-flow when formulated as a linear program, but the result seems artificial to me.

$\endgroup$
  • 4
    $\begingroup$ The minimum cut is the bottleneck of the whole network. I think every metaphor for flows (water pipes, streets, ...) illustrate that. $\endgroup$ – Raphael Apr 24 '15 at 10:34
3
$\begingroup$

So you have a flow thought the network. If you want the maximal flow, your network should not have any bottlenecks. And if you partition the network in two parts, where the source and the sink are in different partitions - you won't be able to push more though the network than this cut - i.e. the sum of edges.

Now the minimum cut will be the worst bottleneck in the network. So it will correspond to maxflow.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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