Maximum flow and the min-cut theorem

A flow network is a directed graph with a source s, a sink t, and a capacity on every edge: the most that can travel along it per unit of time. Think of pipes, of cables between data centres, of the settlement capacity between banks. A flow assigns an amount to each edge such that:

• capacity: no edge carries more than its capacity;
• conservation: at every node other than s and t, what flows in equals what flows out.

The value of the flow is the total leaving s (equivalently, arriving at t). The maximum flow problem asks for the largest value possible.

Split the nodes into two sides, S containing s and T containing t. Every unit of flow must cross from S to T on some edge, so no flow can exceed the total capacity of the edges going from S to T. That total is the capacity of the cut.

Every cut gives a bound, so the maximum flow is at most the minimum cut capacity. The max-flow min-cut theorem says the two are equal: the largest flow is exactly the capacity of the smallest cut. The algorithm in the next lesson proves it constructively: when it stops, it hands you a flow and a cut of the same value.

The theorem turns many problems into flow problems. "The fewest roads to close so that A cannot reach B" is a minimum cut with every capacity 1, and its answer is the maximum flow.

• Matching and assignment: candidates to roles, students to projects (the next module).
• Edge-disjoint paths: how many routes from A to B share no link? Set every capacity to 1.
• Reliability: the fewest links whose failure disconnects two sites is the minimum cut.
• Project selection and image segmentation, where a cleverly built network's minimum cut is the optimal choice.