The Cut
Reading the Cut
Once no augmenting path remains, the final residual graph tells you where the minimum cut is. The source side is exactly the residual-reachable set, and the sink side is everything else. This lesson reads the certificate directly from the diagram, turning the stopping condition into a proof rather than a guess.
Read S
Read S as the nodes still reachable from s in the final residual graph. This is not a new optimization problem; it is a reachability pass on the final residual arcs. Why: if t is unreachable, then no augmenting path remains. Interpretation: the reachable set is the part of the network that still has residual access from the source after all useful pushes have been exhausted.
Read T
The remaining nodes form T. The partition is forced once the residual-reachable side is known. Why: every source-to-sink route in the original network would have to cross the boundary from S to T.
Read the bottleneck
The cut value is 4. The boundary edges are the bottleneck certificate. Why: their total capacity is an upper bound, and the already-computed flow reaches that same value.
Diagram note
The cut is read from recomputed residual reachability, then painted by the graph atom. The exact scope is this integer-capacity network: Ford-Fulkerson finds the flow, residual reachability finds the cut, and equality proves optimality for this instance. Pixel positions are rounded for layout; every number shown is exact.