= Solution
{c}
<flow conservation> determines the unspecified initial arcs:
$$
(x_{12},x_{13},x_{24},x_{34},x_{35},x_{46},x_{56})
=(1,3,1,2,1,3,1).
$$
Every entry respects capacity, and the initial value is four. In the <residual network> take the <augmenting path>
$$
1\longrightarrow2\longrightarrow4
\longrightarrow3\longrightarrow5\longrightarrow6.
$$
The step $4\to3$ is the reverse residual arc of the used arc $3\to4$. 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 are
$$
\boxed{(x_{12},x_{13},x_{24},x_{34},x_{35},x_{46},x_{56})
=(2,3,2,1,2,3,2).}
$$
Their 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.
\Image[/past-exam-of-the-probability-statistics-and-options-i-course-of-the-university-of-oxford/2007-residual-flow.png]
{title=One unit of residual rerouting cancels flow on 34 and raises the total from four to five}
Back to article page
