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

A maximum flow problem specifies a finite directed flow network, a source $s$, a sink $t$, and nonnegative arc capacities. A feasible flow assigns $0\le f_e\le c_e$ to each arc, with incoming flow equal to outgoing flow at each vertex other than $s,t$. The objective is to maximize the net flow leaving $s$, equivalently entering $t$.

The Ford-Fulkerson algorithm starts with zero flow. Its residual network has a forward arc of capacity $c_e-f_e$ and a reverse arc of capacity $f_e$ for each original arc. If an $s$–$t$ path has positive residual capacities, augment by their minimum: increase flow along forward arcs and decrease it along reverse arcs. This preserves capacity bounds and conservation, and increases the flow value by that positive bottleneck. Repeat until there is no augmenting path.

For rational capacities, choose a positive integer $D$ clearing every denominator. Initially all flows and residual capacities are integer multiples of $1/D$, and augmentation preserves that property. Every augmentation therefore increases the flow value by at least $1/D$. The flow value is bounded above by the sum of capacities of arcs leaving $s$. Thus only finitely many augmentations can occur, independently of how the augmenting paths are chosen.

To see why termination supplies a maximum, let $S$ consist of vertices reachable from $s$ in the final residual network. The sink is not in $S$. Each original arc from $S$ to its complement is saturated; each original arc entering $S$ has zero flow, since otherwise its reverse residual arc would leave $S$. The resulting flow value equals the capacity of this cut. No feasible flow exceeds a cut capacity. Hence the algorithm terminates at a maximum flow for rational capacities, proving the relevant max-flow min-cut theorem conclusion as well.

An extreme point of a convex set cannot be written as a nontrivial convex combination of two distinct members. If a permutation matrix $P=\theta B+(1-\theta )C$ with $0<\theta <1$ and $B,C$ doubly stochastic, each zero entry of $P$ forces the corresponding entries of $B,C$ to be zero by nonnegativity. The unique possible nonzero entry in each row must then be one by the row sum. Thus $B=C=P$, proving that every permutation matrix is extreme.

Conversely, let $A$ be a doubly stochastic matrix that is not a permutation matrix. At least one entry lies strictly between zero and one. Form a bipartite graph whose two vertex classes are rows and columns, with edges precisely at these fractional entries. Every incident row has at least two fractional entries: a single fractional entry, with all other entries zero or one, could not give row sum one. The same holds for columns.

A finite nonempty graph whose incident vertices all have degree at least two contains a cycle. In a bipartite graph that cycle has even length. Assign alternating signs $+1,-1$ to its entries, giving a nonzero matrix $D$ with every row and column sum zero. Choose $\epsilon >0$ smaller than the distance of each cycle entry from both zero and one. Then $A+\epsilon D$ and $A-\epsilon D$ remain doubly stochastic matrices, are distinct, and satisfySo $A$ is not extreme. ThereforeThis alternating-cycle perturbation of a doubly stochastic matrix proves the extreme-point part of the Birkhoff-von Neumann theorem directly.