Lower and upper capacity networks

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-14_807_1472_429_276}

1. Find the value of the cut \(Q\).
2. Figure 2 shows most of the values of a feasible flow of 34 litres per second from \(S\) to \(T\).
   1. Insert the missing values of the flows along \(D E\) and \(F G\) on Figure 2.
   2. Using this feasible flow as the initial flow, indicate potential increases and decreases of the flow along each edge on Figure 3.
   3. Use flow augmentation on Figure 3 to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
3. 1. State the value of the maximum flow.
   2. Illustrate your maximum flow on Figure 4.
4. Find a cut with capacity equal to that of the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_1646_1463_280_381}
   \end{figure} Figure 3 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_668_1230_1998_404}
   \end{figure}

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per minute. \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-12_810_1433_429_306}

1. Find the value of the cut \(Q\).
2. Figure 3 opposite shows a partially completed diagram for a feasible flow of 24 litres per minute from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(B T , D E\) and \(E T\).
3. 1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4 opposite.
   2. Use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 5 opposite.
4. Find a cut with value equal to that of the maximum flow. You may wish to show the cut on the network above. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_759_1442_276_299}
   \end{figure} Figure 4 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_764_1438_1930_296}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-15_2349_1691_221_153} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-16_2489_1719_221_150}

4 Answer parts (v) and (vi) of this question on the insert provided. The diagram represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities of the pipes in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{33995efa-7ede-4e83-89d3-7b6c8be8d955-4_703_789_479_678}

1. Which vertex is the source and which vertex is the sink?
2. Cut \(\alpha\) partitions the vertices into the sets \(\{ A , B , C \} , \{ D , E , F , G , H , I \}\). Calculate the capacity of cut \(\alpha\).
3. Explain why partitioning the vertices into sets \(\{ A , D , G \} , \{ B , C , E , F , H , I \}\) does not give a cut.
4. (a) How many litres per second must flow along arc \(D G\) ?
   (b) Explain why the arc \(A D\) must be at its upper capacity. Hence find the flow in \(\operatorname { arc } B A\).
   (c) Explain why at least 7 litres per second must flow along arc \(B C\).
5. Use the diagrams in the insert to show a minimum feasible flow and a maximum feasible flow. The upper capacity of \(B C\) is now increased from 8 to 18 .
6. (a) Use the diagram in the insert to show a flow of 19 litres per second.
   (b) List the saturated arcs when 19 litres per second flows through the network. Hence, or otherwise, find a cut of capacity 19 .
7. Explain how your answers to part (vi) show that 19 litres per second is the maximum flow.

4 The diagram represents a system of pipes through which fluid can flow from two sources, \(S _ { 1 }\) and \(S _ { 2 }\), to a sink, \(T\). Most of the pipes have valves which restrict the flow to one direction only. However, the flow in arc \(D E\) can be in either direction. The weights on the arcs show the lower capacities and the upper capacities of the pipes in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{fc01c62e-64bd-4fbc-ac1e-cdfa47c07228-5_565_1130_447_463}

1. Add a supersource, \(S\), to the copy of the diagram in the answer book, and weight the arcs attached to it with appropriate lower and upper capacities.
2. The cut \(\alpha\) partitions the vertices into the sets \(\left\{ S , S _ { 1 } , S _ { 2 } , A , C \right\} , \{ B , D , E , T \}\). By considering the cut arcs only, calculate the maximum and minimum capacities of cut \(\alpha\).
3. Show that the maximum capacity of the cut \(\left\{ S , S _ { 1 } , S _ { 2 } , A , E \right\} , \{ B , C , D , T \}\) is 47 litres per second. A flow is set up in which the arcs \(S _ { 1 } A , S _ { 1 } B , S _ { 2 } C , A E , C E\) and \(D T\) are all at their lower capacities.
4. Show the flow in each arc on the diagram in the answer book, indicating the direction of the flow in \(\operatorname { arc } D E\).
5. What is the maximum amount, in litres per second, by which the flow can be augmented using the routes \(S _ { 1 } A D T\) and \(S _ { 2 } C E T\) ?
6. Find the maximum possible flow through the system, explaining how you know both that this is feasible and that it cannot be exceeded.

