7.04f Network problems: choosing appropriate algorithm

4 The network below represents a small village. The arcs represent the streets and the weights on the arcs represent distances in km . \includegraphics[max width=\textwidth, alt={}, center]{7ca6d572-d776-4ad7-a0ed-9ec43c975585-04_503_1179_324_482}

1. Use Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Write down the route of the shortest path from \(A\) to \(G\). Hannah wants to deliver newsletters along every street; she will start and end at \(A\).
2. Which standard network problem does Hannah need to solve to find the shortest route that uses every arc? The total weight of all the arcs is 3.7 km .
3. Hannah knows that she will need to travel \(A B\) and \(E F\) twice, once in each direction. With this information, use an appropriate algorithm to find the length of the shortest route that Hannah can use. Show all your working. (You may find the lengths of shortest paths between vertices by inspection.) There are street name signs at each vertex except for \(A\) and \(E\). Hannah's friend Peter wants to check that the signs have not been vandalised. He will start and end at \(B\). The table below shows the complete set of shortest distances between vertices \(B , C , D , F\) and \(G\).

   	\(B\)	\(C\)	\(D\)	\(F\)	\(G\)
   \(B\)	-	0.2	0.1	0.3	0.75
   \(C\)	0.2	-	0.3	0.5	0.95
   \(D\)	0.1	0.3	-	0.2	0.65
   \(F\)	0.3	0.5	0.2	-	0.45
   \(G\)	0.75	0.95	0.65	0.45	-

4. Apply the nearest neighbour method to this table, starting from \(B\), to find an upper bound for the distance that Peter must travel.
5. Apply Prim's algorithm to the matrix formed by deleting the row and column for vertex \(G\) from the table. Start building your tree at vertex \(B\). Draw your tree. Give the order in which vertices are built into your tree and calculate the total weight of your tree. Hence find a lower bound for the distance that Peter must travel.

5 The arcs in the network below represent the tracks in a forest and the weights on the arcs represent distances in km. \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_543_1269_392_438} Dijkstra's algorithm is to be used to find the shortest path from \(A\) to \(G\).

1. Apply Dijkstra's algorithm to find the shortest path from \(A\) to \(G\). Show your working, including temporary labels, permanent labels and the order in which permanent labels are assigned. Do not cross out your working values. Write down the route of the shortest path from \(A\) to \(G\) and give its length. The track joining \(B\) and \(D\) is washed away in a flood. It is replaced by a new track of unknown length, \(x \mathrm {~km}\). \includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-6_544_1271_1480_438}
2. What is the smallest value that \(x\) can take so that the route found in part (i) is still a shortest path? If the value of \(x\) is smaller than this, what is the weight of the shortest path from \(A\) to \(G\) ?
3. (a) For what values of \(x\) will vertex \(E\) have two temporary labels? Write down the values of these temporary labels.
   (b) For what values of \(x\) will vertex \(C\) have two temporary labels? Write down the values of these temporary labels. Dijkstra's algorithm has quadratic order.
4. If a computer takes 20 seconds to apply Dijkstra's algorithm to a complete network with 50 vertices, approximately how long will it take for a complete network with 100 vertices?

4 The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres. The total length of the paths shown is 4200 metres. \includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-4_681_1157_450_459}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest distance (in metres) from \(A\) to each of the other vertices. Alex wants to hunt for the treasure. His current location is marked on the network as \(A\). The clues to the location of the treasure are located on the paths. Every path has at least one clue and some paths have more than one. This means that Alex will need to search along the full length of every path to find all the clues.
2. Showing your working, find the length of the shortest route that Alex can take, starting and ending at \(A\), to find every clue. The clues tell Alex that the treasure is located at the point marked as \(H\) on the network.
3. Write down the shortest route from \(A\) to \(H\). Zac also starts at \(A\) and searches along every path to find the clues. He also uses a shortest route to do this, but without returning to \(A\). Instead he proceeds directly to the treasure at \(H\).
4. Calculate the length of the shortest route that Zac can take to search for all the clues and reach the treasure.

3. This question should be answered on the sheet provided. \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.
      (2 marks)

3. \begin{figure}[h] \end{figure} Figure 1 shows a graph in which \(y \geq 0\).
Given that the graph is a weighted network,

1. find the range of values for the path of lowest weight from \(S\) to \(T\). Given instead, that the graph is a capacitated network with the numbers representing the capacity along each arc,
2. find the range of values for the maximum flow from \(S\) to \(T\).
3. Give an example of a practical problem which could be solved by using:
   1. the weighted network in part (a),
   2. the capacitated network in part (b).

