Cuts, labelling procedure and max-flow min-cutEdexcel A-Level Further Maths: Revision notes

A network of directed arcs has a source S, where flow starts, and a sink T, where it ends. Each arc has a capacity, the greatest flow it can carry. A feasible flow obeys two rules: on every arc, $0\le\text{flow}\le\text{capacity}$; and at every other vertex, flow in = flow out. The value of a flow is the amount leaving S, which equals the amount entering T. An arc is saturated when its flow equals its capacity.

A cut divides the vertices into two sets, $X$ containing the source S and $Y$ containing the sink T. 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. Example: arcs SA 7, SB 5, AB 3, AT 4, BT 6. For $X=\{S,A\}$, $Y=\{B,T\}$ the arcs from $X$ to $Y$ are SB, AB and AT: capacity $5+3+4=12$. For $X=\{S,A,B\}$, $Y=\{T\}$ the capacity is AT $+$ BT $=4+6=10$. Every flow is at most the capacity of every cut, because all the flow must cross from $X$ to $Y$. So the value of the flow is at most the minimum cut.

The labelling procedure finds a flow-augmenting route from S to T and the amount by which to increase the flow. Each arc carries two numbers. The arrow in the same direction as the arc shows the amount by which the flow can be increased (capacity $-$ flow). The arrow in the opposite direction shows the amount by which the flow could be reduced (the current flow). Starting from S, label vertices that can be reached using an arc with spare capacity (forward) or an arc with flow that can be reduced (backward). If T is labelled, trace back a route. The flow increases by the smallest number along the route: add it on forward arcs and subtract it on backward arcs. Repeat until T cannot be labelled.

Arcs SA 9, SB 7, AB 4, AC 5, BC 6, BT 4, CT 8 with flow SA 5, SB 3, AB 2, AC 3, BC 3, BT 2, CT 6 (value 8). Route S, A, C, T: spare capacities $4$, $2$, $2$, so the flow increases by $2$ to $10$. Next, S, B, T has spare capacity $4$ on SB and $2$ on BT, giving $2$ more: value $12$. Now BT and CT are both saturated, and every route to T is blocked. The cut $X=\{S,A,B,C\}$, $Y=\{T\}$ has capacity $4+8=12$, equal to the flow.

Max-flow min-cut theorem: the maximum value of a flow in a network equals the capacity of the minimum cut. To prove that a flow is maximum, find a cut whose capacity equals the value of the flow. Because no flow can exceed any cut, the flow cannot be larger, so it is maximum and the cut is a minimum cut. The arcs in the cut from $X$ to $Y$ are all saturated, and arcs from $Y$ to $X$ carry no flow. The theorem also tells you where to improve a network: increasing the capacity of an arc that is not in the minimum cut does not raise the maximum flow.