Chapter 12
Cuts and Flows
Max-flow min-cut is the most reusable theorem in combinatorial optimisation: every problem whose answer is “the smallest set of things blocking the largest number of paths” is a flow problem in disguise.
4 pages3,727 words10 problems1 interactive
1Cuts and FlowsThe definitions, the capacity bound, and why "flow" and "cut" are the same optimisation seen from two sides.2Max Flow: Ford–Fulkerson, Dinic, Push–RelabelThree augmenting strategies, why each terminates, Dinic's O(V^2 E) proof, and how to read the min cut out of the residual graph.3Min-Cut ModelsSeven reductions where the answer of a combinatorial problem is exactly a minimum cut — maximum closure, bipartite covering, project selection, and the submodular energy.4Min-Cost Max-FlowSuccessive shortest augmenting paths with potentials, why negative cycles cannot appear, and the assignment/transportation problems it solves.