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

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