7.04f Network problems: choosing appropriate algorithm

4. A group of students and teachers from a performing arts college are attending the Glasenburgh drama festival. All of the group want to see an innovative modern production of the play 'The Decision is Final'. Unfortunately there are not enough seats left for them all to see the same performance. There are three performances of the play, 1,2 , and 3 . There are two types of ticket, Adult and Student. Student tickets will be purchased for the students and Adult tickets for the teachers. The table below shows the price of tickets for each performance of the play. There are 18 teachers and 200 students requiring tickets. There are 94,65 and 80 seats available for performances 1,2 , and 3 espectively.

1. Complete the table below.

   	Adult	Student	Dummy	Seats available
   Performance 1	£5.00	£4.50
   Performance 2	£4.20	£3.80
   Performance 3	£4.60	£4.00
   Tickets needed

2. Explain why a dummy column was added to the table above.
3. Use the north-west corner method to obtain a possible solution.
4. Taking the most negative improvement index to indicate the entering square, use the stepping stone method once to obtain an improved solution. You must make your shadow costs and improvement indices clear. After a further iteration the table becomes:

   	Adult	Student	Dummy
   Performance 1		73	21
   Performance 2	18	47
   Performance 3		80

5. Demonstrate that this solution gives the minimum cost, and find its value.
   (Total 16 marks)

5. \begin{figure}[h] \end{figure} In solving a network flow problem using the labelling procedure, the diagram in Figure 1 was created.
The arrow on each arc indicates the direction of the flow along that arc.
The arrows above and below each arc show the direction and value of the flow as indicated by the labelling procedure.

1. Add a supersource S , a supersink T and appropriate arcs to the diagram above, and complete the labelling procedure for these arcs.
2. Write down the value of the initial flow shown in Figure 1.
3. Use Figure 2 below, the initial flow and the labelling procedure to find the maximal flow of 124 through this network. List each flow-augmenting path you use, together with its flow.
4. Show your flow on the diagram below and state its value. \includegraphics[max width=\textwidth, alt={}, center]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-4_967_1520_114_214}
5. Prove that your flow is maximal.
   (2)
   (Total 14 marks)

9. \begin{figure}[h] \end{figure}

1. State the value of the initial flow.
2. State the capacities of cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\). Figure 2 shows the labelling procedure applied to the above network.
3. Using Figure 2, increase the flow by a further 19 units. You must list each flow-augmenting path you use, together with its flow.
4. Prove that the flow is now maximal. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{0e86cb18-2c6e-49f1-b235-aa15eb83e260-8_2146_1038_127_422} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure}

1. The diagram above 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.

3. Jameson cars are made in two factories A and B. Sales have been made at the two main showrooms in London and Edinburgh. Cars are to be transported from the factories to the showrooms. The table below shows the cost, in pounds, of transporting one car from each factory to each showroom. It also shows the number of cars available at each factory and the number required at each showroom. It is decided to use the transportation algorithm to obtain a minimal cost solution.

1. Explain why it is necessary to add a dummy demand point.
2. Complete the table below.

   	L	E	Dummy	Supply
   A	80	70		55
   B	60	50		45
   Demand	35	60		100

3. Use the north-west corner rule to obtain a possible pattern of distribution.
   (1)
4. Taking the most negative improvement index to indicate the entering square, use the stepping-stone method to obtain an optimal solution. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.
   (7)
5. State the cost of your optimal solution.
   (1) (Total 13 marks)

6. Four salespersons, Joe, Min-Seong, Olivia and Robert, are to attend four business fairs, \(A , B , C\) and \(D\). Each salesperson must attend just one fair and each fair must be attended by just one salesperson. The expected sales, in thousands of pounds, that each salesperson would make at each fair is shown in the table below.

1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that maximises the total expected sales from the four salespersons. You must make your method clear and show the table after each stage.
2. State all possible optimal allocations and the optimal total value.
   (4)(Total 14 marks)

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.
   (1)
2. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { SB } , \mathrm { BD } , \mathrm { CF }\) and FT .
   (2)
3. 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.
   (4)
4. Draw a maximal flow pattern on Diagram 2 in your answer book.
   (2)
5. Prove that your flow is maximal.
   (2)

