Max-Flow / Min-Cut

Ford-Fulkerson augmenting paths on a random network. Green = flow, red = saturated edges, dashed = min-cut. Max flow equals min cut capacity (Max-flow min-cut theorem).

Press "New Graph" to start

The max-flow min-cut theorem (Ford & Fulkerson 1956, Elias et al. 1956): the maximum flow equals the minimum cut capacity. Fundamental to network analysis, matching, and scheduling.