6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{0af7fd3e-68af-41fc-883b-3bc2589035bb-7_816_1138_178_459}
\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.
- State the value of the initial flow.
- On Diagram 1 and Diagram 2 in the answer book, add a supersource S and a supersink T . On Diagram 1, show the minimum capacities of the arcs you have added.
- Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values on the arcs to S and T and on \(\operatorname { arcs } \mathrm { CD }\), DE , DG , FG, FI and GI.
- Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
- Show your maximum flow on Diagram 3 in the answer book.
- Prove that your flow is maximal.