Augmenting flows and refinementsAQA A-Level Further Maths: Revision notes

Given a feasible flow, you improve it by finding a flow-augmenting route from $S$ to $T$. Along each arc used in its own direction (a forward arc) the spare capacity is $\text{capacity}-\text{flow}$. An arc may also be used backwards: if arc $AB$ carries flow $f$, then travelling from $B$ to $A$ is allowed and can cancel up to $f$ units of it. The amount by which you can increase the flow is the smallest spare capacity (or backward flow) along the route, the bottleneck. After augmenting, update every arc: add the amount on forward arcs, subtract it on backward arcs. Example: arc $SA$ with capacity 6 and flow 4 has forward spare capacity 2.

Start with any feasible flow (for example zero). Repeatedly find a flow-augmenting route and increase the flow by its bottleneck. Stop when no augmenting route exists. At that point, the nodes reachable from $S$ by forward arcs with spare capacity and backward arcs with positive flow form the set $X$; every arc leaving $X$ is saturated and every arc entering $X$ carries no flow, so the flow equals the capacity of the cut $X|Y$. By the max-flow min-cut theorem the flow is maximal. Example: arcs $SA$ 6, $SB$ 3, $AB$ 5, $AT$ 3, $BT$ 4 with flow 4 on $S\to A\to B\to T$. Route $S\to A\to T$ adds 2 (total 6). Route $S\to B\to A\to T$, using $AB$ backwards, adds 1 (total 7). The cut $\{S,A,B\}|\{T\}$ has capacity $3+4=7$, so 7 is the maximum.

Some arcs have a lower capacity as well as an upper capacity, written $[l,u]$: the flow must satisfy $l\leq f\leq u$. A flow is feasible only if every arc meets its limits and conservation holds at every intermediate node. Find a feasible flow first (it may need adjusting by trial), then augment it. On an arc with flow $f$, the forward spare capacity is $u-f$ and the amount that can be cancelled by a backward move is $f-l$. For a cut $X|Y$, the capacity is $\sum u$ for arcs from $X$ to $Y$ minus $\sum l$ for arcs from $Y$ to $X$. Lower capacities also set a minimum flow: for example, if $AT\geq4$ and $BT\geq3$ into the sink, every feasible flow has value at least 7.

Sometimes a node, not an arc, limits the flow, for example a depot that can handle at most 6 units per hour. Replace the node $B$ by two nodes $B_1$ and $B_2$ joined by an arc $B_1\to B_2$ whose capacity is the restriction. Every arc that entered $B$ now enters $B_1$, and every arc that left $B$ now leaves $B_2$. The new arc is then treated like any other, and may appear in a minimum cut. Example: with $SA$ 8, $SB$ 7, $AB$ 4, $AC$ 5, $BC$ 6, $BT$ 5, $CT$ 9, the unrestricted maximum flow is 14. Limiting $B$ to 6 gives a minimum cut $\{AC,B_1B_2\}$ of capacity $5+6=11$.

Once the maximum flow is known you can evaluate changes. The minimum cuts show where the bottleneck is. Raising an arc's capacity helps only if that arc is in every minimum cut, and then the flow rises by the increase or until another cut becomes the minimum, whichever is smaller. Example: raising a capacity by 2 may raise the maximum flow by only 1 if another cut has capacity one more than the current minimum. Always check the next smallest cut before you give the new maximum, and state conclusions in context with units.