6.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e0c66144-9e34-42fc-9f40-a87a49331483-07_719_1313_246_376}
\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.
- 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 in the answer book by entering values along the new arcs from S to T , and along \(\operatorname { arcs } \mathrm { S } _ { 1 } \mathrm {~B}\) and \(\mathrm { AT } _ { 1 }\)
- 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.