Explain capacity/flow constraints

4. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. Two cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown.

1. Find the capacity of each of the two cuts. Given that one of these two cuts is a minimum cut,
2. write down the maximum possible flow through the network. Given that the network now has a maximal flow from S to T ,
3. determine the flow along arc SB.
4. Explain why arcs GF and GT cannot both be saturated. Given that arcs EC, AD and DF are saturated and that there is no flow along arc GF,
5. determine a maximum flow pattern for this network and draw it on Diagram 1 in the answer book. You do not need to use the labelling procedure to determine the maximum flow.

3 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are the capacities in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}

1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
2. Explain why the capacity of the cut \(\alpha\), shown on the diagram, is only 21 litres per second.
3. Explain why neither of the arcs \(S C\) and \(A D\) can be full to capacity. Give the maximum flow in \(\operatorname { arc } S B\).
4. Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.

4 The diagram represents a system of roads through which traffic flows from a source, \(S\), to a sink, \(T\). The weights on the arcs show the capacities of the roads in cars per minute. \includegraphics[max width=\textwidth, alt={}, center]{3a47bac8-0067-4acb-a3c7-7d8512403cca-5_414_1080_349_488}

1. (a) The cut \(\alpha\) partitions the vertices into the sets \(\{ S , A , B , C \} , \{ D , E , F , T \}\). Calculate the capacity of cut \(\alpha\).
   (b) The cut \(\beta\) partitions the vertices into the sets \(\{ S , A , B , D \} , \{ C , E , F , T \}\). Calculate the capacity of cut \(\beta\).
   (c) Using only the capacities of cuts \(\alpha\) and \(\beta\), what can you deduce about the maximum possible flow through the system?
2. Explain why partitioning the vertices into sets \(\{ S , A , D , T \} , \{ B , C , E , F \}\) does not give a cut.
3. What do the double arcs between \(D\) and \(E\) and between \(E\) and \(F\) represent?
4. Explain why the maximum possible flow along \(C F\) must be less than 45 cars per minute.
5. (a) Show how a flow of 60 cars per minute along \(F T\) can be achieved.
   (b) Show that 60 cars per minute is the maximum possible flow through the system. An extra road is opened linking \(S\) to \(C\). Let the capacity of this road be \(x\) cars per minute.
6. Find the maximum possible flow through the new system, in terms of \(x\) where necessary, for the different possible values of \(x\).

5 The network represents a simplified map of a town centre. On certain days, large numbers of visitors need to travel through the town centre, from \(S\) to \(T\). The arcs represent roads and the weights show the maximum number of visitors per hour who can use each road. To find the maximum rate at which visitors can travel through the town centre without any of them being delayed, the problem is modelled as a maximum flow problem. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-6_837_1317_523_413}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , G \}\) from \(\{ B , D , E , F , T \}\).
2. Explain why neither arc \(S A\) nor arc \(E T\) can be full to capacity. Also explain why the arcs \(A C\) and \(B C\) cannot simultaneously be full to capacity.
3. Show a flow of 3300 people per hour, and find a cut of capacity 3300 . The direction of flow in \(B C\) is reversed.
4. Show the excess capacities and potential backflows when there is no flow.
5. Without obscuring your answer to part (iv), augment the labels to show a flow of 2000 people per hour along \(S B E T\).
6. Write down further flow augmenting routes and augment the labels, without obscuring your previous answers, to find the maximum flow from \(S\) to \(T\).
7. Show the maximum flow and explain how you know that this flow is maximal.

5 Answer this question on the insert provided. The network represents a system of irrigation channels along which water can flow. The weights on the arcs represent the maximum flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-05_597_1553_479_296}

1. Calculate the capacity of the cut that separates \(\{ S , B , C , E \}\) from \(\{ A , D , F , G , H , T \}\).
2. Explain why neither arc \(S C\) nor arc \(B C\) can be full to capacity. Explain why the arcs \(E F\) and \(E H\) cannot both be full to capacity. Hence find the maximum flow along arc \(H T\). When arc \(H T\) carries its maximum flow, what is the flow along arc \(H G\) ?
3. Show a flow of 58 litres per second on the diagram in the insert, and find a cut of capacity 58. The direction of flow in \(H G\) is reversed.
4. Use the diagram in the insert to show the excess capacities and potential backflows for your flow from part (iii) in this case.
5. Without augmenting the labels from part (iv), write down flow augmenting routes to enable an additional 2 litres per second to flow from \(S\) to \(T\).
6. Show your augmented flow on the diagram in the insert. Explain how you know that this flow is maximal.