5. Figure 3
\includegraphics[max width=\textwidth, alt={}, center]{f4258313-53d5-4a88-abf9-c0c7926770e4-6_584_992_287_589}
Figure 3 shows a capacitated directed network. The number on each arc is its capacity.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{f4258313-53d5-4a88-abf9-c0c7926770e4-6_585_979_1101_561}
\end{figure}
Figure 4 shows a feasible initial flow through the same network.
- Write down the values of the flow \(x\) and the flow \(y\).
- Obtain the value of the initial flow through the network, and explain how you know it is not maximal.
- Use this initial flow and the labelling procedure on Diagram 1 in this answer book to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
- Show your maximal flow pattern on Diagram 2.
- Prove that your flow is maximal.