Add supersource and/or supersink

\includegraphics{figure_2} A company has 3 warehouses \(W_1\), \(W_2\) and \(W_3\). It needs to transport the goods stored there to 2 retail outlets \(R_1\) and \(R_2\). The capacities of the possible routes, in van loads per day, are shown in Fig. 2. Warehouses \(W_1\), \(W_2\) and \(W_3\) have 14, 12 and 14 van loads respectively available per day and retail outlets \(R_1\) and \(R_2\) can accept 6 and 25 van loads respectively per day.

1. On Diagram 1 on the answer sheet add a supersource \(W\) and a supersink \(R\) and the appropriate directed arcs to obtain a single-source, single-sink capacitated network. State the minimum capacity of each arc you have added. [3]
2. State the maximum flow along
   1. \(W_1W_1R_1R\),
   2. \(W_2CR_2R\).
   [2]
3. Taking your answers to part (b) as the initial flow pattern, use the labelling procedure to obtain a maximum flow through the network from \(W\) to \(R\). Show your working on Diagram 2. List each flow-augmenting route you find together with its flow. [5]
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day. [1]

The diagram shows a network of pipes. Each pipe is labelled with its upper capacity in \(\mathrm{m}^3 \mathrm{s}^{-1}\) \includegraphics{figure_3}

1. Find the value of Cut \(X\) [1 mark]
2. Find the value of Cut \(Y\) [1 mark]
3. Add a supersink \(T\) to the network. [2 marks]

Figure 1 shows a network of water pipes. 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 103 litres per second. \includegraphics{figure_1}

1. On Figure 1 above, add a supersource \(S\) and a supersink \(T\) to the network. [2 marks]
2. Using flow augmentation, find the maximum flow through the network. You must indicate any flow augmenting paths clearly in the table below. You may use Figure 2, on the opposite page, in your solution. [4 marks]

   Augmenting Path	Extra Flow

   Maximum Flow ______________ litres per second
3. While the flow through the network is at its maximum value, the pipe \(EG\) develops a leak. To repair the leak, an engineer turns off the flow of water through \(EG\) The engineer claims that the maximum flow of water through the network will reduce by 31 litres per second. Comment on the validity of the engineer's claim. [2 marks]