Math Detours · Grade 11 · Around the corner · 15

The bottleneck theorem

The most traffic a network can carry equals the capacity of its narrowest cut. Push flow along paths until no path is left, and the cut reveals itself.

Name ____________________Date ____________

Tonight's idea

Water runs through one-way pipes from a source \(s\) to a sink \(t\). Each pipe has a capacity. A flow gives each pipe an amount, at most its capacity, with nothing lost at a junction: what goes in comes out. How much can reach \(t\)?

A cut gives a limit. Put the junctions on two sides, \(s\) on one and \(t\) on the other. The cut's capacity is the total capacity of the pipes leading from the \(s\) side to the \(t\) side. Everything that reaches \(t\) has to cross, so

every flow \(\le\) every cut. If a flow and a cut have the same size, that flow is the largest possible and that cut is the smallest.

Ford and Fulkerson proved that this always happens: max flow = min cut.

7 / 8 2 / 6 4 / 4 3 / 3 2 / 5 4 / 6 5 / 5 cut s A B C D t
Each pipe shows flow / capacity for the flow found in the example. Full pipes are orange. The dashed cut has \(s\), \(A\), \(B\), \(D\) on the source side.

To find both, push flow along any path from \(s\) to \(t\) with spare capacity in every pipe, and repeat until none is left. Then mark every junction still reachable from \(s\) through pipes with spare capacity. They form the \(s\) side of a cut whose pipes are all full. (Sometimes a path must also undo earlier flow: see the stretch.)

Watch one: the network in the figure

Push 4 along \(s \to A \to C \to t\), 3 along \(s \to A \to D \to t\) and 2 along \(s \to B \to D \to t\). The flow is 9, and \(A \to C\), \(A \to D\), \(D \to t\) are full.

Now every path is blocked. From \(s\) you can still reach \(A\) and \(B\), and from \(B\) you reach \(D\). You cannot reach \(C\) or \(t\). So the cut has \(s, A, B, D\) on one side, and the pipes crossing it are \(A \to C\) and \(D \to t\): \(4 + 5 = 9\).

Flow 9, cut 9. Neither can be improved.

Push the flow yourself and watch the cut appear: mathdetours.com/demos/maxflow.html.

Your turn

  1. In the figure, find the capacity of the cut whose \(s\) side is (a) \(s\) alone, (b) \(s, A, B\), (c) everything except \(t\). Check that none is below 9.
  2. You may widen one pipe in the figure by 1. Which pipes raise the max flow to 10? Why does widening \(s \to A\) do nothing?
  3. Replace \(D \to t\) by a pipe of capacity 9. Find the new max flow, and a cut that proves it is the max.
  4. Draw this network: \(s \to A\) 5, \(s \to B\) 7, \(A \to B\) 3, \(A \to t\) 4, \(B \to t\) 6. (a) Find the capacity of the cut with \(s\) and \(B\) on the source side. One pipe crosses between the two sides and still does not count. Which, and why? (b) Find the max flow and a min cut.

Stretch: a wrong turn

Pipes \(s \to A\), \(s \to B\), \(A \to B\), \(A \to t\), \(B \to t\) all have capacity 1. Push 1 along \(s \to A \to B \to t\). Show that no path with spare capacity is left, yet the max flow is 2. What extra move must the method allow?

Answers

  1. (a) \(s \to A\) and \(s \to B\): \(8 + 6 = 14\). (b) \(A \to C\), \(A \to D\), \(B \to D\): \(4 + 3 + 5 = 12\). (c) \(C \to t\) and \(D \to t\): \(6 + 5 = 11\). All are at least 9, as they must be.
  2. \(A \to C\) or \(D \to t\), the two pipes in the min cut. Either one raises that cut to 10, every other cut is already 11 or more, and one more unit fits: along \(s \to A \to C \to t\), or along \(s \to B \to D \to t\). Widening \(s \to A\) leaves the cut \(A \to C\), \(D \to t\) at 9, so the flow cannot pass 9. A pipe outside the bottleneck is not the problem.
  3. 12. One flow: \(s \to A\) 7, \(s \to B\) 5, \(A \to C\) 4, \(A \to D\) 3, \(B \to D\) 5, \(C \to t\) 4, \(D \to t\) 8. The cut with \(s, A, B\) on the source side has capacity \(4 + 3 + 5 = 12\), so no flow can beat 12. The bottleneck has moved.
  4. (a) The pipes leaving the source side are \(s \to A\) and \(B \to t\): \(5 + 6 = 11\). The pipe \(A \to B\) runs from the sink side back to the source side. It carries nothing across towards \(t\), so it does not count. (b) Push 4 along \(s \to A \to t\) and 6 along \(s \to B \to t\): flow 10. The cut with \(s, A, B\) on the source side is \(A \to t\) and \(B \to t\): \(4 + 6 = 10\). So the max flow is 10.

Stretch. After the push, \(s \to A\) and \(B \to t\) are full. The only pipe out of \(s\) with spare capacity is \(s \to B\), and from \(B\) the only way on is the full pipe \(B \to t\). So the method is stuck at 1. But \(s \to A \to t\) and \(s \to B \to t\) together carry 2, and the cut around \(s\) is 2, so 2 is the max. The fix: a path may also cancel flow in a pipe by going against it. Here \(s \to B\), back along \(A \to B\) (cancelling its 1), then \(A \to t\). With that move allowed, being stuck always gives a min cut.

← PreviousNext: Where should the penalty taker aim? →