How do you know a flow is the largest possible? By showing a set of lines that every train must cross, whose capacities add up to exactly the flow. The max-flow min-cut theorem says such a set always exists, and it proves that Ford-Fulkerson’s stopping rule is right.
Cuts in a network
An s-t cut splits the vertices into two sides: S, which contains s, and T, the rest, which contains t. Its capacity c(S, T) is the total capacity of the edges from S to T. Edges from T back to S do not count. SPAN-4 used cuts with costs; here the edges have a direction and capacities.
The flow across the cut is the flow on edges from S to T minus the flow on edges from T to S. Step through the figure’s first variant: four different cuts of the same maximum flow.
A maximum flow of 19. A cut splits the stations into a side S with s, and the rest with t. Its capacity is the total capacity of the lines from S to the rest.
Every flow fits under every cut
Add up (flow out − flow in) over the vertices of S, as in lesson 1. Conservation makes every term 0 except the term for s, which is the value. In the sum, an edge with both ends in S is added once and taken once, so it cancels. What is left are the edges between S and T: those from S to T count plus, those from T to S count minus. That is the flow across.
The flow across is at most the flow on the edges from S to T (the edges back only subtract), and each of those carries at most its capacity. So the largest flow is at most the smallest cut. Any one cut gives an upper bound on every flow.
The theorem
Ford and Fulkerson proved more: for a flow f, these three statements are equivalent.
- f is a maximum flow.
- The residual graph of f has no augmenting path.
- Some cut has capacity exactly |f|.
1 gives 2: if there were an augmenting path, lesson 2 would give a larger flow. 3 gives 1: no flow can be larger than that cut, by the bound above.
2 gives 3, the main step: let S be every vertex that s can reach in the residual graph, and T the rest. t is in T, because there is no augmenting path, so this is a cut. Take an edge u → v from S to T. If it had room left, the arc u → v would be in the residual graph and v would be reachable, so it is full: f(u, v) = c(u, v). Take an edge v → u from T to S. If it carried any flow, the back arc u → v would be in the residual graph, so it carries 0. So the flow across the cut is exactly c(S, T), and it equals |f|.
So Ford-Fulkerson is right when it stops (statement 2 gives statement 1), and the maximum flow and the minimum cut are the same number. This is an example of duality: a maximum problem and a minimum problem whose answers meet, so each answer proves that the other is the best possible.
Finding a smallest cut
The proof is also the method. Run any maximum-flow method to the end. The last search from s fails to reach t, and the vertices it reached are S. Step through the second variant of the figure: S = {s, B}, and the two lines out of it, s → A and B → D, are both full, 10 + 9 = 19.
With Edmonds-Karp, the arcs that reached each vertex in the last BFS mark S at no extra cost. Several smallest cuts can exist; the one from s is the one with the smallest S. Searching backwards from t gives the one with the smallest T. Now try FLOW-P4, The weakest set of lines.
What cuts answer
- Separate routes (Menger’s theorem). Give every line capacity 1. A flow of value k gives k routes from s to t that share no line (follow the flow), and a cut of capacity k is k lines whose closing separates s from t. So the most routes that share no line equals the fewest lines whose closing separates the two. Vertex limits of 1 (lesson 1’s split) give the same for routes that share no station. CONN-3’s bridges are the case of one line.
- Choosing projects. Projects earn money, some need machines that cost money, and a project can only run if its machines are bought. The best set of projects is found with one minimum cut: s to each project (its earning), each machine to t (its cost), and a line of very large capacity from each project to each machine it needs.
- Splitting an image. To separate an object from its background, each pixel is joined to s by how much it looks like the object, to t by how much it looks like background, and to its neighbours by how similar they are. The minimum cut is a good split.
- Matching. Lesson 5: in a bipartite graph, the minimum cut is a smallest set of vertices that touches every edge.
The cost of finding a minimum cut is the cost of the flow plus one search: O(V · E²) (V times E times E) with Edmonds-Karp, O(V² · E) (V times V times E) with Dinic.
FLOW-4 counts as completed once you step through the figure to the last step.