Past exam of the mathematics course of the University of Cambridge / 2019 / ib / Paper 4 / 20H / b

Starting from zero, one valid run of the Ford-Fulkerson algorithm augments alongThe resulting nonzero edge flows areand they obey every capacity constraint and every flow-conservation equation. The flow value is

After these augmentations, the vertices reachable from $S$ in the residual network areThe edges leaving this set are $S\to b$, $a\to d$, and $c\to e$, with capacities $3$, $1$, and $4$. HenceThe flow in part (i) has the same value, so the max-flow min-cut theorem proves that it is maximum and that this cut is minimum.

The maximum flow is not unique. For any $x\in [1,2]$, setand split the flow from $b$ byFlow conservation then requiresAll capacities are respected precisely throughout the displayed interval, and every member of this one-parameter family has value $8$. For example, $x=1$ and $x=2$ give distinct maximum flows.