Past exam of the mathematics course of the University of Cambridge / 2005 / ib / Paper 4 / 20D / Solution

Start with a feasible network flow, meaning capacity bounds and flow conservation at every vertex other than source and sink. Its residual network has, for an arc with capacity $c$ and current flow $f$, a forward residual capacity $c-f$ and a reverse residual capacity $f$. A reverse arc allows earlier flow to be cancelled. The Ford-Fulkerson algorithm repeatedly finds a residual source-to-sink augmenting path, takes the smallest residual capacity $\delta$ on it, and augments by $\delta$, increasing forward flows and decreasing reverse flows as appropriate. Feasibility is preserved and the total flow increases by $\delta$.

For rational capacities and initial flows, choose one common denominator $D$ and scale all quantities by $D$. Every residual capacity and augmentation is then integral; each augmentation increases the integer-valued flow by at least one. The flow value is bounded by the finite sum of capacities out of the source, so termination occurs after finitely many augmentations. When no residual path remains, let $U$ be the vertices reachable from the source. Every original arc leaving $U$ is saturated and every original arc entering $U$ carries zero flow, or its reverse arc would extend reachability. Conservation then makes the flow value equal to the capacity of the cut $(U,U^c)$. Every feasible flow is bounded by that cut capacity. Thus the terminating flow is globally optimal, proving the needed max-flow min-cut theorem conclusion.

For the given directed graph, begin at zero. One valid sequence of augmentations is:

Each amount is the current path bottleneck. The resulting nonzero arc flows areevery other arc has zero flow. Directly summing incoming and outgoing flows verifies conservation, and every displayed flow is at most its printed capacity. A minimum-cut certificate isIts only outgoing arcs are $SD$, $EK$, $HJ$ and $BT$, with capacities $10,6,8,6$. ThereforeThe matching feasible flow and cut prove optimality independently of the augmenting-path choices.