Past exam of the probability, statistics and options I course of the University of Oxford / 2007 / S / 2

flow conservation determines the unspecified initial arcs:Every entry respects capacity, and the initial value is four. In the residual network take the augmenting pathThe step $4\to 3$ is the reverse residual arc of the used arc $3\to 4$. Its use cancels some existing flow rather than sending new physical flow on a nonexistent original arc. The residual capacities along the path are $2,1,2,2,1$, so augment by their minimum, one.

The resulting original-arc flows areTheir value is five. The cut separating the sink from all other nodes has capacity $c_{46}+c_{56}=3+2=5$. Every feasible flow is bounded by this cut capacity, so the value-five flow is optimal.

Start the augmenting-path algorithm from the zero flow. With integer capacities and an integer electric current flow, every residual capacity is an integer, so a path bottleneck is a positive integer. Augmenting by it preserves integrality and increases the flow value by at least one. The value is bounded by the finite total capacity leaving the source, so the process terminates. At termination there is no augmenting path, hence the flow is maximum by the max-flow min-cut theorem. Its value is an integer.

Equivalently a minimum cut has capacity equal to the sum of integer arc capacities, so the maximum flow value equals an integer. Thus integer capacities guarantee an integer optimal volume, even though arbitrary feasible real-valued flows need not themselves have integer entries.