State maximum flow along specific routes

8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge. \includegraphics[max width=\textwidth, alt={}, center]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-22_743_977_404_536}

1. Find the maximum flow along each of the routes \(A B E H , A C F H\) and \(A D G H\) and enter their values in the table on Figure 4 opposite.
2. 1. Taking your answers to part (a) 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 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 5 opposite, 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{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4}

   Route	Flow
   \(A B E H\)
   \(A C F H\)
   \(A D G H\)

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_746_972_397_845}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-23_739_971_1311_539}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{3ba973a1-6a45-4381-b634-e9c4673ef1fb-24_2253_1691_221_153}

5 The network shows the evacuation routes along corridors in a college, from two teaching areas to the exit, in case of a fire alarm sounding. \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-14_729_1013_434_497} The two teaching areas are at \(A\) and \(G\) and the exit is at \(X\). The number on each edge represents the maximum number of people that can travel along a particular corridor in one minute.

1. Find the value of the cut shown on the diagram.
2. Find the maximum flow along each of the routes \(A B D X , G F B X\) and \(G H E X\) and enter their values in the table on Figure 3 opposite.
3. 1. Taking your answers to part (b) as the initial flow, use 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.
4. During one particular fire drill, there is an obstruction allowing no more than 45 people per minute to pass through vertex \(B\). State the maximum number of people that can move through the network per minute during this fire drill. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_905_1559_331_292}
   \end{figure} Figure 4 \includegraphics[max width=\textwidth, alt={}, center]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-15_689_851_1370_598} Maximum flow is \(\_\_\_\_\) people per minute.

9. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-6_540_1291_203_411} This diagram shows a capacitated directed network. The number on each arc is its capacity.

1. State the maximum flow along
   1. SADT,
   2. SCET,
   3. \(S B F T\).
2. Show these maximum flows on Diagram 1 below. \section*{Diagram 1}
   \includegraphics[max width=\textwidth, alt={}]{be329a47-a709-4719-abe6-41d388a6c631-6_561_1187_1283_721}
   Take your answer to part (b) as the initial flow pattern.
3. 1. Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 below. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_718_1525_205_269}
   2. Draw your final flow pattern on Diagram 3 below. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-7_611_1196_1082_717}
   3. Prove that your flow is maximal.
4. Give an example of a practical situation that could have been modelled by the original network.

4

1. \includegraphics[max width=\textwidth, alt={}, center]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_725_276_751}
2. \(\_\_\_\_\)
3. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour
4. \(\_\_\_\_\) = \(\_\_\_\_\) gallons per hour \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(v)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_671_729_1822_315}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{(vi)} \includegraphics[alt={},max width=\textwidth]{95fbb09b-0301-4fc1-b694-838b8d0b64a6-11_677_735_1816_1171}
   \end{figure} Maximum flow = \(\_\_\_\_\) gallons per hour

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.

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.
   (1 mark)
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.
   (6 marks)
4. Indicate a maximum flow on Diagram 3.
   (2 marks)
5. Prove that your flow is maximal.
   (2 marks)

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.

8 The network below represents a system of pipes. The capacity of each pipe, in litres per second, is indicated on the corresponding edge. \includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-146_743_977_404_536}

1. Find the maximum flow along each of the routes \(A B E H , A C F H\) and \(A D G H\) and enter their values in the table on Figure 4 opposite.
2. 1. Taking your answers to part (a) 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 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 5 opposite, 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{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4}

   Route	Flow
   \(A B E H\)
   \(A C F H\)
   \(A D G H\)

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-147_746_972_397_845}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-147_739_971_1311_539}
   \end{figure}

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 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)

4 [Figures 4 and 5, printed on the insert, are provided for use in this question.]
The network shows the routes along corridors from the playgrounds \(A\) and \(G\) to the assembly hall in a school. The number on each edge represents the maximum number of pupils that can travel along the corridor in one minute. \includegraphics[max width=\textwidth, alt={}, center]{587bccdf-abd7-4a08-a76e-61374f322e2e-04_1043_1573_559_228}

1. State the vertex that represents the assembly hall.
2. Find the value of the cut shown on the diagram.
3. State the maximum flow along the routes \(A B D\) and \(G E D\).
4. 1. Taking your answers to part (c) as the initial flow, use a labelling procedure on Figure 4 to find the maximum flow through 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.
   3. Verify that your flow is a maximum flow by finding a cut of the same value.
5. On a particular day, there is an obstruction allowing no more than 15 pupils per minute to pass through vertex \(E\). State the maximum number of pupils that can move through the network per minute on this particular day.

This question should be answered on the sheet provided in the answer booklet. \includegraphics{figure_3} 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. [1 mark]
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. [6 marks]
4. Indicate a maximum flow on Diagram 3. [2 marks]
5. Prove that your flow is maximal. [2 marks]

\includegraphics{figure_4} Figure 4 shows a capacitated directed network. The number on each arc is its capacity.

1. State the maximum flow along
   1. \(SADT\),
   2. \(SCET\),
   3. \(SBFT\). [2]
2. Show these maximum flows on Diagram 1 in the answer book. [1]

Take your answer to part (b) as the initial flow pattern.

1. 1. Use the labelling procedure to find a maximum flow from \(S\) to \(T\). Your working should be shown on Diagram 2 in the answer book. List each flow-augmenting route you use, together with its flow. [5]
   2. Draw your final flow pattern on Diagram 3 in the answer book. [2]
   3. Prove that your flow is maximal. [3]
2. Give an example of a practical situation that could have been modelled by the original network. [1]