Flows, cuts and the max-flow min-cut theoremAQA A-Level Further Maths: Revision notes

A network flow problem is modelled by a network of directed arcs. Each arc has a capacity, the greatest amount that can travel along it in the direction shown. Flow enters at a source $S$ and leaves at a sink $T$. A feasible flow satisfies two rules: on every arc the flow is at most the capacity (and not negative), and at every intermediate node the total flow in equals the total flow out (conservation). The value of a flow is the total leaving the source, which equals the total arriving at the sink. An arc is saturated when its flow equals its capacity. Example: if arcs carrying 6 and 5 units enter a node and one outgoing arc carries 7, the other outgoing arc must carry $6+5-7=4$.

A cut divides the nodes into two sets, $X$ containing the source and $Y$ containing the sink. The capacity of the cut is the sum of the capacities of the arcs directed from $X$ to $Y$. Arcs directed from $Y$ to $X$ are not counted, because they carry no flow from the source side to the sink side. Example: with arcs $SA$ 7, $SB$ 6, $AB$ 2, $AT$ 4, $BT$ 8, the cut $\{S,B\}|\{A,T\}$ has capacity $SA+BT=7+8=15$; the arc $AB$ is ignored because it goes from $A$ into $B$. Every unit of flow from $S$ to $T$ must cross every cut, so the value of any flow is at most the capacity of any cut. The minimum cut is the cut of smallest capacity.

The maximum flow-minimum cut theorem states that in any network the value of the maximum flow equals the capacity of the minimum cut. In practice you use it in two ways. To prove a flow is maximal, find a cut whose capacity equals the flow's value: no flow can exceed that cut, so the flow is a maximum and the cut is a minimum. To find the maximum flow, find the minimum cut by listing cuts systematically, for example by growing the source set one node at a time. The arcs of a minimum cut are the bottleneck: they are all saturated in a maximum flow. Raising the capacity of an arc increases the maximum flow only if the arc is in every minimum cut.

Some problems have several sources or several sinks. Add a supersource $S$, with a directed arc from $S$ to each real source, and/or a supersink $Z$, with a directed arc from each real sink to $Z$. The capacity of each added arc is the most that source can supply or that sink can absorb. If no limit is given the arc is given unlimited capacity. The problem then has one source and one sink, and the usual methods apply. Example: factories able to supply 10 and 8 units become arcs $SF_1$ (10) and $SF_2$ (8); shops able to take 8 and 6 become arcs $T_1Z$ (8) and $T_2Z$ (6).

Arcs: $SA$ 10, $SB$ 6, $AB$ 3, $AC$ 5, $BC$ 4, $BT$ 2, $CT$ 9. Cuts: $\{S\}|\{A,B,C,T\}$ has capacity $10+6=16$; $\{S,A\}$ has $6+3+5=14$; $\{S,A,B\}$ has $5+4+2=11$; $\{S,A,B,C\}$ has $2+9=11$. The minimum is 11, so the maximum flow is 11. In context, if the arcs were pipes in litres per second, this says the system can deliver at most 11 litres per second, and the arcs $AC$, $BC$ and $BT$ are the bottleneck. To interpret a cut, say what it means: all flow must pass through those arcs, so their combined capacity limits the whole network.