5 The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities for the pipes, in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-6_577_1182_351_443}

1. Identify the source and explain how you know that the sink is at \(G\).
2. Calculate the capacity of the cut that separates \(\{ A , B , C , D , E , F \}\) from \(\{ G , H , I , J , K , L \}\).
3. Assuming that a feasible flow exists, explain why arc \(J G\) must be at its lower capacity. Write down the flows in arcs \(H K\) and \(I L\).
4. Assuming that a feasible flow exists, explain why arc HI must be at its upper capacity. Write down the flows in arcs \(E H\) and \(C B\).
5. Show a flow of 10 litres per second through the system.
6. Using your flows from part (v), label the arrows on the diagram to show the excess capacities and the potential backflows.
7. Write down a flow augmenting path from your diagram in part (vi), but do not update the excess capacities and the potential backflows. Hence show a maximum flow through the system, and state how you know that the flow is maximal.

6
The network shows a system of pipes, where \(S\) is the source and \(T\) is the sink.
The lower and upper capacities, in litres per second, of each pipe are shown on each arc. \includegraphics[max width=\textwidth, alt={}, center]{88669bc0-9d3f-431a-8939-8aef2682412b-09_649_1399_580_424} 6

1. There is a feasible flow from \(S\) to \(T\). 6
   1. (i) Explain why arc \(A D\) must be at its lower capacity.
      [0pt] [1 mark] 6
   2. (ii) Explain why arc \(B E\) must be at its upper capacity.
      [0pt] [1 mark] 6
   3. Explain why a flow of 11 litres per second through the network is impossible.
      [0pt] [1 mark] 6
   4. The network in Figure 2 shows a second system of pipes, where \(S\) is the source and \(T\) is the sink. The lower and upper capacities, in litres per second, of each pipe are shown on each edge. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{88669bc0-9d3f-431a-8939-8aef2682412b-10_760_1372_680_470}
      \end{figure} Figure 3 shows a feasible flow of 17 litres per second through the system of pipes. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{88669bc0-9d3f-431a-8939-8aef2682412b-10_750_1371_1811_466}
      \end{figure} 6
   5. 1. Using Figures 2 and 3, indicate on Figure 4 potential increases and decreases in the flow along each arc.
         [0pt] [2 marks] \begin{figure}[h]
         \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{88669bc0-9d3f-431a-8939-8aef2682412b-11_749_1384_457_426}
         \end{figure} 6
   6. (ii) Use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\).
      You should indicate any flow augmenting paths clearly in the table below and modify the potential increases and decreases of the flow on Figure 4.
      [0pt] [3 marks]

      Augmenting Path	Flow

      6
   7. (iii) Prove the flow found in part (d) (ii) is maximum.
      6
   8. (iv) Due to maintenance work, the flow through node \(E\) is restricted to 9 litres per second.
      [0pt] Interpret the impact of this restriction on the maximum flow through the system of pipes. [2 marks]

6. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid flows from a source, S , to a sink, T . The numbers ( \(l , u\) ) on each arc represent, in litres per second, the lower capacity, \(l\), and the upper capacity, \(u\), of the corresponding pipe. Two cuts \(C _ { 1 }\) and \(C _ { 2 }\) are shown.

1. Find the capacity of
   1. \(\operatorname { cut } C _ { 1 }\)
   2. \(\operatorname { cut } C _ { 2 }\)
2. Explain why the arcs AE and CE cannot be at their upper capacities simultaneously.
3. Explain why a flow of 31 litres per second through the system is not possible.
4. Hence determine a minimum feasible flow and a maximum feasible flow through the system. You must draw these feasible flows on the diagrams in the answer book and give reasons to justify your answer. You should not apply the labelling procedure to find these flows.

5. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities for the corresponding pipes, in litres per second.

1. Calculate the capacity of
   1. cut \(C _ { 1 }\)
   2. cut \(C _ { 2 }\)
