7.04f Network problems: choosing appropriate algorithm

6. This question is to be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 4 shows a capacitated network. The numbers on each arc indicate the capacity of that arc in appropriate units.

1. Explain why it is not possible to achieve a flow of 30 through the network from \(S\) to \(T\).
2. State the maximum flow along
   1. \(S A B T\)
   2. SCET.
3. Show these flows on Diagram 1 of the answer sheet.
4. Taking your answer to part (c) as the initial flow pattern, use the labelling procedure to find the maximum flow from \(S\) to \(T\). Show your working on Diagram 2. List each flow-augmenting path you use together with its flow.
5. Indicate a maximum flow on Diagram 3.
6. Prove that your flow is maximal.

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.

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Five tour guides, Alice, Emily, George, Rose and Weidi, need to be assigned to five coach trips, 1, 2, 3, 4 and 5 . A bipartite graph showing their preferences is given in Figure 1 and an initial matching is given in Figure 2.

1. Use the maximum matching algorithm, starting with vertex G , to increase the number of matchings. State the alternating path you used.
2. List the improved matching you found in (a).
3. Explain why a complete matching is not possible. Weidi agrees to be assigned to coach trip 3, 4 or 5.
4. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching.
   (3)

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

1. State the values of \(x\) and \(y\).
2. List the saturated arcs.
3. State the value of the feasible flow.
4. State the capacities of the cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\), and \(\mathrm { C } _ { 3 }\).
5. By inspection, find a flow-augmenting route to increase the flow by one unit. You must state your route.
6. Prove that the new 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.

1. \begin{figure}[h] \end{figure} Figure 1 shows a directed, capacitated network where the number on each arc is its capacity. A possible flow is shown from \(S\) to \(T\) and the value in brackets on each arc is the flow in that arc.

1. Find the values of \(x , y\) and \(z\).
2. Find, by inspection, the maximal flow from \(S\) to \(T\) and verify that it is maximal.
   (2)

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. 1. Explain why arc \(A D\) must be at its lower capacity.
         [0pt] [1 mark] 6
      2. 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
   2. 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
      2. 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
      3. Prove the flow found in part
      (d) (ii) is maximum.
      6
   3. (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]

3. \begin{figure}[h] \end{figure} Figure 1 models the flow of fluid through a system of pipes from a source, S , to a sink, T . The weights on the arcs show the capacities of the corresponding pipes in litres per minute. Two cuts \(C _ { 1 }\) and \(C _ { 2 }\) are shown.

1. Find 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 possible flow through the system.
3. On Diagram 1 in the answer book, show how a flow of 120 litres per minute from S to T can be achieved. You do not need to apply the labelling procedure to find this flow.
4. Prove that 120 litres per minute is the maximum possible flow through the system. A new pipe is planned from S to A . Let the capacity of this pipe be \(x\) litres per minute.
5. Find, in terms of \(x\) where necessary, the maximum possible flow through the new system.

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.

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

1. 1. Find the value of \(x\).
   2. Find the value of \(y\).
2. List the saturated arcs. Two cuts, \(C _ { 1 }\) and \(C _ { 2 }\), are shown in Figure 1.
3. Find the capacity of
   1. \(C _ { 1 }\)
   2. \(\mathrm { C } _ { 2 }\)
4. Write down a flow-augmenting route, using the arc CF, that increases the flow by two units. Given that the flow through the network is increased by two units using the route found in (d), (e) prove that this new flow is maximal.

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} Figure 1 shows a capacitated, directed network of pipes. The number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent a feasible flow from S to T.

1. State the value of this flow.
2. List the eight saturated arcs.
3. Explain why arc EH can never be full to capacity.
4. Find the capacity of
   1. cut \(C _ { 1 }\)
   2. cut \(C _ { 2 }\)
5. Write down a flow-augmenting route that increases the flow by three units. Given that the flow through the network is increased by three units,
6. prove that this new flow is maximal.

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.

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

1. State the value of this flow.
   (1)
2. Explain why arcs CD and CG cannot both be saturated.
   (1)
3. Find the capacity of
   1. cut \(C _ { 1 }\)
   2. cut \(C _ { 2 }\)
4. Write down a flow augmenting route of weight 6 which saturates BF. The flow augmenting route in part (d) is applied to give an increased flow.
5. Prove that this increased flow is maximal.

3. \begin{figure}[h] \end{figure} Figure 5 represents a network of corridors in a school. The number on each arc represents the maximum number of students, per minute, that may pass along each corridor at any one time. At 11 am on Friday morning, all students leave the hall (S) after assembly and travel to the cybercafé ( T ). The numbers in circles represent the initial flow of students recorded at 11 am one Friday.

1. State an assumption that has been made about the corridors in order for this situation to be modelled by a directed network.
2. Find the value of x and the value of y , explaining your reasoning. Five new students also attend the assembly in the hall the following Friday. They too need to travel to the cybercafé at 11 am . They wish to travel together so that they do not get lost. You may assume that the initial flow of students through the network is the same as that shown in Figure 5 above.
3. 1. List all the flow augmenting routes from S to T that increase the flow by at least 5
   2. State which route the new students should take, giving a reason for your answer.
