Most examples I've seen involve cuts snaking through graphs picking off various edges.

My question is why not simply do a cut either involved the edges leaving the source or the edges entering the sink?

Max-flow min-cut theorem says the maximum flow is equal to the minimum cut so surely either of these two cuts satisfies the conditions for a minimum cut?

  • 2
    $\begingroup$ Just make an example where not all the edges at the source and at the sink are saturated by a maximal flow, and you'll have an example where those edges don't give a minimal cut. I bet if you look at an example where the cut "snakes" through the graph, the cut you want to use instead is not minimal. Maybe the problem is that you don't understand the definition of "minimal cut"? It's a cut of minimal total capacity. $\endgroup$ – Gerry Myerson May 5 '16 at 13:27
  • $\begingroup$ Here's an example of a given solution for a minimum cut question following finding the maximum flow: Example. Maybe it's simply that the examples I've been given happen to satisfy my query? $\endgroup$ – Jonathan May 5 '16 at 15:18
  • 2
    $\begingroup$ So, in that example, the value of the flow is 12. What's the capacity of the cut using all the edges leaving the source? What's the capacity of the cut using all the edges entering the sink? They're both bigger than 12, aren't they? So, neither one is a minimal cut, is it? $\endgroup$ – Gerry Myerson May 5 '16 at 23:07
  • $\begingroup$ Are you still here? $\endgroup$ – Gerry Myerson May 6 '16 at 23:14
  • 1
    $\begingroup$ Capacity of an edge is the bigger number on the edge. Capacity of a cut is the sum of the capacities of the edges in the cut. You're adding up the flows, instead. $\endgroup$ – Gerry Myerson May 7 '16 at 13:07

Your Answer

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

Browse other questions tagged or ask your own question.