7.04f Network problems: choosing appropriate algorithm

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.

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

1. The network shows a flow from \(S\) to \(T\) along a system of pipes, with the capacity in litres per second indicated on each edge. \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-14_510_936_411_552}
   1. Show that the value of the cut shown on the diagram is 36 .
   2. The cut shown on the diagram can be represented as \(\{ S , B \} , \{ A , C , T \}\). Complete the table below to give the value of each of the 8 possible cuts.

      Cut		Value
      \(\{ S \}\)	\(\{ A , B , C , T \}\)	30
      \(\{ S , A \}\)	\(\{ B , C , T \}\)	29
      \(\{ S , B \}\)	\(\{ A , C , T \}\)	36
      \(\{ S , C \}\)	\(\{ A , B , T \}\)	33
      \(\{ S , A , B \}\)	\(\{ C , T \}\)
      \(\{ S , A , C \}\)	\(\{ B , T \}\)
      \(\{ S , B , C \}\)	\(\{ A , T \}\)
      \(\{ S , A , B , C \}\)	\(\{ T \}\)	30

   3. State the value of the maximum flow through the network, giving a reason for your answer. Maximum flow is \(\_\_\_\_\) because \(\_\_\_\_\)
   4. Indicate on the diagram below a possible flow along each edge corresponding to this maximum flow. \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_469_933_406_550}
2. The capacities along \(S C\) and along \(A T\) are each increased by 4 litres per second.
   1. Using your values from part (a)(iv) as the initial flow, indicate potential increases and decreases on the diagram below and use the labelling procedure to find the new 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 diagram. \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_470_935_1315_260}

      Path	Additional Flow

   2. Use your results from part (b)(i) to illustrate the flow along each edge that gives this new maximum flow, and state the value of the new maximum flow. New maximum flow is \(\_\_\_\_\) \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_474_933_2078_550}

3 The diagram below shows a network of pipes with source \(A\) and \(\operatorname { sink } J\). The capacity of each pipe is given by the number on each edge. \includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-08_816_1280_443_386}

1. Find the values of the cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
2. Find by inspection a flow of 60 units, with flows of 25,10 and 25 along \(H J , G J\) and \(I J\) respectively. Illustrate your answer on Figure 1.
3. 1. On a certain day the section \(E H\) is blocked, as shown on Figure 2. Find, by inspection or otherwise, the maximum flow on this day and illustrate your answer on Figure 2.
   2. Show that the flow obtained in part (c)(i) is maximal. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-09_595_1065_376_475}
      \end{figure} (c) \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-09_617_1061_1142_477}
      \end{figure} 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}

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

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.

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?

5 Answer this question on the insert provided. The network represents a system of irrigation channels along which water can flow. The weights on the arcs represent the maximum flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-05_597_1553_479_296}

1. Calculate the capacity of the cut that separates \(\{ S , B , C , E \}\) from \(\{ A , D , F , G , H , T \}\).
2. Explain why neither arc \(S C\) nor arc \(B C\) can be full to capacity. Explain why the arcs \(E F\) and \(E H\) cannot both be full to capacity. Hence find the maximum flow along arc \(H T\). When arc \(H T\) carries its maximum flow, what is the flow along arc \(H G\) ?
3. Show a flow of 58 litres per second on the diagram in the insert, and find a cut of capacity 58. The direction of flow in \(H G\) is reversed.
4. Use the diagram in the insert to show the excess capacities and potential backflows for your flow from part (iii) in this case.
5. Without augmenting the labels from part (iv), write down flow augmenting routes to enable an additional 2 litres per second to flow from \(S\) to \(T\).
6. Show your augmented flow on the diagram in the insert. Explain how you know that this flow is maximal.

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

\begin{figure}[h] \end{figure} Figure 2 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. Calculate the values of cuts \(C _ { 1 }\) and \(C _ { 2 }\).
2. Find the minimum cut and state its value. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{89e3545e-fa4b-47dd-8651-7c8f998df9e7-3_645_1316_1430_338} \captionsetup{labelformat=empty} \caption{Fig. 3}
   \end{figure} Figure 3 shows a feasible flow through the same network.
3. State the values of \(x , y\) and \(z\).
4. 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. State how you know that you have found a maximal flow.
   

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

