Complete labelling procedure initialization

5. \begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
   (1)
2. State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
   (2)
3. By entering values along DH, FH, FI and IT, complete the labelling procedure on Diagram 1 in the answer book.
   (2)
4. Using Diagram 1, increase the flow by a further 4 units. You must list each flow-augmenting route you use, together with its flow.
   (3)
5. Prove that the flow is now maximal.
   (2)

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
   (1)
2. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { SB } , \mathrm { BD } , \mathrm { CF }\) and FT .
   (2)
3. Hence 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.
   (4)
4. Draw a maximal flow pattern on Diagram 2 in your answer book.
   (2)
5. Prove that your flow is maximal.
   (2)

5. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
   (1)
2. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { SC } , \mathrm { AB } , \mathrm { CE } , \mathrm { DE }\) and DT .
   (2)
3. Hence 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.
   (4)
4. Draw a maximal flow pattern on Diagram 2 in the answer book.
   (2)
5. Prove that your flow is maximal.
   (2)

5. \begin{figure}[h] \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.

1. Find the capacity of each of the two cuts and the value of the initial flow.
   (3)
2. 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)
3. 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)
4. Show your flow pattern on Figure 2.
   (2)
5. Prove that your flow is maximal.
   (2)

1 [Answer this question on the insert provided.]
The network below represents a system of pipelines through which fluid flows from \(S\) to \(T\). The capacities of the pipelines, in litres per second, are shown as weights on the arcs. \includegraphics[max width=\textwidth, alt={}, center]{0403a37e-46dd-4346-afc6-e48a34417c48-2_863_1201_486_477}

1. Write down the arcs from \(\{ S , A , C , E \}\) to \(\{ B , D , F , T \}\). Hence find the capacity of the cut that separates \(\{ S , A , C , E \}\) from \(\{ B , D , F , T \}\).
2. On the diagram in the insert show the excess capacities and potential backflows when 5 litres per second flow along SADT and 6 litres per second flow along SCFT.
3. Give a flow-augmenting path of capacity 2 . On the second diagram in the insert show the new capacities and potential backflows.
4. Use the maximum flow - minimum cut theorem to show that the maximum flow from \(S\) to \(T\) is 13 litres per second.
5. \(E B\) is replaced by a pipeline with capacity 2 litres per second from \(B\) to \(E\). Find the new maximum flow from \(S\) to \(T\). You should show the flow on the third diagram in the insert and explain how you know that this is a maximum.

5 The diagram shows a flow through a network of directed arcs. The amount that can flow in each arc is limited by its upper capacity, and the lower capacity of each arc is 0 . The labelled arrows by the arcs show how much more (excess capacity) and how much less (potential backflow) could flow in each arc, in litres per second, and the objective is to find the maximum flow from \(S\) to \(T\). \includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-6_969_1363_459_351}

1. How many litres per second are currently flowing along the route SACHT?
2. How many litres per second are currently flowing from \(S\) to \(T\) ?
3. What is the maximum by which the flow along the route SBGIT can be increased? Use the copy of the network in your answer book to show what happens to the labels on the arrows when the flow along this route is augmented by this amount.
4. Find the maximum amount that can flow through the network. Explain, by using a cut, how you know that your flow is a maximum. The network had vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\). The single vertex \(E\) is replaced by the pair of vertices \(E _ { 1 }\) and \(E _ { 2 }\), together with the \(\operatorname { arc } E _ { 1 } E _ { 2 }\).
5. What does the \(\operatorname { arc }\) joining \(E _ { 1 }\) and \(E _ { 2 }\) tell you about the flow at \(E\) ?
6. Complete the diagram in your answer book to show the flow resulting after part (iii) on a directed network with vertices \(S , A , B , C , D , E , F , G , H , I\) and \(T\).