5. \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. 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.
2. Complete the initialisation of the labelling procedure on Diagram 2 by entering values along the new arcs from \(S\) and \(T\), and along \(A B , A D\) and \(D _ { 2 }\).
3. 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.
4. Draw a maximal flow pattern on Diagram 3 in the answer book.
5. Prove that your flow is maximal.

5. \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. Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along \(\mathrm { SC } , \mathrm { AB } , \mathrm { CE } , \mathrm { DE }\) and DT .
   (2)
3. 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.
   (4)
4. Draw a maximal flow pattern on Diagram 2 in the answer book.
   (2)
5. Prove that your flow is maximal.
   (2)

4. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated network. The capacity of each arc is shown on the arc. Two cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\) are shown.

1. Find the capacity of each of the two cuts. Given that one of these two cuts is a minimum cut,
2. write down the maximum possible flow through the network. Given that the network now has a maximal flow from S to T ,
3. determine the flow along arc SB.
4. Explain why arcs GF and GT cannot both be saturated. Given that arcs EC, AD and DF are saturated and that there is no flow along arc GF,
5. determine a maximum flow pattern for this network and draw it on Diagram 1 in the answer book. You do not need to use the labelling procedure to determine the maximum flow.

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 an initial flow.

1. List the saturated arcs.
2. State the value of the initial flow.
3. State the capacities of the cuts \(C _ { 1 }\) and \(C _ { 2 }\)
4. By inspection, find a flow-augmenting route to increase the flow by three units. You must state your route.
5. Prove that the new flow is maximal.

3 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are the capacities in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}

1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
2. Explain why the capacity of the cut \(\alpha\), shown on the diagram, is only 21 litres per second.
3. Explain why neither of the arcs \(S C\) and \(A D\) can be full to capacity. Give the maximum flow in \(\operatorname { arc } S B\).
4. Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.

5

1. Capacity = \(\_\_\_\_\)
2. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}
3. Route: \(\_\_\_\_\) Flow \(=\) \(\_\_\_\_\)
4. Maximum flow = \(\_\_\_\_\) Cut: \(\mathrm { X } = \{\) \} \(\quad \mathrm { Y } = \{\)
5. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}

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 The diagram represents a system of pipes through which fluid can flow from a source, \(S\), to a sink, \(T\). It also shows two cuts, \(\alpha\) and \(\beta\). The weights on the arcs show the lower and upper capacities of the pipes in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{1ceb5585-6d3f-4723-ad49-7addfb40ab66-6_818_1285_434_429}

1. Calculate the capacities of the cuts \(\alpha\) and \(\beta\).
2. Explain why the arcs \(A C\) and \(A F\) cannot both be at their lower capacities.
3. Explain why the \(\operatorname { arcs } B C , B D , D E\) and \(D T\) must all be at their lower capacities.
4. Show that a flow of 10 litres per second is impossible. Deduce the minimum and maximum feasible flows, showing your working. Vertex \(E\) becomes blocked so that no fluid can flow through it.
5. Draw a copy of the network with this vertex restriction. You are advised to make your diagram quite large. Show a flow of 9 litres per second on your diagram.

4 Answer parts (v) and (vi) of this question on the insert provided. The diagram represents a system of pipes through which fluid can flow. The weights on the arcs show the lower and upper capacities of the pipes in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{33995efa-7ede-4e83-89d3-7b6c8be8d955-4_703_789_479_678}

1. Which vertex is the source and which vertex is the sink?
2. Cut \(\alpha\) partitions the vertices into the sets \(\{ A , B , C \} , \{ D , E , F , G , H , I \}\). Calculate the capacity of cut \(\alpha\).
3. Explain why partitioning the vertices into sets \(\{ A , D , G \} , \{ B , C , E , F , H , I \}\) does not give a cut.
4. (a) How many litres per second must flow along arc \(D G\) ?
   (b) Explain why the arc \(A D\) must be at its upper capacity. Hence find the flow in \(\operatorname { arc } B A\).
   (c) Explain why at least 7 litres per second must flow along arc \(B C\).
5. Use the diagrams in the insert to show a minimum feasible flow and a maximum feasible flow. The upper capacity of \(B C\) is now increased from 8 to 18 .
6. (a) Use the diagram in the insert to show a flow of 19 litres per second.
   (b) List the saturated arcs when 19 litres per second flows through the network. Hence, or otherwise, find a cut of capacity 19 .