4. Use the answer to part (c) to find a maximum flow pattern for this network and draw it on Diagram 1 in the answer book.
5. Prove that the answer to part (d) is optimal. The school is intending to increase the number of students it takes but has been informed it cannot do so until it improves the flow of students at peak times. The school can widen corridors to increase their capacity, but can only afford to widen one corridor in the coming term.
6. State, explaining your reasoning,
   1. which corridor they should widen,
   2. the resulting increase of flow through the network.

4. \begin{figure}[h] \end{figure} Direct roads between six cities, A, B, C, D, E and F, are represented in Figure 3. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd's algorithm is to be used to find the complete network of shortest times between the six cities.
An initial route matrix is given in the answer book.

1. Set up the initial time matrix.
2. Perform the first iteration of Floyd's algorithm. You should show the time and route matrices after this iteration. The final time matrix after completion of Floyd's algorithm is shown below.

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	A	B	C	D	E	F
   A	-	57	95	147	63	220
   B	57	-	72	204	120	197
   C	95	72	-	242	158	125
   D	147	204	242	-	84	275
   E	63	120	158	84	-	191
   F	220	197	125	275	191	-

   A route is needed that minimises the total time taken to traverse each road at least once.
   The route must start at B and finish at E .
3. Use an appropriate algorithm to find the roads that will need to be traversed twice. You should make your method and working clear.
4. Write down the length of the route.

3. \begin{figure}[h] \end{figure} In Figure 1 the weight of \(\operatorname { arc } \mathrm { SB }\) is denoted by \(x\) where \(x \geqslant 0\)

1. Explain why Dijkstra's algorithm cannot be used on the directed network in Figure 1.
   (1) It is given that the minimum weight route from S to T passes through B .
2. Use dynamic programming to find
   1. the range of possible values of \(x\)
   2. the minimum weight route from S to T .
      (12)

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. This question should be answered on the sheet provided in the answer booklet. \begin{figure}[h] \end{figure} Figure 3 shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. State the maximum flow along
   1. SAET,
   2. SBDT,
   3. SCFT.
      (3 marks)
2. Show these maximum flows on Diagram 1 on the answer sheet.
3. Taking your answer to part (b) as the initial flow pattern, use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2. List each flow augmenting route you find, together with its flow.
4. Indicate a maximum flow on Diagram 3.
5. Prove that your flow is maximal.

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 2 and 3, printed on the insert, are provided for use in this question.]
The diagram shows a network of pipelines through which oil can travel. The oil field is at \(S\), the refinery is at \(T\) and the other vertices are intermediate stations. The weights on the edges show the capacities in millions of barrels per hour that can flow through each pipeline. \includegraphics[max width=\textwidth, alt={}, center]{be283950-ef4c-482f-94cb-bdb3def9ff6d-06_956_1470_593_283}

1. 1. Find the value of the cut marked \(C\) on the diagram.
   2. Hence make a deduction about the maximum flow of oil through the network.
2. State the maximum possible flows along the routes \(S A B T , S D E T\) and \(S F T\).
3. 1. Taking your answer to part (b) as the initial flow, use a labelling procedure on Figure 2 to find the maximum flow from \(S\) to \(T\). Record your routes and flows in the table provided and show the augmented flows on the network diagram. (6 marks)
   2. State the value of the maximum flow, and, on Figure 3, illustrate a possible flow along each edge corresponding to this maximum flow.
   3. Prove that your flow in part (c)(ii) is a maximum.

      Surname

      Other Names

      Centre Number

      Candidate Number

      Candidate Signature

      \section*{General Certificate of Education
      January 2007
      Advanced Level Examination} \section*{MATHEMATICS
      Unit Decision 2} MD02 \section*{Insert} Insert for use in Questions 1 and 6.
      Fill in the boxes at the top of this page.
      Fasten this insert securely to your answer book.

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.

6 [Figures 4 and 5, printed on the insert, are provided for use in this question.]
The network shows the routes along corridors from two arrival gates to the passport control area, \(P\), in a small airport. The number on each edge represents the maximum number of passengers that can travel along a particular corridor in one minute. \includegraphics[max width=\textwidth, alt={}, center]{6c407dbf-efe5-49e4-881f-91e7de5c46d9-7_933_1063_552_486}

1. State the vertices that represent the arrival gates.
2. Find the value of the cut shown on the network.
3. State the maximum flow along each of the routes UTSP and RQVP.
4. 1. Taking your answers to part (c) as the initial flow, use the labelling procedure on Figure 4 to find the maximum flow through the network. You should indicate any flow augmenting paths 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 5, illustrate a possible flow along each edge corresponding to this maximum flow.
5. On a particular day, there is an obstruction allowing no more than 50 passengers per minute to pass through vertex \(V\). State the maximum number of passengers that can move through the network per minute on this particular day.
   (2 marks)