A town has adopted a one-way system to cope with recent problems associated with congestion in one area. \begin{figure}[h] \end{figure} Figure 3 models the one-way system as a capacitated directed network. The numbers on the arcs are proportional to the number of vehicles that can pass along each road in a given period of time.

1. Find the capacity of the cut which passes through the \(\operatorname { arcs } A E , B F , B G\) and \(C D\).
   (1 mark) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{34728928-2a21-463d-982e-c46ab2dc05c8-6_714_1280_171_333} \captionsetup{labelformat=empty} \caption{Fig. 4}
   \end{figure} Figure 4 shows a feasible flow of 17 through the same network. For convenience, a supersource, \(S\), and a supersink, \(T\), have been used.
2. 1. Use the labelling procedure to find the maximum flow through this network listing each flow-augmenting route you use together with its flow.
   2. Show your maximum flow pattern and state its value.
3. Prove that your flow is the maximum possible through the network.
4. It is suggested that the maximum flow through the network could be increased by making road \(E F\) undirected, so that it has a capacity of 8 in either direction. Using the maximum flow-minimum cut theorem, find the increase in maximum flow this change would allow.

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.
   

2. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The numbers on each arc indicate the maximum capacity of that arc. In addition to the restrictions on flow through the arcs a maximum flow of 6 units is allowed to pass through vertex \(C\).

1. Redraw the network to take into account this restriction.
2. Starting with an initial flow of 6 units along SADT and 6 units along SBT 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.

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

\begin{figure}[h] \end{figure} Figure 2 shows a capacitated, directed network.
The numbers in bold denote the capacities of each arc.
The numbers in circles show a feasible flow of 48 through the network.

1. Find the values of \(x\) and \(y\).
2. 1. Use the labelling procedure to find the maximum flow through this network, listing each flow-augmenting route you use together with its flow.
   2. Show your maximum flow pattern and state its value.
3. 1. Find a minimum cut, listing the arcs through which it passes.
   2. Explain why this proves that the flow found in part (b) is a maximum.
      

4

1. 1. Find the value of the cut given by \(\{ A , B , C , D , F , J \} \{ E , G , H \}\).
      4
      1. (ii) State what can be deduced about the maximum flow through the network.
         4
   2. 1. List the nodes which are sources of the network. 4
   3. (ii) Add a supersource \(S\) to the network. 4
   4. 1. List the nodes which are sinks of the network. 4
   5. (ii) Add a supersink \(T\) to the network.

1 The network represents a system of pipes.
The number on each arc represents the upper capacity for each pipe in \(\mathrm { cm } ^ { 3 } \mathrm {~s} ^ { - 1 }\) \includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-03_691_1067_721_482} The value of the cut \(\{ S , A , B \} \{ C , D , E , T \}\) is \(V \mathrm {~cm} ^ { 3 } \mathrm {~s} ^ { - 1 }\) Find \(V\). Circle your answer.
[0pt] [1 mark]
25303137

1 The network represents a system of pipes.
The number on each arc represents the upper capacity for each pipe in \(\mathrm { cm } ^ { 3 } \mathrm {~s} ^ { - 1 }\) \includegraphics[max width=\textwidth, alt={}, center]{21ed3b4e-a089-4607-b5d6-69d8aac03f31-02_793_1255_731_395} The value of the cut \(\{ S , A , B \} \{ C , D , E , F , T \}\) is \(60 \mathrm {~cm} ^ { 3 } \mathrm {~s} ^ { - 1 }\) The maximum flow through the system is \(M \mathrm {~cm} ^ { 3 } \mathrm {~s} ^ { - 1 }\) What does the value of the cut imply about \(M\) ? Circle your answer. \(M < 60 \quad M \leq 60 \quad M \geq 60 \quad M > 60\)

2 The diagram shows a network of pipes. Each pipe is labelled with its upper capacity in \(\mathrm { m } ^ { 3 } \mathrm {~s} ^ { - 1 }\) \includegraphics[max width=\textwidth, alt={}, center]{ecbeedf5-148e-40ad-b8a2-a7aa3db4a115-03_424_1262_445_388} 2

1. Find the value of the cut \(\{ A , C , D , G , H \} \{ B , E , F , I \}\) 2
2. Write down a cut with a value of \(300 \mathrm {~m} ^ { 3 } \mathrm {~s} ^ { - 1 }\) 2
3. Using the values from part (a) and part (b), state what can be deduced about the maximum flow through the network. Fully justify your answer.

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