2. Using only the capacities of cuts \(C _ { 1 }\) and \(C _ { 2 }\), state what can be deduced about the maximum flow through the system. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{262aa0e6-479f-447a-94db-aeb901b3c6fe-6_775_1516_169_278} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 2 shows an initial flow through the same network.
3. State the value of the initial flow.
4. By entering values along \(B C , C F\) and \(D T\), complete the labelling procedure on Diagram 1 in the answer book.
5. 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.
6. Use your answer to (e) to find a maximum flow pattern for this system of pipes and draw it on Diagram 2 in the answer book.
7. Prove that the answer to (f) is optimal. A vertex restriction is now applied to \(B\) so that no more than 16 litres per second can flow through it.
8. 1. Complete Diagram 3 in the answer book to show this restriction.
   2. State the value of the maximum flow with this restriction.

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc \(( x , y )\) represents the lower \(( x )\) capacity and upper \(( y )\) capacity of that arc.

1. Calculate the value of the cut \(C _ { 1 }\) and cut \(C _ { 2 }\)
2. Explain why the flow through the network must be at least 12 and at most 16
3. Explain why arcs DG, AG, EG and FG must all be at their lower capacities.
4. 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.
5. 1. State the value of the maximum flow through the network.
   2. Explain why the value of the maximum flow is equal to the value of the minimum flow through the network. Node E becomes blocked and no flow can pass through it. To maintain the maximum flow through the network the upper capacity of exactly one arc is increased.
6. Explain how it is possible to maintain the maximum flow found in (d).

3 Answer this question on the insert provided. \begin{figure}[h] \end{figure} Fig. 1 represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). It also shows a cut \(\alpha\). The weights on the arcs show the lower and upper capacities of the pipes in litres per second.

1. Calculate the capacity of the cut \(\alpha\).
2. By considering vertex \(B\), explain why arc \(S B\) must be at its lower capacity. Then by considering vertex \(E\), explain why arc \(C E\) must be at its upper capacity, and hence explain why arc \(H T\) must be at its lower capacity.
3. On the diagram in the insert, show a flow through the network of 15 litres per second. Write down one flow augmenting route that allows another 1 litre per second to flow through the network. Show that the maximum flow is 16 litres per second by finding a cut of 16 litres per second. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-4_602_1086_1809_568} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure} Fig. 2 represents the same system, but with pipe \(E B\) installed the wrong way round.
4. Explain why there can be no feasible flow through this network.

4 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes, with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-005_547_1214_555_404}

1. Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(M N , P Q , N P\) and \(N T\).
2. 1. Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\).
   2. State the value of the maximum flow and illustrate this flow on Figure 5.
3. Find a cut with capacity equal to that of the maximum flow.

4 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes, with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{30a88efe-fe9e-4384-a3e3-da2a05326797-04_547_1214_555_404}

1. Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 10 litres per second from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(M N , P Q , N P\) and \(N T\).
2. 1. Taking your answer from part (a) as an initial flow, use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\).
   2. State the value of the maximum flow and illustrate this flow on Figure 5.
3. Find a cut with capacity equal to that of the maximum flow.

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{0c40b693-72d3-459c-bbb7-b9584a108b8e-07_713_1456_539_294}

1. 1. Find the value of the cut \(C\).
   2. State what can be deduced about the maximum flow from \(S\) to \(T\).
2. Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 20 litres per second from \(S\) to \(T\). Indicate, on Figure 4, the flows along the edges \(M P , P N , Q R\) and \(N R\).
3. 1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
   2. Use flow augmentation on Figure 5 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 6.

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{f98d4434-458a-4118-92ed-309510d7975a-06_796_1337_518_338}

1. 1. Find the value of the cut \(C\).
   2. Hence state what can be deduced about the maximum flow from \(S\) to \(T\).