2 Water flows through pipes from an underground spring to a tap. The size of each pipe limits the amount that can flow. Valves restrict the direction of flow. The pipes are modelled as a network of directed arcs connecting a source at \(S\) to a sink at \(T\). Arc weights represent the (upper) capacities, in litres per second. Pipes may be empty. Fig. 3 shows a flow of 5 litres per second from \(S\) to \(T\). Fig. 4 shows the result of applying the labelling procedure to the network with this flow. The arrows in the direction of potential flow show excess capacities (how much more could flow in the arc, in that direction) and the arrows in the opposite direction show potential backflows (how much less could flow in the arc). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down the capacity of \(\operatorname { arc } F T\) and of \(\operatorname { arc } D T\). Find the value of the cut that separates the vertices \(S , A , B , C , D , E , F\) from the sink at \(T\).
2. (a) Update the excess capacities and the potential backflows to show an additional flow of 2 litres per second along \(S - C - B - F - T\).
   (b) Write down a further flow augmenting route and the amount by which the flow can be augmented. You do not need to update the excess capacities and potential backflows a second time.
3. Show the flow that results from part (ii)(b) and find a cut that has the same value as your flow.

5 [Answer this question on the insert provided.]
Fig. 1 shows a directed flow network. The weight on each arc shows the capacity in litres per second. \begin{figure}[h] \end{figure}

1. Find the capacity of the cut \(\mathscr { C }\) shown.
2. Deduce that there is no possible flow from \(S\) to \(T\) in which both arcs leading into \(T\) are saturated. Explain your reasoning clearly. Fig. 2 shows a possible flow of 160 litres per second through the network. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-05_499_1084_1471_500} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure}
3. On the diagram in the insert, show the excess capacities and potential backflows for this flow.
4. Use the labelling procedure to augment the flow as much as possible. Show your working clearly, but do not obscure your answer to part (iii).
5. Show the final flow that results from part (iv). Explain clearly how you know that this flow is maximal.

6. (a) Define the term 'cut' as it applies to a directed network.
(2) \begin{figure}[h] \end{figure} Figure 6 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.
(b) Complete the labelling procedure on Diagram 2 in your answer book by entering values along CE, EG, HT and GT.
(c) Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
(d) Show a maximal flow pattern on Diagram 3 in your answer book.
(e) State the value of the maximum flow through the network.
(f) Prove that your flow is maximal.

3. \begin{figure}[h] \end{figure} Alexa is monitoring a system of pipes through which fluid can flow from the source, S , to the sink, T . Currently, fluid is flowing through the system from S to T . Alexa initialises the labelling procedure for this system, and the excess capacities and potential backflows are shown on the arrows either side of each arc, as shown in Figure 1.

1. State the value of the initial flow.
2. Explain why arcs DF and DG can never both be full to capacity.
3. Obtain the capacity of the cut that passes through the \(\operatorname { arcs } \mathrm { AC } , \mathrm { AD } , \mathrm { BD } , \mathrm { DE } , \mathrm { EG }\) and EJ .
4. 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.
   (3)
5. Use your answers to part (d) to find a maximum flow pattern for this system of pipes and draw it on Diagram 1 in the answer book.
6. Prove that the answer to part (e) is optimal.

2. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow.

1. State the value of the initial flow.
   (1)
2. Obtain the capacity of the cut that passes through the arcs \(\mathrm { AG } , \mathrm { CG } , \mathrm { GF } , \mathrm { FT } , \mathrm { FH }\) and EH .
   (1)
3. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { SD } , \mathrm { BD } , \mathrm { BE }\) and GF .
   (2)
4. 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.
   (3)
5. Use the answer to part (d) to add a maximum flow pattern to Diagram 2 in the answer book.
   (1)
6. Prove that your answer to part (e) is optimal.
   (3)

2. \begin{figure}[h] \end{figure} An engineer monitors a system of pipes through which a fluid flows from the source, S , to the sink, T . The engineer initialises the labelling procedure for this system, and the excess capacities and potential backflows are shown on the arrows either side of each arc, as shown in Figure 1.

