Calculate cut capacity

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 4 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. Calculate the values of cut \(C _ { 1 }\) and \(C _ { 2 }\).
2. Find the minimum cut and state its value.
   (2 marks) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_647_1303_1430_347} \captionsetup{labelformat=empty} \caption{Fig. 5}
   \end{figure} Figure 5 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.
   (8 marks)

6. This question should be answered on the sheet provided. 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\).
   (2 marks) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e1fd42f7-c97c-4bf2-92d3-69afc8bb6e29-07_659_1278_196_335} \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. You must list 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.
   (2 marks)
5. An alternative suggestion is to widen a single road in order to increase its capacity. Which road, on its own, could lead to the biggest improvement, and what would be the largest maximum flow this could achieve.
   (2 marks)

6 [Figures 4, 5, 6 and 7, printed on the insert, are provided for use in this question.]

1. The network shows a flow from \(S\) to \(T\) along a system of pipes, with the capacity, in litres per minute, indicated on each edge. \includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_350_878_532_591}
   1. Show that the value of the cut shown on the diagram is 97 .
   2. The cut shown on the diagram can be represented as \(\{ S , C \} , \{ A , B , T \}\). Complete the table on Figure 4, giving the value of each of the 8 possible cuts.
   3. State the value of the maximum flow through the network, giving a reason for your answer.
   4. Indicate on Figure 5 a possible flow along each edge corresponding to this maximum flow.
2. Extra pipes, \(B D , C D\) and \(D T\), are added to form a new system, with the capacity, in litres per minute, indicated on each edge of the network below. \includegraphics[max width=\textwidth, alt={}, center]{3ac580ff-f9c8-4e47-b4ca-97d186b0936c-6_483_977_1724_520}
   1. Taking your values from Figure 5 as the initial flow, use the labelling procedure on Figure 6 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 network.
   2. State the value of the new maximum flow, and, on Figure 7, indicate a possible flow along each edge corresponding to this maximum flow.

7.

1. Define the terms
   1. cut,
   2. minimum cut, as applied to a directed network flow. \includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_844_1465_338_299} The figure above shows a capacitated directed network and two cuts \(C _ { 1 }\) and \(C _ { 2 }\). The number on each arc is its capacity.
2. State the values of the cuts \(C _ { 1 }\) and \(C _ { 2 }\). Given that one of these two cuts is a minimum cut,
3. find a maximum flow pattern by inspection, and show it on the diagram below. \includegraphics[max width=\textwidth, alt={}, center]{a5d69a77-c196-483c-a550-1a55363555af-4_597_1470_1656_296}
4. Find a second minimum cut for this network. In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).
5. State, with a reason, which of these arcs should be added, and the value of the increased flow.

4. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. The numbers in circles represent an initial flow from S to T . Two cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown in Figure 1.

1. Find the capacity of each of the two cuts.
   (2)
2. Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow.
   (3)

4 The network represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). The weights on the arcs represent pipe capacities in gallons per minute. \includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-6_599_1580_402_280}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , D \}\) from \(\{ B , E , F , T \}\).
2. Explain why the arcs \(A C\) and \(A D\) cannot both be full to capacity and why the arcs \(D F\) and \(E F\) cannot both be full to capacity.
3. Draw a diagram to show a flow in which as much as possible flows through vertex \(E\) but none flows through vertex \(A\) and none flows through vertex \(D\). State the maximum flow through vertex \(E\). An engineer wants to find a flow augmenting route to improve the flow from part (iii).
4. (a) Explain why there can be no flow augmenting route that passes through vertex \(A\) but not through vertex \(D\).
   (b) Write down a flow augmenting route that passes through vertex \(D\) but not through vertex \(A\). State the maximum by which the flow can be augmented.
5. Prove that the augmented flow in part (iv)(b) is the maximum flow.
6. A vertex restriction means that the flow through \(E\) can no longer be at its maximum rate. By how much can the flow through \(E\) be reduced without reducing the maximum flow from \(S\) to \(T\) ? Explain your reasoning. The pipe represented by the arc \(B E\) becomes blocked and cannot be used.
7. Draw a diagram to show that, even when the flow through \(E\) is reduced as in part (vi), the same maximum flow from \(S\) to \(T\) is still possible.

4 The network represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). The weights on the arcs represent pipe capacities in gallons per minute. \includegraphics[max width=\textwidth, alt={}, center]{bfdc0280-9979-4bbe-81ba-9b1c36ff8374-6_597_1577_404_283}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , D \}\) from \(\{ B , E , F , T \}\).
2. Explain why the \(\operatorname { arcs } A C\) and \(A D\) cannot both be full to capacity and why the \(\operatorname { arcs } D F\) and \(E F\) cannot both be full to capacity.
3. Draw a diagram to show a flow in which as much as possible flows through vertex \(E\) but none flows through vertex \(A\) and none flows through vertex \(D\). State the maximum flow through vertex \(E\). An engineer wants to find a flow augmenting route to improve the flow from part (iii).
4. (a) Explain why there can be no flow augmenting route that passes through vertex \(A\) but not through vertex \(D\).
   (b) Write down a flow augmenting route that passes through vertex \(D\) but not through vertex \(A\). State the maximum by which the flow can be augmented.
