Past exam of the mathematics course of the University of Cambridge / 2024 / ib / Paper 3 / 19H / b

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