= Solution
Label the two intermediate vertices $1,2$. The four outer edges have capacity $M$ and the middle edge has capacity one. The cut separating $s$ from the other vertices has capacity $2M$, and the two paths $s\to1\to t$ and $s\to2\to t$ can each carry $M$. Thus the <maximum flow> is $2M$.
A fast run of the <Ford-Fulkerson algorithm> chooses those two direct paths and augments by $M$ on each: it terminates in \b[two augmentations]. One augmentation cannot suffice, because every initial path has bottleneck at most $M$.
For a run with $M+1$ augmentations, first choose $s\to1\to2\to t$ and augment by one. The middle edge then has net <flow> $1$ from $1$ to $2$. Its reverse residual capacity is $1-(-1)=2$, not one. Alternate crossing paths, next $s\to2\to1\to t$, then $s\to1\to2\to t$, and so on. Each of the next $M-1$ augmentations has bottleneck two. More explicitly, after $k$ crossing augmentations, $1\leq k\leq M$, the total <flow> is $2k-1$, and the outer-edge <flow> totals on the pairs $(s1,2t)$ and $(s2,1t)$ are $k$ and $k-1$ in one order or the other. The middle net <flow> is $\pm1$. The next opposite crossing path uses the less-loaded outer pair and has reverse-middle capacity two. Until $k=M$, its outer residual capacities are at least two.
After these $M$ augmentations, one outer pair is full and the other has one unit left. One final opposite crossing augmentation of one reaches $2M$. The total amounts are $1$, then $M-1$ copies of $2$, then $1$, giving \b[exactly $M+1$ augmentations]. For $M=1$ the middle block is empty and this gives two augmentations as well. These are explicit requested path-choice histories. In an undirected network, $M+1$ need not be a bound on every possible history: for $M=2$, choosing the crossing path, the two direct paths, and then the crossing path again gives four successive unit augmentations.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2005/iii/paper-40-augmenting-paths.png]
{title=Direct and crossing flow augmentations, including reverse residual capacity two on the middle edge}
For a general undirected network, let $y_{ij}=x_{ij}-x_{ji}$ be the antisymmetric net <flow>. Feasibility gives $|y_{ij}|\leq c_{ij}$, so the directed <residual network> has nonnegative capacities $c'_{ij}=c_{ij}-y_{ij}$. For any cut $S$ with $s\in S$, $t\notin S$, conservation at the internal vertices gives
$$
\sum_{i\in S,j\notin S}y_{ij}=f.
$$
Thus its outgoing residual cut capacity is
$$
C'(S)=\sum_{i\in S,j\notin S}(c_{ij}-y_{ij})=C(S)-f.
$$
The subtracted <flow> value is the same for every cut. Taking the minimum and applying the <max-flow min-cut theorem> to the original and <residual networks> proves the <residual maximum flow is the remaining optimality gap> identity
$$
\boxed{f'=f^*-f}.
$$
Suppose now $f'>0$, and let $U$ consist of vertices reachable from $s$ through residual arcs of capacity at least $f'/m$. If $t\notin U$, every outgoing arc from $U$ has capacity strictly below $f'/m$, since its head would otherwise be reachable. At most $m$ original undirected edges cross this cut, and each supplies exactly one outgoing directed arc. Hence $C'(U)<m(f'/m)=f'$, contradicting the residual minimum-cut value $f'$. Therefore $\boxed{t\in U}$, and a <widest augmenting path> has bottleneck at least $f'/m$. When $f'=0$, the current <flow> is already optimal and no such path is needed.
Let $F_k$ be the remaining residual <maximum flow> after $k$ augmentations of the modified rule, starting from zero <flow>. Its chosen widest path increases the <flow> by at least $F_k/m$, so
$$
F_{k+1}\leq\left(1-\frac1m\right)F_k,
\qquad
\boxed{F_k\leq\left(1-\frac1m\right)^k f^*}.
$$
This is the <geometric convergence of widest-path augmentation>. For $m\geq2$, $F_k\leq e^{-k/m}f^*$. Starting from zero with <integer> capacities keeps all <flow> values and residual optimality gaps <integer>. Thus $k>m\ln f^*$ makes $F_k<1$ and hence $F_k=0$, giving termination in $\boxed{O(m\log f^*)}$ augmentations for $f^*\geq2$. If $f^*=1$, one positive <integer> augmentation suffices; if $f^*=0$, none is required. A uniform statement is $O(m\log(1+f^*))$. With $m=1$, a nonzero <flow> is also completed in one augmentation, consistent with the recurrence's zero contraction factor.
Back to article page
