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?

$\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

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.

$\endgroup$

Your Answer

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

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