7 Figure 1 shows a system of water pipes in a manufacturing complex. The number on each arc represents the upper capacity for each pipe in litres per second. The numbers in the circles represent an initial feasible flow of 38 litres of water per second. \begin{figure}[h] \end{figure} 7

1. 1. Calculate the value of the cut \(\{ S , A , B , C \} \{ D , E , F , G , H , T \}\). 7
2. (ii) Explain, in the context of the question, what can be deduced from your answer to part (a)(i). 7
3. 1. Using the initial feasible flow shown in Figure 1, indicate on Figure 2 potential increases and decreases in the flow along each arc. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-11_997_1554_475_242}
      \end{figure} 7
4. (ii) Use flow augmentation on Figure 2 to find the maximum flow through the manufacturing complex. You must indicate any flow augmenting paths clearly in the table and modify the potential increases and decreases of the flow on Figure 2.

   Augmenting Path	Flow

   Maximum Flow \(=\) \(\_\_\_\_\) 7
5. The management of the manufacturing complex want to increase the maximum amount of water which can flow through the system of pipes. To do this they decide to upgrade one of the water pipes by replacing it with a larger capacity pipe. Explain which pipe should be upgraded.
   Deduce what effect this upgrade will have on the maximum amount of water which can flow through the system of pipes.
   \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-13_2488_1716_219_153}