8.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 6}
\includegraphics[alt={},max width=\textwidth]{19cfdf0b-6be6-4f44-bfae-2b6bf592cfd8-8_815_1434_240_322}
\end{figure}
Figure 6 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as 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.
Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
- Complete the initial labelling procedure in Diagram 2.
- Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow, and state the maximal flow.
- Show a maximal flow pattern on Diagram 3.
- Prove that your flow is maximal.
- Describe briefly a situation for which this network could be a suitable model.