Max flow, min cut

Water enters at S and leaves at T. Each pipe shows flow/capacity, and water only runs the way the arrow points. Tap junctions one after another to trace a path from S to T. When you reach T the demo pushes as much as that path can take. Or press Step and let the demo choose a path. Before you start, guess the most that can get through. Keep going until no path is left.

empty pipecarrying flowfullyour path, then the cut

What's going on

A path from S to T can take as much extra flow as its tightest pipe has room for. Push that much, then look for another path. This is the Ford–Fulkerson method.

Going backwards. A path may also run against an arrow, but only along a pipe that already carries flow. Doing so sends some of that flow back and routes it another way. Try the network called "The trap". Tap S, A, B, T first. That path fills the middle pipe and seems to block everything at 4. Now tap S, B, A, T. The step from B to A runs backwards along pipe A → B and undoes the bad choice. The total rises to 8.

The cut. When no path is left, colour every junction that S can still reach with spare room. T is not one of them. The pipes that lead from the coloured junctions to the rest are all full, or S could reach further. Any pipe coming back the other way is empty. So every drop that reaches T crosses those full pipes exactly once, and the flow equals their total capacity.

A set of pipes like that, whose removal separates S from T, is called a cut. No flow can be bigger than the capacity of any cut, because everything has to cross it. You have just found a flow and a cut with the same number. So the flow is the largest possible and the cut is the smallest possible. That is the max-flow min-cut theorem: the most a network can carry equals the capacity of its narrowest cut.

Sheet: The bottleneck theorem. A cousin of this demo: shortest path, step by step.