Past exam of the mathematics course of the University of Cambridge / 2024 / ib / Paper 3 / 19H (Optimisation)

A feasible flow assigns $f_{ij}$ to each directed edge so thatand inflow equals outflow at every vertex other than the source and sink. Its value $|f|$ is the net outflow from the source. For a set $S$ containing the source but not the sink, the associated cut has capacityThe max-flow min-cut theorem states

For every flow and cut, conservation at vertices inside $S$ givesThis proves the weak inequality.

A maximum flow exists because the feasible-flow polytope is nonempty, closed, and bounded. Form its residual graph: a forward edge has residual capacity $C_{ij}-f_{ij}$, and a reverse edge has residual capacity $f_{ij}$. If the residual graph contained a source-to-sink path, augmenting by the smallest positive residual capacity on that path would increase the flow, contradicting maximality.

Let $S$ be the vertices reachable from the source in the residual graph. The sink is not in $S$. Every original edge from $S$ to its complement is saturated, and every original edge from the complement into $S$ carries zero flow; otherwise the appropriate residual edge would make its other endpoint reachable. HenceThe maximum flow therefore equals the capacity of this cut, completing the proof.

Label the seven black intermediate vertices, from left to right and top to bottom within each column, by $a,b,c,d,e,f,g$: thus $a$ is directly below $r$, $b$ is the lower-left vertex, $c,d$ are the next upper and lower vertices, $e$ is the middle-right vertex, and $f,g$ are the upper-right and lower-right vertices.

For $x=4$, the following nonzero edge flows are feasible:Their value is $9$. The cut with source side $\{s\}$ has capacityBy the max-flow min-cut theorem,

Two cuts give the upper boundsfrom the source cut, andfrom the cut whose source side isThe latter cut crosses the edges $ce,de,dg,ft$, of respective capacities $3,3,2,6$.

At $x=0$, a flow of value $5$ isAt $x=9$, a flow of value $14$ is given byFor $0\le x\le 9$, take the convex combination of these two flows with weights $1-x/9$ and $x/9$. It is feasible at capacity $x$ and has value $5+x$. For $x\ge 9$, the second flow remains feasible and has value $14$. The two cut bounds are therefore attained, and the parametric maximum flow with one source capacity is