5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{d708ce08-4ea3-4a13-a39c-00efcde32c57-5_707_969_237_523}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
- Add a supersource, S , and a supersink, T , and corresponding arcs to Diagrams 1 and 2, in the answer book.
- Enter the flow value and appropriate capacity on each of the arcs you have added to Diagram 1.
- Complete the initialisation of the labelling procedure on Diagram 2 by entering values along the new arcs from \(S\) and \(T\), and along \(A B , A D\) and \(D _ { 2 }\).
- Hence use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
- Draw a maximal flow pattern on Diagram 3 in the answer book.
- Prove that your flow is maximal.