5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{e80fcab6-7c7d-4a0c-84e0-c23f5a969a75-4_924_1646_221_207}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
Figure 1 shows a capacitated, directed, network. The capacity of each arc is shown on that arc and the numbers in circles represent an initial flow from S to T .
Two cuts, \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown on Figure 1.
- Find the capacity of each of the two cuts and the value of the initial flow.
(3) - Complete the initialisation of the labelling procedure on Figure 1 in the answer book, by entering values along \(\mathrm { SB } , \mathrm { AB } , \mathrm { BE }\) and BG .
(2) - Hence use the labelling procedure to find a maximum flow of 85 through the network. You must list each flow-augmenting path you use, together with its flow.
(5) - Show your flow pattern on Figure 2.
(2) - Prove that your flow is maximal.
(2)