Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 4 / 20H (Optimisation)

A finite flow network is a directed graph with distinguished source $s$, sink $t$, and nonnegative finite flow network edge capacities $c_{ij}$ on its directed edges. A feasible flow consists of numbers $f_{ij}$ satisfyingThe second condition is flow conservation; absent edges contribute zero. The strength of a flow is its net outflow from the source,which equals net inflow to the sink by summing flow conservation over the other vertices. The maximum flow problem isNo assumption that a capacity-saturating flow at the source is feasible downstream is made. On a finite network a maximum exists, because the constraints define a nonempty compact set of edge flows and the objective is continuous.

The Ford-Fulkerson algorithm starts with zero flow. For each original edge $i\to j$, the residual network has a forward edge with residual capacity $c_{ij}-f_{ij}$ and a reverse edge with residual capacity $f_{ij}$. Distinguish these labelled residual edges if the original graph has antiparallel edges. While there is a source-to-sink augmenting path with positive residual capacities, increase the flow by the minimum residual capacity along it, adding on forward edges and subtracting on reverse edges. This preserves capacity bounds and flow conservation and increases the strength of a flow by that positive bottleneck.

A cut of a flow network is a partition $(S,V\setminus S)$ with $s\in S$, $t\notin S$, of capacity $c(S)={\sum }_{i\in S,j\notin S}{c}_{ij}$. Summing flow conservation gives $|f|=f(S,V\setminus S)-f(V\setminus S,S)\le c(S)$. The max-flow min-cut theorem statesWhen no augmenting path remains, take $S$ to be the vertices reachable from $s$ in the residual network. Every original outgoing edge of this cut of a flow network is saturated and every incoming edge has zero flow; otherwise a positive residual edge would leave $S$. Thus $|f|=c(S)$, certifying optimality and the theorem. For general finite real capacities, one can also apply this argument to an existing maximum: it cannot admit an augmenting path.

With integer capacities, each augmentation increases the value by at least one, so the Ford-Fulkerson algorithm terminates. Rational capacities can be scaled to integers. Arbitrary path choices with irrational capacities need not terminate; the existence theorem does not justify claiming finite termination in that generality. The given network has integer capacities, so this caveat does not obstruct its computation.

Reading the arrows directly from the original PDF gives, in particular, $c\to a$ and $e\to d$. Starting from zero flow, use the following augmenting paths and bottlenecks, in order:

Each path is available in the current residual network. The resulting nonzero edge flows areThe flows on $c\to a$ and $e\to d$ are zero. Capacity constraints and flow conservation hold at each interior vertex; net source outflow is $6+8+5=19$.

Take $S=\{s,a,b,c\}$. Its outgoing edges are $a\to d$, $c\to d$, $b\to e$, $c\to e$, with total capacity $6+2+5+6=19$. Thus the matching flow and cut of a flow network certificates giveThese are also exactly the source-reachable vertices in the final residual network. The original drawing below labels each edge by flow/capacity; the highlighted edges realise the minimum cut of a flow network.

No: the increase need not equal $\epsilon$. For a simple counterexample, use two edge-disjoint paths $s\to a\to t$ and $s\to b\to t$, with all four capacities equal to one. Initially the maximum flow is $2$. After every capacity increases to $1+\epsilon$, send $1+\epsilon$ down each path; a source cut of a flow network bounds the total by the same value. HenceMore generally, by the max-flow min-cut theorem, if $m(S)$ is the number of directed edges leaving a cut of a flow network, uniform capacity perturbation of a flow network givesThe number of outgoing edges, and possible changes of the minimising cut of a flow network, determine the increase. If the question were interpreted as asking for an increase of at least $\epsilon$, this does hold when the graph has a directed $s$-to-$t$ path, because then every cut of a flow network has $m(S)\ge 1$. Without such a path a zero-edge cut of a flow network remains of capacity zero and the maximum can stay zero. Thus neither an exact increment nor an unconditional positive increment follows merely by adding the same amount to every edge capacity.