Add supersource and/or supersink

6 A retail company has warehouses at \(P , Q\) and \(R\), and goods are to be transported to retail outlets at \(Y\) and \(Z\). There are also retaining depots at \(U , V , W\) and \(X\). The possible routes with the capacities along each edge, in van loads per week, are shown in the following diagram. \includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-14_673_1193_577_429}

1. On Figure 5 opposite, add a super-source, \(S\), and a super-sink, \(T\), and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each edge that you have added.
2. On Figure 6, write down the maximum flows along the routes SPUYT and SRVWZT.
3. 1. On Figure 7, add the vertices \(S\) and \(T\) and the edges connecting \(S\) and \(T\) to the network. Using the maximum flows along the routes SPUYT and SRVWZT found in part (b) as the initial flow, indicate the potential increases and decreases of the flow on each edge of these routes.
   2. Use flow augmentation to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting routes on Figure 6 and modify the potential increases and decreases of the flow on Figure 7.
4. Find a cut with value equal to the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_629_1100_342_477}
   \end{figure} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 6}

   Route	Flow
   SPUYT
   SRVWZT

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 7} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_634_1109_1838_470}
   \end{figure}

7 Figure 2 shows a network of pipes. Water from two reservoirs, \(R _ { 1 }\) and \(R _ { 2 }\), is used to supply three towns, \(T _ { 1 } , T _ { 2 }\) and \(T _ { 3 }\).
In Figure 2, the capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.

1. Add a supersource, supersink and appropriate weighted edges to Figure 2. (2 marks)
2. 1. Use the initial flow and the labelling procedure on Figure 3 to find the maximum flow through the network. You should indicate any flow augmenting routes in the table and modify the potential increases and decreases of the flow on the network.
   2. State the value of the maximum flow and, on Figure 4, illustrate a possible flow along each edge corresponding to this maximum flow.
3. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-18_1077_1246_1475_395}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_1049_1264_308_386}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_835_1011_1738_171}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_688_524_1448_1302}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-20_2256_1707_221_153}

8. \begin{figure}[h] \end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.

1. Write down the source vertices. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4c64221-0373-4be9-abe3-5ff281922cdb-07_521_1402_1170_343}
   \end{figure} Figure 5 shows a feasible flow through the same network.
2. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
3. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
4. Show the maximal flow on Diagram 2 and state its value.
5. Prove that your flow is maximal.

11. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h] \end{figure}

1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
2. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
   2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
3. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
   2. Prove that your final flow is maximal.

12. \begin{figure}[h] \end{figure} 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\), 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.
2. State the maximum flow along
   1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
   2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
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 flowaugmenting route you use, together with its flow.
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day.

7. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.

1. Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 1 below. \section*{Diagram 1} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-4_684_1531_1816_267}
2. Find the values of \(x\) and \(y\), explaining your method briefly.
3. Find the value of cuts \(C _ { 1 }\) and \(C _ { 2 }\). Starting with the given feasible flow of 68,
4. use the labelling procedure on Diagram 2 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_647_1506_612_283}
5. Show your maximal flow on Diagram 3 and state its value. \section*{Diagram 3} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_654_1511_1567_278}
6. Prove that your flow is maximal.

6. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-3_696_1319_1292_374} This figure 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. Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
2. Complete the initial labelling procedure in Diagram 2.
3. 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.
4. Show a maximal flow pattern on Diagram 3.
5. Prove that your flow is maximal.
6. Describe briefly a situation for which this network could be a suitable model.
   (Total 16 marks) \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-4_1486_1963_568_50}

5. \begin{figure}[h] \end{figure} In solving a network flow problem using the labelling procedure, the diagram in Figure 1 was created.
The arrow on each arc indicates the direction of the flow along that arc.
The arrows above and below each arc show the direction and value of the flow as indicated by the labelling procedure.

1. Add a supersource S , a supersink T and appropriate arcs to the diagram above, and complete the labelling procedure for these arcs.
2. Write down the value of the initial flow shown in Figure 1.
3. Use Figure 2 below, the initial flow and the labelling procedure to find the maximal flow of 124 through this network. List each flow-augmenting path you use, together with its flow.
4. Show your flow on the diagram below and state its value. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-4_967_1520_114_214}
5. Prove that your flow is maximal.
   (2)
   (Total 14 marks)

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.
2. 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.
3. Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values on the arcs to S and T and on \(\operatorname { arcs } \mathrm { CD }\), DE , DG , FG, FI and GI.
4. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
5. Show your maximum flow on Diagram 3 in the answer book.
6. Prove that your flow is maximal.

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. 1. Add a supersource, S , and a supersink, T , and corresponding arcs to Diagrams 1 and 2, in the answer book.
   2. Enter the flow value and appropriate capacity on each of the arcs you have added to Diagram 1.
