Network flow Ford-Fulkerson has finished. A minimum cut splits the vertices into a source side and a target side. How are those two sides identified using the final residual network?

Question

Accepted Answer

The source side is the set of vertices still reachable from s in the residual network, and the target side is the set of remaining vertices.

Answer

The sides are found by running the algorithm again from t to s and taking the vertices it visits as the source side.

Answer

The two sides are the two endpoints of each saturated arc, one side each.

Answer

The source side is the set of vertices that can still reach t in the residual network, and the target side is the set of remaining vertices.

Answer

The source side is the set of vertices adjacent to s in the original network, and the target side is the set of remaining vertices.

Crowdly

Network flow Ford-Fulkerson has finished. A minimum cut splits the vertices into...

Want instant access to all verified answers on learning.monash.edu?