Solution

ID: past-exam-of-the-probability-statistics-and-options-i-course-of-the-university-of-oxford/2007/s/2/a/solution

flow conservation determines the unspecified initial arcs:
Every entry respects capacity, and the initial value is four. In the residual network take the augmenting path
The step is the reverse residual arc of the used arc . Its use cancels some existing flow rather than sending new physical flow on a nonexistent original arc. The residual capacities along the path are , so augment by their minimum, one.
The resulting original-arc flows are
Their value is five. The cut separating the sink from all other nodes has capacity . Every feasible flow is bounded by this cut capacity, so the value-five flow is optimal.
Figure 1.
One unit of residual rerouting cancels flow on 34 and raises the total from four to five
. Details.

New to topics? Read the docs here!