5. Prove that the augmented flow in part (iv)(b) is the maximum flow.
6. A vertex restriction means that the flow through \(E\) can no longer be at its maximum rate. By how much can the flow through \(E\) be reduced without reducing the maximum flow from \(S\) to \(T\) ? Explain your reasoning. The pipe represented by the arc \(B E\) becomes blocked and cannot be used.
7. Draw a diagram to show that, even when the flow through \(E\) is reduced as in part (vi), the same maximum flow from \(S\) to \(T\) is still possible.

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.

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 = \(\_\_\_\_\)

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.

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.

7 The network shows a system of pipes, where \(S\) is the source and \(T\) is the sink.
The capacity, in litres per second, of each pipe is shown on each arc.
The cut shown in the diagram can be represented as \(\{ S , P , R \} , \{ Q , T \}\). \includegraphics[max width=\textwidth, alt={}, center]{ba9e9840-ce27-4ca7-ab05-50461d135445-10_629_1168_616_557} 7

1. Complete the table below to give the value of each of the 8 possible cuts.

   Cut		Value
   \{ S \}	\(\{ P , Q , R , T \}\)	31
   \(\{ S , P \}\)	\(\{ Q , R , T \}\)	32
   \(\{ S , Q \}\)	\(\{ P , R , T \}\)
   \(\{ S , R \}\)	\(\{ P , Q , T \}\)
   \(\{ S , P , Q \}\)	\(\{ R , T \}\)	30
   \(\{ S , P , R \}\)	\(\{ Q , T \}\)	37
   \(\{ S , Q , R \}\)	\(\{ P , T \}\)	35
   \(\{ S , P , Q , R \}\)	\(\{ T \}\)	30

   7
2. State the value of the maximum flow through the network. Give a reason for your answer.
   [0pt] [1 mark] 7
3. Indicate on Figure 1 a possible flow along each arc, corresponding to the maximum flow through the network.
   [0pt] [2 marks] \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{ba9e9840-ce27-4ca7-ab05-50461d135445-11_618_1150_1260_557}
   \end{figure}

2 The network below represents a system of pipes. The numbers on each arc represent the lower and upper capacity for each pipe. \includegraphics[max width=\textwidth, alt={}, center]{59347089-ea4a-4ee6-b40e-1ab78aa7cdc3-03_616_1415_447_310} Find the value of the cut \(\{ A , B , C , D , E \} \{ F , G , H , I \}\).
Circle your answer. 56586370

4 The network below represents a system of water pipes in a geothermal power station. The numbers on each arc represent the lower and upper capacity for each pipe in gallons per second. \includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-04_837_1413_493_312} The water is taken from a nearby river at node \(A\) The water is then pumped through the system of pipes and passes through one of three treatment facilities at nodes \(H , I\) and \(J\) before returning to the river. 4

1. The senior management at the power station want all of the water to undergo a final quality control check at a new facility before it returns to the river. Using the language of networks, explain how the network above could be modified to include the new facility. 4
2. Find the value of the cut \(\{ A , B , C , D , E \} \{ F , G , H , I , J \}\) 4
3. Tim, a trainee engineer at the power station, correctly calculates the value of the cut \(\{ A , B , C , D , E , F \} \{ G , H , I , J \}\) to be 106 gallons per second. Tim then claims that the maximum flow through the network of pipes is 106 gallons per second. Comment on the validity of Tim's claim.

\includegraphics{figure_1} Figure 1 shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from \(B\) to \(L\). Three cuts \(C_1\), \(C_2\) and \(C_3\) are shown on Fig. 1.

1. Find the capacity of each of the three cuts. [3]
2. Verify that the flow of 26 is maximal. [1]

The government aims to maximise the possible flow from \(B\) to \(L\) by using one of two options. Option 1: Build a new road from \(E\) to \(J\) with capacity 5. or Option 2: Build a new road from \(F\) to \(H\) with capacity 3.

1. By considering both options, explain which one meets the government's aim [3]

1. Define the terms
   1. cut,
   2. minimum cut,
   as applied to a directed network flow. [2]

\includegraphics{figure_4} Figure 4 shows a capacitated directed network and two cuts \(C_1\) and \(C_2\). The number on each arc is its capacity.

1. State the values of the cuts \(C_1\) and \(C_2\). [3]

Given that one of these two cuts is a minimum cut,

1. Find a maximum flow pattern by inspection, and show it on the diagram in the answer book. [3]
2. Find a second minimum cut for this network. [1]

In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).

1. State, with a reason, which of these arcs should be added, and the value of the increased flow. [2]

\includegraphics{figure_5} Figure 5 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 Figure 5.

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 Diagram 1 by entering values along arcs AC, CD, DE and DT. [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 Diagram 2. [2]
5. Prove that your flow is maximal. [2]

\includegraphics{figure_6} 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.

1. State the value of the initial flow. [1]
2. State the capacities of cuts \(C_1\) and \(C_2\). [2]

Diagram 3 in the answer book shows the labelling procedure applied to the above network.

1. Using Diagram 3, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow. [5]
2. Prove that the flow is now maximal. [2]

(Total 10 marks)

\includegraphics{figure_5} The diagram above shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from \(B\) to \(L\). Three cuts \(C_1\), \(C_2\) and \(C_3\) are shown on The diagram above.

1. Find the capacity of each of the three cuts. [3]
2. Verify that the flow of 26 is maximal. [1]

The government aims to maximise the possible flow from \(B\) to \(L\) by using one of two options. Option 1: Build a new road from \(E\) to \(J\) with capacity 5. or Option 2: Build a new road from \(F\) to \(H\) with capacity 3.

1. By considering both options, explain which one meets the government's aim [3]