4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4abb2325-b9df-4849-b08c-7db465fe85e0-05_1054_1569_194_248}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 represents a system of pipes through which fluid can flow from the source node, S , to the sink node, T. The labelling procedure has been applied to Figure 1, and the numbers on the arrows, either side of each arc, show the excess capacities and potential backflows.
Currently, no fluid is flowing through the system.
- Calculate the capacity of the cut that passes through arcs \(\mathrm { GT } , \mathrm { EG } , \mathrm { DE } , \mathrm { BE } , \mathrm { FE }\) and FH .
- Explain why arc GT can never be full to capacity when fluid is flowing through the system.
- Apply the labelling procedure to Diagram 1 in the answer book to show the maximum flow along SBET. State the amount that can flow along this route.
- 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.
- State the maximum flow through the system and find a cut to show that this flow is maximal.
- Show the maximum flow on Diagram 2 in the answer book.