1. State the value of the initial flow.
2. Obtain the capacity of the cut that passes through the arcs \(\mathrm { SA } , \mathrm { SB } , \mathrm { CE } , \mathrm { FE }\) and FJ .
3. 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.
4. Use your answer to (c) to draw a maximum flow pattern on Diagram 1 in the answer book.
5. Prove that the answer to (d) is optimal.

5 Answer this question on the insert provided. The network represents a system of pipes through which fluid can flow from a source, S , to a sink, T . \includegraphics[max width=\textwidth, alt={}, center]{09d4aacd-026b-4d81-a826-3d3f29f9c105-5_1310_1301_447_424} The arrows are labelled to show excess capacities and potential backflows (how much more and how much less could flow in each pipe). The excess capacities and potential backflows are measured in litres per second. Currently the flow is 6 litres per second, all flowing along a single route through the system.

1. Write down the route of the 6 litres per second that is flowing from \(S\) to \(T\).
2. What is the capacity of the pipe AG and in which direction can fluid flow along this pipe?
3. Calculate the capacity of the \(\operatorname { cut } \mathrm { X } = \{ \mathrm { S } , \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \} , \mathrm { Y } = \{ \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { I } , \mathrm { T } \}\).
4. Describe how a further 7 litres per second can flow from S to T and update the labels on the arrows to show your flow. Explain how you know that this is the maximum flow. {}

6. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of the corresponding arc. The numbers in circles represent an initial flow from S to T .

1. State the value of the initial flow.
2. State the capacity of cut \(C _ { 1 }\)
3. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { AC } , \mathrm { SB } , \mathrm { BE } , \mathrm { DE }\) and FG .
   (2)
4. Hence 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.
5. Draw a maximal flow pattern on Diagram 2 in the answer book.
6. Prove that your flow is maximal.

4. \begin{figure}[h] \end{figure} Figure 1 represents a system of pipes through which fluid can flow from the source node, S , to the sink node, T. The labelling procedure has been applied to Figure 1, and the numbers on the arrows, either side of each arc, show the excess capacities and potential backflows. Currently, no fluid is flowing through the system.

1. Calculate the capacity of the cut that passes through arcs \(\mathrm { GT } , \mathrm { EG } , \mathrm { DE } , \mathrm { BE } , \mathrm { FE }\) and FH .
2. Explain why arc GT can never be full to capacity when fluid is flowing through the system.
3. Apply the labelling procedure to Diagram 1 in the answer book to show the maximum flow along SBET. State the amount that can flow along this route.
4. 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.
5. State the maximum flow through the system and find a cut to show that this flow is maximal.
6. Show the maximum flow on Diagram 2 in the answer book.

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
      1. (ii) Explain, in the context of the question, what can be deduced from your answer to part (a)(i). 7
   2. 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
   3. (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
   4. 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}

\includegraphics{figure_6} Figure 6 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.

1. On Diagram 1 and Diagram 2 in the answer book, add a supersource \(S\) and a supersink \(T\). On Diagram 1 show the minimum capacities of the arcs you have added. [2]

Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.

1. Complete the initial labelling procedure in Diagram 2. [2]
2. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow, and state the maximal flow. [6]
3. Show a maximal flow pattern on Diagram 3. [2]
4. Prove that your flow is maximal. [2]
5. Describe briefly a situation for which this network could be a suitable model. [2]

(Total 16 marks)

\includegraphics{figure_9} The figure above shows a capacitated, directed network. The capacity of each arc is shown on each arc. The numbers in circles represent an initial flow from \(S\) to \(T\). Two cuts \(C_1\) and \(C_2\) are shown on the figure.

1. Write down the capacity of each of the two cuts and the value of the initial flow. [3]
2. Complete the initialisation of the labelling procedure on the diagram below by entering values along arcs \(AC\), \(CD\), \(DE\) and \(DT\). \includegraphics{figure_9b} [2]
3. Hence use the labelling procedure to find a maximal flow through the network. You must list each flow-augmenting path you use, together with its flow. [5]
4. Show your maximal flow pattern on the diagram below. \includegraphics{figure_9d} [2]
5. Prove that your flow is maximal. [2]

(Total 14 marks)