7.02p Networks: weighted graphs, modelling connections

3 Answer this question on the insert provided. \begin{figure}[h] \end{figure} Fig. 1 represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). It also shows a cut \(\alpha\). The weights on the arcs show the lower and upper capacities of the pipes in litres per second.

1. Calculate the capacity of the cut \(\alpha\).
2. By considering vertex \(B\), explain why arc \(S B\) must be at its lower capacity. Then by considering vertex \(E\), explain why arc \(C E\) must be at its upper capacity, and hence explain why arc \(H T\) must be at its lower capacity.
3. On the diagram in the insert, show a flow through the network of 15 litres per second. Write down one flow augmenting route that allows another 1 litre per second to flow through the network. Show that the maximum flow is 16 litres per second by finding a cut of 16 litres per second. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c5bfbe78-64c4-4254-ad83-0c90f4a54b18-4_602_1086_1809_568} \captionsetup{labelformat=empty} \caption{Fig. 2}
   \end{figure} Fig. 2 represents the same system, but with pipe \(E B\) installed the wrong way round.
4. Explain why there can be no feasible flow through this network.

5 Answer this question on the insert provided. The network represents a system of pipes through which fluid can flow from a source, S , to a sink, T . \includegraphics[max width=\textwidth, alt={}, center]{09d4aacd-026b-4d81-a826-3d3f29f9c105-5_1310_1301_447_424} The arrows are labelled to show excess capacities and potential backflows (how much more and how much less could flow in each pipe). The excess capacities and potential backflows are measured in litres per second. Currently the flow is 6 litres per second, all flowing along a single route through the system.

1. Write down the route of the 6 litres per second that is flowing from \(S\) to \(T\).
2. What is the capacity of the pipe AG and in which direction can fluid flow along this pipe?
3. Calculate the capacity of the \(\operatorname { cut } \mathrm { X } = \{ \mathrm { S } , \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \} , \mathrm { Y } = \{ \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { I } , \mathrm { T } \}\).
4. Describe how a further 7 litres per second can flow from S to T and update the labels on the arrows to show your flow. Explain how you know that this is the maximum flow. {}

5 Consider the problem given below: $$\begin{array} { l l } \text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF } \\ \text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1 \\ & \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5 \\ & \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 , \\ & \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1 \end{array}$$

1. Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables \(\mathrm { AB } , \mathrm { AC } , \ldots\) correspond to arcs in a network. The weight on each arc is the coefficient of the corresponding variable in the objective function.
2. Draw the network on the vertices in the Printed Answer Booklet. A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
3. Explain what is ensured by the constraint \(\mathrm { AB } + \mathrm { AC } \geqslant 1\). Julie claims that the solution to the problem will give the minimum spanning tree for the network.
4. Find the minimum spanning tree for the network.
   Kim has a different network, exactly one of the arcs in this network is a directed arc.
   Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.
5. Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

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)

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]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-005_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.

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}

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.

5. \begin{figure}[h] \end{figure} Figure 2 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 capacities and upper capacities for the corresponding pipes, in litres per second.

1. State the source node.
2. Explain why the sink node must be G.
3. Calculate the capacity of the cut \(C _ { 1 }\)
4. Assuming that a feasible flow exists,
   1. explain why arc JH must be at its upper capacity,
   2. explain why arcs AD and CD must be at their lower capacities.
5. Use Diagram 1 in the answer book to show a flow of 18 litres per second through the system.
6. Prove that the answer to (e) is the maximum flow through the system.

1. Four workers, A, B, C and D, are to be assigned to four tasks, 1, 2, 3 and 4. Each task must be assigned to just one worker and each worker must do only one task.

The cost of assigning each worker to each task is shown in the table below.
The total cost is to be minimised.

1. Reducing rows first, use the Hungarian algorithm to obtain an allocation that minimises the total cost. You must make your method clear and show the table after each stage.
2. State the minimum total cost.
   

4. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network of pipes. The uncircled number on each arc represents the capacity of the corresponding pipe. The numbers in circles represent an initial flow.

1. List the saturated arcs.
2. State the value of the initial flow.
3. Explain why arc FT cannot be full to capacity.
4. State the capacity of cut \(C _ { 1 }\) and the capacity of cut \(C _ { 2 }\)
5. By inspection find one flow-augmenting route to increase the flow by three units. You must state your route.
6. Prove that, once the flow-augmenting route found in part (e) has been applied, the flow is maximal.

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]

Six people, \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake. \includegraphics{figure_1}

1. Represent this information in an adjacency matrix. [2]
2. Initially, \(B\) is assigned to task 5, \(D\) to task 2, \(E\) to task 4 and \(F\) to task 3. Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task. [5]

\includegraphics{figure_4} 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. [2]

\includegraphics{figure_5} Figure 5 shows a feasible flow through the same network.