6. The table below shows the maximum flows possible within a system. For example, the maximum flow from \(B\) to \(A\) is 12 units.

1. Draw a digraph to represent this information.
2. Give the capacity of the cut \(\{ S , A , B , C \} \mid \{ D , T \}\).
3. Find the minimum cut, stating its capacity, and expressing it in the form \(\{ \quad \} \mid \{ \quad \}\).
4. Use the labelling procedure to find the maximum flow from \(S\) to \(T\). You should list each flow-augmenting route you find together with its flow.
5. Explain how you know that you have found the maximum possible flow.
6. Give an example of a practical situation that could be modelled by the original table.

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)

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}

6 The network shows a system of pipes with the lower and upper capacities for each pipe in litres per minute. \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-12_810_1433_429_306}

1. Find the value of the cut \(Q\).
2. Figure 3 opposite shows a partially completed diagram for a feasible flow of 24 litres per minute from \(S\) to \(T\). Indicate, on Figure 3, the flows along the edges \(B T , D E\) and \(E T\).
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 opposite.
   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.
   3. Illustrate the maximum flow on Figure 5 opposite.
4. Find a cut with value equal to that of the maximum flow. You may wish to show the cut on the network above. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_759_1442_276_299}
   \end{figure} Figure 4 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-13_764_1438_1930_296}
   \end{figure} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-15_2349_1691_221_153} \includegraphics[max width=\textwidth, alt={}, center]{c4dc61a7-47ee-4d5c-bf6d-30a5da2ee8dd-16_2489_1719_221_150}

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.

2 The network below represents a system of pipes. The number not circled on each edge represents the capacity of each pipe in litres per second. The number or letter in each circle represents an initial flow in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{5123be51-168e-4487-8cd3-33aee9e3b23f-04_1060_1076_434_466}

1. Write down the capacity of edge \(E F\).
2. State the source vertex.
3. State the sink vertex.
4. Find the values of \(x , y\) and \(z\).
5. Find the value of the initial flow.
6. Find the value of a cut through the edges \(E B , E C , E D , E F\) and \(E G\).

7 Figure 2 shows a network of pipes. Water from two reservoirs, \(R _ { 1 }\) and \(R _ { 2 }\), is used to supply three towns, \(T _ { 1 } , T _ { 2 }\) and \(T _ { 3 }\).
In Figure 2, the capacity of each pipe is given by the number not circled on each edge. The numbers in circles represent an initial flow.

1. Add a supersource, supersink and appropriate weighted edges to Figure 2. (2 marks)
2. 1. Use the initial flow and 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.
3. Confirm that you have a maximum flow by finding a cut of the same value. List the edges of your cut. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-18_1077_1246_1475_395}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_1049_1264_308_386}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_835_1011_1738_171}
   \end{figure}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-19_688_524_1448_1302}
   \includegraphics[max width=\textwidth, alt={}]{5123be51-168e-4487-8cd3-33aee9e3b23f-20_2256_1707_221_153}

4. The following minimising transportation problem is to be solved.

1. Complete the table below.

   	J	K	L	Supply
   A	12	15		9
   B	8	17		13
   C	4	9		12
   Demand	9	11		34

2. Explain why an extra demand column was added to the table above. A possible north-west corner solution is:

   	J	K	L
   A	9	0
   B		11	2
   C			12

3. Explain why it was necessary to place a zero in the first row of the second column. After three iterations of the stepping-stone method the table becomes:

   	J	K	L
   A		8	1
   B			13
   C	9	3

4. Taking the most negative improvement index as the entering square for the stepping stone method, solve the transportation problem. You must make your shadow costs and improvement indices clear and demonstrate that your solution is optimal.

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.

7. A steel manufacturer has 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) which can produce 35,25 and 15 kilotonnes of steel per year, respectively. Three businesses \(B _ { 1 } , B _ { 2 }\) and \(B _ { 3 }\) have annual requirements of 20,25 and 30 kilotonnes respectively. The table below shows the cost \(C _ { i j }\) in appropriate units, of transporting one kilotonne of steel from factory \(F _ { i }\) to business \(B _ { j }\). The manufacturer wishes to transport the steel to the businesses at minimum total cost.

