Graph Theory37 sections · 1633 units
Open in Course

Finding the Min Cut

Using max flow residual graph

After computing max flow, the minimum cut is found using the residual graph. Run BFS or DFS from ss in the residual graph to find all reachable vertices. These vertices can still receive flow from ss. Let SS be the set of reachable vertices and TT be the rest.

The cut (S,T)(S, T) is a minimum ss-tt cut. This partition naturally separates the graph. Edges from SS to TT in the original graph are saturated (flow equals capacity). Removing them disconnects ss from tt. These are exactly the bottleneck edges.