7.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-3_526_903_1455_575}
\end{figure}
Figure 1 shows a capacitated directed network. The number on each arc is its capacity.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-3_499_967_2231_548}
\end{figure}
Figure 2 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 below to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
\section*{Diagram 1}
\includegraphics[max width=\textwidth, alt={}, center]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-4_1920_1175_742_450}
d) Show your maximal flow pattern on Diagram 2.
\section*{Diagram 2}
\includegraphics[max width=\textwidth, alt={}, center]{343fdcef-660e-4e8c-bd9c-a7f929dc668e-5_679_1102_315_479}
(2) - Prove that your flow is maximal.
(2)
(Total 13 marks)