= Solution
Two cuts give the upper bounds
$$
\delta^*(x)\leq x+5
$$
from the source cut, and
$$
\delta^*(x)\leq14
$$
from the cut whose source side is
$$
S=\{s,r,a,b,c,d,f\}.
$$
The latter cut crosses the edges $ce,de,dg,ft$, of respective capacities $3,3,2,6$.
At $x=0$, a flow of value $5$ is
$$
sb=bd=5,
\qquad de=et=3,
\qquad dg=gt=2.
$$
At $x=9$, a flow of value $14$ is given by
$$
\begin{array}{c|rrrrrrrrrrrrr}
\text{edge}&sr&sb&rc&ra&ac&bd&cf&ce&de&dg&et&ft>\\ \hline
\text{flow}&9&5&6&3&3&5&6&3&3&2&6&6&2.
\end{array}
$$
For $0\leq x\leq9$, 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\geq9$, 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
$$
\boxed{
\delta^*(x)=\min\{x+5,14\}
=\begin{cases}
x+5,&0\leq x\leq9,\\
14,&x\geq9.
\end{cases}}
$$
Back to article page
