8.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0fdc5a3c-97e7-46e3-a57c-45a13755f0e5-9_1131_1653_242_207}
\captionsetup{labelformat=empty}
\caption{Figure 6}
\end{figure}
Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
- State the value of the initial flow.
(1) - State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
(2)
Diagram 3 in the answer book shows the labelling procedure applied to the above network. - Using Diagram 3, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow.
(5) - Prove that the flow is now maximal.