1. Write down the transportation pattern obtained by using the North-West corner rule.
2. Calculate all of the improvement indices \(I _ { i j }\), and hence show that this pattern is not optimal.
3. Use the stepping-stone method to obtain an improved solution.
4. Show that the transportation pattern obtained in part (c) is optimal and find its cost.

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]{c4c64221-0373-4be9-abe3-5ff281922cdb-07_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.

5. The manager of a car hire firm has to arrange to move cars from three garages \(A , B\) and \(C\) to three airports \(D , E\) and \(F\) so that customers can collect them. The table below shows the transportation cost of moving one car from each garage to each airport. It also shows the number of cars available in each garage and the number of cars required at each airport. The total number of cars available is equal to the total number required.

1. Use the North-West corner rule to obtain a possible pattern of distribution and find its cost.
   (3)
2. Calculate shadow costs for this pattern and hence obtain improvement indices for each route.
3. Use the stepping-stone method to obtain an optimal solution and state its cost.

7. \begin{figure}[h] \end{figure} Figure 1 shows a capacitated, directed network. The unbracketed number on each arc indicates the capacity of that arc, and the numbers in brackets show a feasible flow of value 68 through the network.

1. Add a supersource and a supersink, and arcs of appropriate capacity, to Diagram 1 below. \section*{Diagram 1} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-4_684_1531_1816_267}
2. Find the values of \(x\) and \(y\), explaining your method briefly.
3. Find the value of cuts \(C _ { 1 }\) and \(C _ { 2 }\). Starting with the given feasible flow of 68,
4. use the labelling procedure on Diagram 2 to find a maximal flow through this network. List each flow-augmenting route you use, together with its flow. \section*{Diagram 2} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_647_1506_612_283}
5. Show your maximal flow on Diagram 3 and state its value. \section*{Diagram 3} \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-5_654_1511_1567_278}
6. Prove that your flow is maximal.

1. Freezy Co. has three factories \(A , B\) and \(C\). It supplies freezers to three shops \(D , E\) and \(F\). The table shows the transportation cost in pounds of moving one freezer from each factory to each outlet. It also shows the number of freezers available for delivery at each factory and the number of freezers required at each shop. The total number of freezers required is equal to the total number of freezers available.

1. Use the north-west corner rule to find an initial solution.
2. Obtain improvement indices for each unused route.
3. Use the stepping-stone method once to obtain a better solution and state its cost.

5. Four salesperson \(A , B , C\) and \(D\) are to be sent to visit four companies \(1,2,3\) and 4 . Each salesperson will visit exactly one company, and all companies will be visited. Previous sales figures show that each salesperson will make sales of different values, depending on the company that they visit. These values (in \(\pounds 10000\) s) are shown in the table below.

1. Use the Hungarian algorithm to obtain an allocation that maximises the sales. You must make your method clear and show the table after each stage.
2. State the value of the maximum sales.
3. Show that there is a second allocation that maximises the sales.
   (Total 15 marks)

6. \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-3_696_1319_1292_374} This figure shows a capacitated directed network. The number on each arc is its capacity. The numbers in circles show a feasible flow through the network. Take this as the initial flow.

1. On Diagram 1 and Diagram 2 in the answer book, add a supersource \(S\) and a supersink \(T\). On Diagram 1 show the minimum capacities of the arcs you have added. Diagram 2 in the answer book shows the first stage of the labelling procedure for the given initial flow.
2. Complete the initial labelling procedure in Diagram 2.
3. Find the maximum flow through the network. You must list each flow-augmenting route you use together with its flow, and state the maximal flow.
4. Show a maximal flow pattern on Diagram 3.
5. Prove that your flow is maximal.
6. Describe briefly a situation for which this network could be a suitable model.
   (Total 16 marks) \includegraphics[max width=\textwidth, alt={}, center]{be329a47-a709-4719-abe6-41d388a6c631-4_1486_1963_568_50}

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.

3. To raise money for charity it is decided to hold a Teddy Bear making competition. Teams of four compete against each other to make 20 Teddy Bears as quickly as possible. There are four stages: first cutting, then stitching, then filling and finally dressing.
Each team member can only work on one stage during the competition. As soon as a stage is completed on each Teddy Bear the work is passed immediately to the next team member. The table shows the time, in seconds, taken to complete each stage of the work on one Teddy Bear by the members \(A , B , C\) and \(D\) of one of the teams.

1. Use the Hungarian algorithm, reducing rows first, to obtain an allocation that minimises the time taken by this team to produce one Teddy Bear. You must make your method clear and show the table after each iteration.
2. State the minimum time it will take this team to produce one Teddy Bear. Using the allocation found in (a),
3. calculate the minimum total time this team will take to complete 20 Teddy Bears. You should make your reasoning clear and state your answer in minutes and seconds.
   (Total 13 marks)