1
$\begingroup$

So I'm following this article and they use the following algorithm to find the min-cut.

Algorithm:

  1. Run Ford-Fulkerson algorithm and consider the final residual graph.

  2. Find the set of vertices that are reachable from the source in the residual graph.

  3. All edges which are from a reachable vertex to non-reachable vertex are minimum cut edges. Print all such edges.

Is there a proof showing this finds the min-cut?

Improve this question
$\endgroup$
1
  • $\begingroup$ Was the answer below helpful? Have you considered upvoting and accepting it? (This comment will be deleted upon feedback.) $\endgroup$
    – John L.
    Apr 6, 2022 at 7:24

1 Answer 1

Reset to default
1
$\begingroup$

Yes, this is proved in any standard source that proves the max-flow min-cut theorem. You can find one proof on Wikipedia.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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