2. Complete the initialisation of the labelling procedure on Diagram 2 by entering values along the new arcs from \(S\) and \(T\), and along \(A B , A D\) and \(D _ { 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. Draw a maximal flow pattern on Diagram 3 in the answer book.
5. Prove that your flow is maximal.

2 The network models a cooling system in a factory. Coolant starts at \(A , B\) and \(C\) and flows through the system. The arcs model components of the cooling system and the weights show the maximum amount of coolant that can flow through each component of the system (measured in litres per second). The arrows show the direction of flow. \includegraphics[max width=\textwidth, alt={}, center]{cfa46190-9a1e-4552-a551-c28d5c4286ad-3_611_832_539_605}

1. Add a supersource, \(S\), and a supersink, \(T\), to the copy of the network in your answer book. Connect \(S\) and \(T\) to the network using appropriately weighted arcs.
2. (a) Find the capacity of the cut that separates \(A , B , C\) and \(E\) from \(D , F , G\) and \(H\).
   (b) Find the capacity of the cut that separates \(A , B , C , D , E\) and \(F\) from \(G\) and \(H\).
   (c) What can you deduce from this value about the maximum flow through the system?
3. Find the maximum possible flow through the system and prove that this is the maximum.
4. Describe what effect increasing the capacity of \(C E\) would have on the maximum flow.

7. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h] \end{figure}

1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
2. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
   2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
3. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
   2. Prove that your final flow is maximal.

7. \begin{figure}[h] \end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.

1. Write down the source vertices. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{438a62e6-113c-428e-85bf-4b1cbecee0de-6_525_1404_1233_345}
   \end{figure} Figure 5 shows a feasible flow through the same network.
2. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
3. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
   (6)
4. Show the maximal flow on Diagram 2 and state its value.
5. Prove that your flow is maximal.

7. \begin{figure}[h] \end{figure} Figure 6 shows a capacitated, directed network of pipes flowing from two oil fields \(\mathrm { F } _ { 1 }\) and \(\mathrm { F } _ { 2 }\) to three refineries \(\mathrm { R } _ { 1 } , \mathrm { R } _ { 2 }\) and \(\mathrm { R } _ { 3 }\). The number on each arc represents the capacity of the pipe and the numbers in the circles represent a possible flow of 65.

1. Find the value of \(x\) and the value of \(y\).
2. On Diagram 1 in the answer book, add a supersource and a supersink, and arcs showing their minimum capacities.
3. Taking the given flow of 65 as the initial flow pattern, use the labelling procedure on Diagram 2 to find the maximum flow. State clearly your flow augmenting routes.
4. Show the maximum flow on Diagram 3 and write down its value.
5. Verify that this is the maximum flow by finding a cut equal to the flow.

6 [Figures 4, 5 and 6, printed on the insert, are provided for use in this question.]
Water has to be transferred from two mountain lakes \(P\) and \(Q\) to three urban reservoirs \(U\), \(V\) and \(W\). There are pumping stations at \(X , Y\) and \(Z\). The possible routes with the capacities along each edge, in millions of litres per hour, are shown in the following diagram. \includegraphics[max width=\textwidth, alt={}, center]{68ff5b50-6aff-4b28-8fad-d16a8bb4779e-06_862_1316_662_338}

1. On Figure 4, add a super-source, \(S\), and a super-sink, \(T\), and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each of the edges you have added.
2. 1. Find the value of the cut \(C\).
   2. State what can be deduced about the maximum flow from \(S\) to \(T\).
3. On Figure 5, write down the maximum flows along the routes \(S Q Z W T\) and \(S P Y X Z V T\).
4. 1. On Figure 6, add the vertices \(S\) and \(T\) and the edges connecting \(S\) and \(T\) to the network. Using the maximum flows along the routes SQZWT and SPYXZVT found in part (c) as the initial flow, indicate the potential increases and decreases of flow on each edge.
   2. Use flow augmentation to find the maximum flow from \(S\) to \(T\). You should indicate any flow augmenting paths on Figure 5 and modify the potential increases and decreases of the flow on Figure 6.
5. State the value of the flow from \(Y\) to \(X\) in millions of litres per hour when the maximum flow is achieved.

8. \begin{figure}[h] \end{figure} The network in Fig. 4 models a drainage system. The number on each arc indicates the capacity of that arc, in litres per second.

1. Write down the source vertices. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{195b1c1f-5ce3-4762-80c3-34c26382b88b-008_521_1402_1170_343}
   \end{figure} Figure 5 shows a feasible flow through the same network.
2. State the value of the feasible flow shown in Fig. 5. Taking the flow in Fig. 5 as your initial flow pattern,
3. use the labelling procedure on Diagram 1 to find a maximum flow through this network. You should list each flow-augmenting route you use, together with its flow.
4. Show the maximal flow on Diagram 2 and state its value.
5. Prove that your flow is maximal.

11. A company wishes to transport its products from 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \begin{figure}[h] \end{figure}

1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added.
2. 1. State the maximum flow along \(S F _ { 1 } A B R\) and \(S F _ { 3 } C R\).
   2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles. Taking your answer to part (b)(ii) as the initial flow pattern,
3. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow.
   2. Prove that your final flow is maximal.

12. \begin{figure}[h] \end{figure} 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\), 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.
2. State the maximum flow along
   1. \(W \quad W _ { 1 } \quad A \quad R _ { 1 } \quad R\),
   2. \(W W _ { 3 } \quad C \quad R _ { 2 } \quad R\).
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 flowaugmenting route you use, together with its flow.
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day.

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.
2. 1. Add a supersource, S , and a supersink, T , and corresponding arcs to Diagrams 1 and 2 in the answer book.
   2. Enter the flow value and appropriate capacity on each of the arcs you have added to Diagram 1.
3. Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values along the new arcs from S to T , and along \(\operatorname { arcs } \mathrm { S } _ { 1 } \mathrm {~B}\) and \(\mathrm { AT } _ { 1 }\)
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 3 in the answer book.
6. Prove that your flow is maximal.

2 The diagram below shows a network of pipes with their capacities. \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-04_691_1155_340_424} A supersource is added to the network. Which nodes are connected to the supersource? Tick ( ✓ ) one box. \(A\) and \(B\) □ \(A\) and \(G\) □ \(G\) and \(H\) \includegraphics[max width=\textwidth, alt={}, center]{372edcfa-c3cd-4c83-89e9-2bb5fd9825f1-04_104_108_1822_685} \(H\) and \(I\) □

1 The diagram below shows a network of pipes with their capacities. \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-02_734_1275_630_386} A supersource and a supersink will be added to the network.
To which nodes should the supersource and supersink be connected?
Tick \(( \checkmark )\) one box. □
□
□ \includegraphics[max width=\textwidth, alt={}, center]{c297a67f-65fd-47e0-a60c-d38fd86c6081-02_118_113_2261_1324}

\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\), 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\) \(W_1\) \(A\) \(R_1\) \(R\),
   2. \(W\) \(W_3\) \(C\) \(R_2\) \(R\). [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 use, together with its flow. [5]
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day. [1]

The company has the opportunity to increase the number of vans loads from one of the warehouses \(W_1\), \(W_2\), \(W_3\), to \(A\), \(B\) or \(C\).

1. Determine how the company should use this opportunity so that it achieves a maximal flow. [3]

\includegraphics{figure_4} Figure 4 shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow from sources \(A\) and \(B\) to sinks \(I\), \(J\) and \(K\). Take this as the initial flow pattern.

1. On Diagram 1 in the answer booklet, add a supersource \(S\) and a supersink \(W\) to obtain a capacitated network with a single source and single sink. State the minimum capacities of the arcs you have added. [3]
2. 1. Use the given initial flow and the labelling procedure on Diagram 2 to find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
   2. Verify that your flow is maximal.
   [9]
3. Show your maximum flow pattern on Diagram 3. [2]

\includegraphics{figure_7} In solving a network flow problem using the labelling procedure, the diagram in Figure 7 was created. The arrow on each arc indicates the direction of the flow along that arc. The arrows above and below each arc show the direction and value of the flow as indicated by the labelling procedure.

1. Add a supersource S, a supersink T and appropriate arcs to Diagram 2 in the answer book, and complete the labelling procedure for these arcs. (3)
2. Write down the value of the initial flow shown in Figure 7. (1)
3. Use Diagram 2, the initial flow and the labelling procedure to find the maximal flow of 124 through this network. List each flow-augmenting path you use, together with its flow. (5)
4. Show your flow on Diagram 3 and state its value. (3)
5. Prove that your flow is maximal. (2)

(Total 14 marks)

A company wishes to transport its products from 3 factories \(F_1\), \(F_2\) and \(F_3\) to a single retail outlet \(R\). The capacities of the possible routes, in van loads per day, are shown in Fig. 5. \includegraphics{figure_5}

1. On Diagram 1 in the answer booklet add a supersource \(S\) to obtain a capacitated network with a single source and a single sink. State the minimum capacity of each arc you have added. [2]
2. 1. State the maximum flow along \(SF_1ABR\) and \(SF_2CR\). [2]
   2. Show these maximum flows on Diagram 2 in the answer booklet, using numbers in circles.
   Taking your answer to part (b)(ii) as the initial flow pattern,
3. 1. use the labelling procedure to find a maximum flow from \(S\) to \(R\). Your working should be shown on Diagram 3. List each flow-augmenting route you find together with its flow. [7]
   2. Prove that your final flow is maximal.