7. Explain how your answers to part (vi) show that 19 litres per second is the maximum flow.

4 The diagram represents a system of roads through which traffic flows from a source, \(S\), to a sink, \(T\). The weights on the arcs show the capacities of the roads in cars per minute. \includegraphics[max width=\textwidth, alt={}, center]{3a47bac8-0067-4acb-a3c7-7d8512403cca-5_414_1080_349_488}

1. (a) The cut \(\alpha\) partitions the vertices into the sets \(\{ S , A , B , C \} , \{ D , E , F , T \}\). Calculate the capacity of cut \(\alpha\).
   (b) The cut \(\beta\) partitions the vertices into the sets \(\{ S , A , B , D \} , \{ C , E , F , T \}\). Calculate the capacity of cut \(\beta\).
   (c) Using only the capacities of cuts \(\alpha\) and \(\beta\), what can you deduce about the maximum possible flow through the system?
2. Explain why partitioning the vertices into sets \(\{ S , A , D , T \} , \{ B , C , E , F \}\) does not give a cut.
3. What do the double arcs between \(D\) and \(E\) and between \(E\) and \(F\) represent?
4. Explain why the maximum possible flow along \(C F\) must be less than 45 cars per minute.
5. (a) Show how a flow of 60 cars per minute along \(F T\) can be achieved.
   (b) Show that 60 cars per minute is the maximum possible flow through the system. An extra road is opened linking \(S\) to \(C\). Let the capacity of this road be \(x\) cars per minute.
6. Find the maximum possible flow through the new system, in terms of \(x\) where necessary, for the different possible values of \(x\).

4 The diagram represents a system of pipes through which fluid can flow from two sources, \(S _ { 1 }\) and \(S _ { 2 }\), to a sink, \(T\). Most of the pipes have valves which restrict the flow to one direction only. However, the flow in arc \(D E\) can be in either direction. The weights on the arcs show the lower capacities and the upper capacities of the pipes in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{fc01c62e-64bd-4fbc-ac1e-cdfa47c07228-5_565_1130_447_463}

1. Add a supersource, \(S\), to the copy of the diagram in the answer book, and weight the arcs attached to it with appropriate lower and upper capacities.
2. The cut \(\alpha\) partitions the vertices into the sets \(\left\{ S , S _ { 1 } , S _ { 2 } , A , C \right\} , \{ B , D , E , T \}\). By considering the cut arcs only, calculate the maximum and minimum capacities of cut \(\alpha\).
3. Show that the maximum capacity of the cut \(\left\{ S , S _ { 1 } , S _ { 2 } , A , E \right\} , \{ B , C , D , T \}\) is 47 litres per second. A flow is set up in which the arcs \(S _ { 1 } A , S _ { 1 } B , S _ { 2 } C , A E , C E\) and \(D T\) are all at their lower capacities.
4. Show the flow in each arc on the diagram in the answer book, indicating the direction of the flow in \(\operatorname { arc } D E\).
5. What is the maximum amount, in litres per second, by which the flow can be augmented using the routes \(S _ { 1 } A D T\) and \(S _ { 2 } C E T\) ?
6. Find the maximum possible flow through the system, explaining how you know both that this is feasible and that it cannot be exceeded.

1 [Answer this question on the insert provided.]
The network below represents a system of pipelines through which fluid flows from \(S\) to \(T\). The capacities of the pipelines, in litres per second, are shown as weights on the arcs. \includegraphics[max width=\textwidth, alt={}, center]{0403a37e-46dd-4346-afc6-e48a34417c48-2_863_1201_486_477}

1. Write down the arcs from \(\{ S , A , C , E \}\) to \(\{ B , D , F , T \}\). Hence find the capacity of the cut that separates \(\{ S , A , C , E \}\) from \(\{ B , D , F , T \}\).
2. On the diagram in the insert show the excess capacities and potential backflows when 5 litres per second flow along SADT and 6 litres per second flow along SCFT.
3. Give a flow-augmenting path of capacity 2 . On the second diagram in the insert show the new capacities and potential backflows.
4. Use the maximum flow - minimum cut theorem to show that the maximum flow from \(S\) to \(T\) is 13 litres per second.
5. \(E B\) is replaced by a pipeline with capacity 2 litres per second from \(B\) to \(E\). Find the new maximum flow from \(S\) to \(T\). You should show the flow on the third diagram in the insert and explain how you know that this is a maximum.

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.

