0
$\begingroup$

We are learning of the Ford-Fulkerson Algorithm for max-flow/min-cut, and I have been wondering of the following question:

How do we exactly find which nodes are on the "sink" side of the min-cut produced using the algorithm?

I have read here https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ that all nodes reachable from the source node on the final residual graph using a BFS/DFS are on one side of the min-cut.

Then, will all nodes not reachable from the source node on the final residual graph be on the other side of the min cut? Is there any way of finding these nodes using a search algorithm of some sort - for example, reversing the edges of the final residual graph and running a BFS/DFS on the sink node?

Thanks a lot!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You can prove that any minimal s-t-cut results in two connected components, the one with s in, and the one with t in. Call them S and T.

Then the actual cut is all the edges that go from S to T.

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.