3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{bbdfa492-6578-484a-a0b5-fcdb78020b83-03_801_1728_269_166}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Alexa is monitoring a system of pipes through which fluid can flow from the source, S , to the sink, T . Currently, fluid is flowing through the system from S to T .
Alexa initialises the labelling procedure for this system, and the excess capacities and potential backflows are shown on the arrows either side of each arc, as shown in Figure 1.
- State the value of the initial flow.
- Explain why arcs DF and DG can never both be full to capacity.
- Obtain the capacity of the cut that passes through the \(\operatorname { arcs } \mathrm { AC } , \mathrm { AD } , \mathrm { BD } , \mathrm { DE } , \mathrm { EG }\) and EJ .
- 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.
(3) - Use your answers to part (d) to find a maximum flow pattern for this system of pipes and draw it on Diagram 1 in the answer book.
- Prove that the answer to part (e) is optimal.