1. State the value of the feasible flow shown in Fig. 5. [1]

Taking the flow in Fig. 5 as your initial flow pattern,

1. 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]
2. Show the maximal flow on Diagram 2 and state its value. [3]
3. Prove that your flow is maximal. [2]

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.

\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\) and 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_1W_1R_1R\),
   2. \(W_2CR_2R\).
   [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 find together with its flow. [5]
4. From your final flow pattern, determine the number of van loads passing through \(B\) each day. [1]

\includegraphics{figure_1} Figure 1 shows a capacitated directed network. The number on each arc is its capacity. \includegraphics{figure_2} Figure 2 shows a feasible initial flow through the same network.

1. Write down the values of the flow \(x\) and the flow \(y\). [2]
2. Obtain the value of the initial flow through the network, and explain how you know it is not maximal. [2]
3. Use this initial flow and the labelling procedure on Diagram 1 below to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. Diagram 1 \includegraphics{figure_3} [5]
4. Show your maximal flow pattern on Diagram 2. Diagram 2 \includegraphics{figure_4} [2]
5. Prove that your flow is maximal. [2]

(Total 13 marks)

The following matrix gives the capacities of the pipes in a system. \begin{array}{c|c|c|c|c|c|c|c} To & & S & T & A & B & C & D
From & & & & & & &
\hline S & & -- & -- & 16 & 26 & -- & --
T & & -- & -- & -- & -- & -- & --
A & & -- & -- & -- & -- & 13 & 5
B & & -- & 16 & -- & -- & -- & 11
C & & -- & 11 & -- & -- & -- & --
D & & -- & 11 & -- & -- & -- & --
\end{array}

1. Represent this information as a digraph. [3 marks]
2. Find the minimum cut, expressing it in the form \(\{\) \(\}|\{\) \(\}\), and state its value. [2 marks]
3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow. [5 marks]
4. Explain how you know that this flow is maximal. [1 mark]

[11 marks]

The diagram shows a network of pipes. Each pipe is labelled with its upper capacity in \(\mathrm{m}^3 \mathrm{s}^{-1}\) \includegraphics{figure_3}

1. Find the value of Cut \(X\) [1 mark]
2. Find the value of Cut \(Y\) [1 mark]
3. Add a supersink \(T\) to the network. [2 marks]

The diagram below shows a network of pipes. \includegraphics{figure_8} The uncircled numbers on each arc represent the capacity of each pipe in m³ s⁻¹ The circled numbers on each arc represent an initial feasible flow, in m³ s⁻¹, through the network. The initial flow through pipe \(SD\) is \(x\) m³ s⁻¹ The initial flow through pipe \(DC\) is \(y\) m³ s⁻¹ The initial flow through pipe \(CB\) is \(z\) m³ s⁻¹

1. By considering the flows at the source and the sink, explain why \(x = 7\) [3 marks]
2. 1. State the value of \(y\) [1 mark]
   2. State the value of \(z\) [1 mark]
3. Prove that the maximum flow through the network is at most 27 m³ s⁻¹ [2 marks]

Figure 1 shows a network of gas pipes. The numbers on each arc represent the lower and upper capacity for each pipe in \(\text{m}^3 \text{s}^{-1}\) The numbers in the circles represent an initial feasible flow of 73 \(\text{m}^3 \text{s}^{-1}\) through the network. \includegraphics{figure_8}

1. On Figure 1 above, add a supersink \(T\) to the network. [2 marks]
2. Using flow augmentation, find the maximum flow through the network. You must indicate any flow augmenting paths clearly in the table below. You may use Figure 2, on the page opposite, in your solution. [4 marks]

   Augmenting Path	Flow

   Maximum flow \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
3. Prove that the flow found in part (b) is the maximum flow through the network. [2 marks]
4. A trainee engineer claims that increasing the upper capacity of the pipe \(AG\) will increase the maximum flow through the network, as the flow through this pipe cannot currently be increased. Comment on the validity of the trainee's claim. [2 marks]

Figure 1 shows a network of water pipes. The number on each arc represents the upper capacity for each pipe in litres per second. The numbers in the circles represent an initial feasible flow of 103 litres per second. \includegraphics{figure_1}

1. On Figure 1 above, add a supersource \(S\) and a supersink \(T\) to the network. [2 marks]
2. Using flow augmentation, find the maximum flow through the network. You must indicate any flow augmenting paths clearly in the table below. You may use Figure 2, on the opposite page, in your solution. [4 marks]

   Augmenting Path	Extra Flow

   Maximum Flow ______________ litres per second
3. While the flow through the network is at its maximum value, the pipe \(EG\) develops a leak. To repair the leak, an engineer turns off the flow of water through \(EG\) The engineer claims that the maximum flow of water through the network will reduce by 31 litres per second. Comment on the validity of the engineer's claim. [2 marks]