5 The network represents a simplified map of a town centre. On certain days, large numbers of visitors need to travel through the town centre, from \(S\) to \(T\). The arcs represent roads and the weights show the maximum number of visitors per hour who can use each road. To find the maximum rate at which visitors can travel through the town centre without any of them being delayed, the problem is modelled as a maximum flow problem. \includegraphics[max width=\textwidth, alt={}, center]{76486ad4-c00e-4e0b-9527-6f13f9222dbb-6_837_1317_523_413}

1. Calculate the capacity of the cut that separates \(\{ S , A , C , G \}\) from \(\{ B , D , E , F , T \}\).
2. Explain why neither arc \(S A\) nor arc \(E T\) can be full to capacity. Also explain why the arcs \(A C\) and \(B C\) cannot simultaneously be full to capacity.
3. Show a flow of 3300 people per hour, and find a cut of capacity 3300 . The direction of flow in \(B C\) is reversed.
4. Show the excess capacities and potential backflows when there is no flow.
5. Without obscuring your answer to part (iv), augment the labels to show a flow of 2000 people per hour along \(S B E T\).
6. Write down further flow augmenting routes and augment the labels, without obscuring your previous answers, to find the maximum flow from \(S\) to \(T\).
7. Show the maximum flow and explain how you know that this flow is maximal.

5 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 pipes, in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{661c776a-9c9f-485f-b0fd-f58651e3e065-6_577_1182_351_443}

1. Identify the source and explain how you know that the sink is at \(G\).
2. Calculate the capacity of the cut that separates \(\{ A , B , C , D , E , F \}\) from \(\{ G , H , I , J , K , L \}\).
3. Assuming that a feasible flow exists, explain why arc \(J G\) must be at its lower capacity. Write down the flows in arcs \(H K\) and \(I L\).
4. Assuming that a feasible flow exists, explain why arc HI must be at its upper capacity. Write down the flows in arcs \(E H\) and \(C B\).
5. Show a flow of 10 litres per second through the system.
6. Using your flows from part (v), label the arrows on the diagram to show the excess capacities and the potential backflows.
7. Write down a flow augmenting path from your diagram in part (vi), but do not update the excess capacities and the potential backflows. Hence show a maximum flow through the system, and state how you know that the flow is maximal.

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Amrit (A), Bernard (B), Cameron (C), David (D), Emily (E) and Francis (F), to six tasks, 1, 2, 3, 4, 5 and 6

1. Explain why it is not possible to find a complete matching. Figure 2 shows an initial matching. Starting from this initial matching,
2. find the two alternating paths that start at C .
3. List the two improved matchings generated by using the two alternating paths found in (b). After training, task 5 is added to Bernard's possible allocation.
   Starting from either of the two improved matchings found in (c),
4. use the maximum matching algorithm to obtain a complete matching. You must list the additional alternating path that you use, and state the complete matching.
   (3)

3. \begin{figure}[h] \end{figure} Figure 4 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track. Sally wishes to travel from A to J. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to J. State the path and its length.
2. Find a route of minimal length that goes from D to H via A and state its length.
3. Use Prim's algorithm, starting at E , to find a minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
4. Find the length, in kilometres, of your minimum spanning tree.

7. \begin{figure}[h] \end{figure} [The total weight of the network is \(205 + 3 x\) ] Figure 3 represents a network of roads. The number on each arc represents the time taken, in minutes, to drive along the corresponding road. Malcolm wishes to minimise the time spent driving from his home at A to his office at H . The delays from roadworks on two of the roads leading in to H vary daily, and so the time taken to drive along these roads is expressed in terms of \(x\), where \(x\) is fixed for any given day and \(x > 0\)

1. Use Dijkstra's algorithm to find the possible routes that minimise the driving time from A to H. State the length of each route, leaving your answer in terms of \(x\) where necessary. On Monday, Malcolm needs to check each road. He must travel along each road at least once. He must start and finish at H and minimise the total time taken for his inspection route. Malcolm finds that his minimum duration inspection route requires him to traverse exactly four roads twice and the total time it takes to complete his inspection route is 307 minutes.
2. Calculate the minimum time taken for Malcolm to travel from A to H on Monday. You must make your method and working clear.