2. Figure 4, printed on the insert, shows a partially completed diagram for a feasible flow of 32 litres per second from \(S\) to \(T\). Indicate, on Figure 4, the flows along the edges \(P Q , U Q\) and \(U T\).
3. 1. Taking your feasible flow from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 5.
   2. Use flow augmentation on Figure 5 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. Illustrate the maximum flow on Figure 6.

6 [Figures 3, 4 and 5, printed on the insert, are provided for use in this question.]
The network shows a system of pipes with the lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{1bf0d8b7-9f91-437a-bc18-3bfe5ca12223-07_849_1363_518_326}

1. Find the value of the cut \(C\).
2. Figure 3, on the insert, shows a partially completed diagram for a feasible flow of 40 litres per second from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(A E , E F\) and \(F G\).
3. 1. Taking your answer from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4.
   2. Use flow augmentation on Figure 4 to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
4. Illustrate the maximum flow on Figure 5.
5. Find a cut with value equal to that of the maximum flow.

6 The network shows a system of pipes with lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{34de3f03-a275-44fb-88b2-b88038bcec97-22_817_744_397_648}

1. 1. Find the value of the cut \(X\).
   2. Hence state what can be deduced about the maximum flow from \(A\) to \(H\).
2. Figure 3 shows a partially completed diagram for a feasible flow of 28 litres per second from \(A\) to \(H\). Indicate, on Figure 3, the flows along the edges \(B D , B E\) and \(C D\).
3. 1. Using your feasible flow from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4.
   2. Use flow augmentation on Figure 4 to find the maximum flow from \(A\) to \(H\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. State the maximum flow and indicate a maximum flow on Figure 5. \section*{Answer space for question 6} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-23_682_689_312_397}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-23_935_1477_1037_365}
      \end{figure} Figure 5
      \includegraphics[max width=\textwidth, alt={}]{34de3f03-a275-44fb-88b2-b88038bcec97-24_2032_1707_219_153}

1 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are lower and upper capacities in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{e879b1f5-edc7-4819-80be-2a90dbf3d451-02_696_1292_376_424}

1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
2. Show that the capacity of the cut \(\alpha\), shown on the diagram, is 12 litres per second and calculate the minimum flow across the cut \(\alpha\), from \(S\) to \(T\), (without regard to the remainder of the diagram).
3. Explain why the arc SC must have at least 5 litres per second flowing through it. By considering the flow through \(A\), explain why \(A D\) cannot be full to capacity.
4. Show that it is possible for 11 litres per second to flow through the system.
5. From your previous answers, what can be deduced about the maximum flow through the system?

1. A sheet is provided for use in answering this question.

\begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the minimum and maximum capacity of that arc. \begin{figure}[h] \end{figure} Figure 2 shows a feasible flow through the same network.

1. Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow and draw the maximal flow pattern.
   (6 marks)
2. Find a cut of the same value as your maximum flow and explain why this proves it gives the maximim possible flow.

5. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower capacities and upper capacities for the corresponding pipes, in litres per second.

1. State the source node.
2. Explain why the sink node must be G.
3. Calculate the capacity of the cut \(C _ { 1 }\)
4. Assuming that a feasible flow exists,
   1. explain why arc JH must be at its upper capacity,
   2. explain why arcs AD and CD must be at their lower capacities.
5. Use Diagram 1 in the answer book to show a flow of 18 litres per second through the system.
6. Prove that the answer to (e) is the maximum flow through the system.

Figure 1 shows a network of gas pipes. The numbers on each arc represent the lower and upper capacity for each pipe in \(\text{m}^3 \text{s}^{-1}\) The numbers in the circles represent an initial feasible flow of 73 \(\text{m}^3 \text{s}^{-1}\) through the network. \includegraphics{figure_8}

1. On Figure 1 above, add 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 page opposite, in your solution. [4 marks]

   Augmenting Path	Flow

   Maximum flow \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
3. Prove that the flow found in part (b) is the maximum flow through the network. [2 marks]
4. A trainee engineer claims that increasing the upper capacity of the pipe \(AG\) will increase the maximum flow through the network, as the flow through this pipe cannot currently be increased. Comment on the validity of the trainee's claim. [2 marks]