Max-Flow Min-Cut Theorem

Ford-Fulkerson algorithm finds the maximum flow from source S to sink T. By the max-flow min-cut theorem, this equals the minimum cut capacity separating S from T.

0
Max Flow
—
Min Cut
0
Iterations
Ready
Status

Max-Flow Min-Cut Theorem (Ford & Fulkerson 1956)

Max flow from S→T = Min cut capacity
Augmenting path: path in residual graph from S to T
Residual capacity: r(u,v) = c(u,v) − f(u,v)
Complexity: O(E · |f*|) for integer capacities
Ready. Press "Step" or "Run" to find max flow.