Multiple sources and sinks, restricted capacities and optimal flowEdexcel A-Level Further Maths: Revision notes

A network may have several sources (for example, several depots) and several sinks (several shops). Add a super source $S$ with an arc to each source, and a super sink $T$ with an arc from each sink. Then solve as a normal single-source, single-sink problem. The capacity of each new arc is the supply of that source, or the demand of that sink. If a source can supply any amount, give its arc infinite capacity (or a number larger than any possible flow). Example: depots P (supply 9) and Q (supply 6): arcs SP of capacity 9 and SQ of capacity 6.

Sometimes a vertex $C$ can handle only a limited total flow, say $7$. Split it into two vertices, $C_{\text{in}}$ and $C_{\text{out}}$, joined by an arc $C_{\text{in}}C_{\text{out}}$ of capacity $7$. Every arc that ended at $C$ now ends at $C_{\text{in}}$, and every arc that started at $C$ now starts at $C_{\text{out}}$. All flow through $C$ must use the new arc, so the throughput is at most $7$. The restriction counts as an arc in cuts: for example, the cut $\{S,A,B,C_{\text{in}}\}$ includes the arc $C_{\text{in}}C_{\text{out}}$. Do not simply reduce the capacity of one arc: if $C$ has several outgoing arcs, the others stay unrestricted.

Some arcs must carry at least a minimum flow as well as at most a maximum. Write each arc as $[\text{lower}, \text{upper}]$. A flow is feasible if on every arc $\text{lower}\le\text{flow}\le\text{upper}$ and flow in equals flow out at each intermediate vertex. Labelling with lower capacities: the arrow in the direction of the arc shows upper $-$ flow (how much it can increase); the arrow in the opposite direction shows flow $-$ lower (how much it can decrease). Start from a feasible flow and augment as before; the flow never drops below any lower capacity.

For a cut with sets $X$ (containing S) and $Y$ (containing T): $\text{capacity of cut}=\sum(\text{upper capacities of arcs from }X\text{ to }Y)-\sum(\text{lower capacities of arcs from }Y\text{ to }X).$ The arcs from $Y$ to $X$ matter now: their minimum flows must return across the cut, which uses up some of the flow that can cross forwards. With all lower capacities zero, this is the earlier rule. Example: arcs SA [1,11], BT [2,8] go out of $X=\{S,B\}$, and AB [3,9] comes into $X$ from $Y$: capacity $11+8-3=16$.

To find the optimal (maximum) flow with lower capacities: start from any feasible flow, augment with the labelling procedure until T cannot be labelled, then confirm with a cut whose capacity equals the flow value (max-flow min-cut). To improve the flow, change an arc in the minimum cut. Raising the upper capacity of an arc from $X$ to $Y$ in the minimum cut, or lowering the lower capacity of an arc from $Y$ to $X$, increases the cut capacity. Changes to arcs elsewhere do nothing. The gain stops when another cut becomes the smallest, so compare with the next-smallest cut capacity.