7.04b Minimum spanning tree: Prim's and Kruskal's algorithms

5 The matrix shows the distances in miles between towns where direct routes exist.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest route from A to F . Give the route and its length.
3. Use Kruskal's algorithm to find a minimum connector for the network, showing your working. Draw your connector and give its total length.
4. How much shorter would AD have to be if it were to be included in
   (A) a shortest route from A to F ,
   (B) a minimum connector?

4 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest paths from A to each of the other vertices. Give the paths and their lengths.
3. Draw a new network containing all of the edges in your shortest paths, and find the total length of the edges in this network.
4. Find a minimum connector for the original network, draw it, and give the total length of its edges.
5. Explain why the method defined by parts (i), (ii) and (iii) does not always give a minimum connector.

1 The weights on the arcs in the network represent times in minutes to travel between vertices. \includegraphics[max width=\textwidth, alt={}, center]{d1e0f047-6484-435b-a685-2cbbf81a6b02-2_606_782_402_628}

1. Use Dijkstra's algorithm to find the fastest route from A to F . Give the route and the time.
2. Use an algorithm to find the minimum connector for the network, showing your working. Find the minimum time to travel from A to F using only arcs in the minimum connector.

6 The matrix gives the lengths of the arcs of a network.

1. Using the copy of the matrix in your answer book, apply the tabular form of Prim's algorithm to find a minimum connector for the network. Start by choosing vertex A and show the order in which you include vertices.
   List the arcs in your connector and give its total length. Serena takes a different approach to find a minimum connector. She first uses Dijkstra's algorithm to find shortest paths from A to each of the other vertices. She then uses the arcs in those paths to construct a connector.
2. Draw the network using the vertices printed in your answer book.
3. Apply Serena's method to produce a connector. List the arcs in the connector and give its total length. Serena adapts her method by starting from each vertex in turn, producing six connectors, from which she chooses the best.
4. Serena's approach will not find the minimum connector in all networks, but it is an algorithm. What is its algorithmic complexity? Justify your answer.

5 The diagram represents canals connecting five cities. Canal lengths (shown on the arcs) are in km. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_410_990_306_539}

1. Draw a network in your answer book with nodes representing the five cities and arcs representing direct canal connections, i.e. canal connections which do not involve passing through another city. The company operating the canal system wishes to close some canals to save money, whilst preserving the connectivity.
2. Starting at A, use Prim's algorithm on your answer to part (i) to find a minimum connector for the network. Give the order in which you include arcs. Draw your minimum connector and give its total length. Consider the original network together with an extra vertex, X , at the junction of four arcs. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_405_987_1361_539}
3. Draw the minimum connector which results from applying Prim's algorithm, starting at A , to this network. Give the length of that minimum connector. Hence advise the company on which canals to close.
4. Give a reason why the company might face objections to such closures.

6 The table shows the distances in miles, where direct rail connections are possible, between 11 cities in a country. The government is proposing to construct a high-speed rail network to connect the cities.

1. Use the tabular form of Prim's algorithm, starting at vertex P , to find a minimum connector for the network. Draw your minimum connector and give its total length.
2. Give one advantage and two disadvantages of constructing a rail network using only the arcs of a minimum connector.
3. Use Dijkstra's algorithm on the diagram in the Printed Answer Book, to find the shortest route and distance from P to Nr in the original network.
4. Give the shortest distance from P to Nr using only arcs in your minimum connector.

3 Six remote villages are linked by a set of roads. Two villages are connected directly if there is a road between them which does not pass through another village. The table gives the lengths in miles of all direct connections.

1. Why might it be thought surprising that the direct distance between A and D is as long as 12 miles? Give a possible reason why the distance is longer than might have been expected.
2. Use the tabular form of Prim's algorithm, starting at A , to find a minimum connector for these villages. Draw your connector and give its total length.

4 The table defines a network on 6 nodes, the numbers representing distances between those nodes.

1. Use Dijkstra's algorithm to find the shortest routes from A to each of the other vertices. Give those routes and their lengths.
2. Jack wants to find a minimum spanning tree for the network.
   1. Apply Prim's algorithm to the network, draw the minimum spanning tree and give its length. Jill suggests the following algorithm is easier.
      Step 1 Remove an arc of longest length which does not disconnect the network
      Step 2 If there is an arc which can be removed without disconnecting the network then go to Step 1
      Step 3 Stop
   2. Show the order in which arcs are removed when Jill's algorithm is applied to the network.
   3. Explain why Jill's algorithm always produces a minimum spanning tree for a connected network.
   4. In a complete network on \(n\) vertices there are \(\frac { n ( n - 1 ) } { 2 }\) arcs. There are \(n - 1\) arcs to include when using Prim's algorithm. How many arcs are there to remove using Jill's algorithm? For what values of \(n\) does Jill have more arcs to remove than Prim has to include?

6 A mountain ridge separates two populated areas. Networks representing roads connecting the villages in each area are shown below. The numbers on the arcs represent distances in kilometres. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-7_524_1429_340_319} There is also a mountain road of length 15 kilometres connecting C to Z .

1. A national bus company needs a route from A to X .
   1. Use Dijkstra's algorithm on the complete network, including CZ, to find the shortest route from A to X . Give the route and its corresponding distance.
   2. Would it need fewer computations to use Dijkstra's algorithm on the network for villages A to F to find the shortest route from A to C, and then use Dijkstra's algorithm on the network for villages U to Z to find the shortest route from Z to X? Give a brief justification for your answer.
2. The local council needs to discover which roads it should keep clear of snow during the winter to keep all the villages connected, and the corresponding total length of road.
   1. Use Kruskal's algorithm on the network for villages A to F to find a minimum connector for \(\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } \}\). Show your use of the algorithm. Draw your minimum connector.
   2. Use Prim's algorithm on the network for villages U to Z to find a minimum connector for \(\{ \mathrm { U } , \mathrm { V } , \mathrm { W } , \mathrm { X } , \mathrm { Y } , \mathrm { Z } \}\), starting at U . Show your use of the algorithm. Draw your minimum connector.
   3. What is the total length of road that the council must keep clear of snow?

1. This question should be answered on the sheet provided.

A College wants to connect the computerised registration equipment at its six sites, \(A\) to \(F\). The table below shows the cost, in pounds, of connecting any two of the sites. Starting at \(D\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. Hence, state the lowest cost of connecting all the sites.
(5 marks)

1. This question should be answered on the sheet provided.

A cable TV company wishes to link 5 villages in the Scottish Highlands. The table below shows the shortest distances, in kilometres, between these 5 villages.

1. Starting at Thurso, use Prim's algorithm to find a minimum spanning tree. You should make your method clear, indicating the order in which you selected the arcs in your final tree.
2. Calculate the minimum total length of cable required.
   

4. The following matrix gives the capacities of the pipes in a system.

1. Represent this information as a digraph.
2. Find the minimum cut, expressing it in the form \(\{ \} \mid \{ \}\), and state its value.
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.
4. Explain how you know that this flow is maximal.

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.

6 A retail company has warehouses at \(P , Q\) and \(R\), and goods are to be transported to retail outlets at \(Y\) and \(Z\). There are also retaining depots at \(U , V , W\) and \(X\). The possible routes with the capacities along each edge, in van loads per week, are shown in the following diagram. \includegraphics[max width=\textwidth, alt={}, center]{172c5c92-4254-4593-b741-1caa83a1e833-14_673_1193_577_429}

1. On Figure 5 opposite, add a super-source, \(S\), and a super-sink, \(T\), and appropriate edges so as to produce a directed network with a single source and a single sink. Indicate the capacity of each edge that you have added.
2. On Figure 6, write down the maximum flows along the routes SPUYT and SRVWZT.
3. 1. On Figure 7, add the vertices \(S\) and \(T\) and the edges connecting \(S\) and \(T\) to the network. Using the maximum flows along the routes SPUYT and SRVWZT found in part (b) as the initial flow, indicate the potential increases and decreases of the flow on each edge of these routes.
   2. Use flow augmentation to find the maximum flow from \(S\) to \(T\). You should indicate any flow-augmenting routes on Figure 6 and modify the potential increases and decreases of the flow on Figure 7.
4. Find a cut with value equal to the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_629_1100_342_477}
   \end{figure} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 6}

   Route	Flow
   SPUYT
   SRVWZT

   \end{table} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 7} \includegraphics[alt={},max width=\textwidth]{172c5c92-4254-4593-b741-1caa83a1e833-15_634_1109_1838_470}
   \end{figure}

6 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]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-14_807_1472_429_276}

1. Find the value of the cut \(Q\).
2. Figure 2 shows most of the values of a feasible flow of 34 litres per second from \(S\) to \(T\).
   1. Insert the missing values of the flows along \(D E\) and \(F G\) on Figure 2.
   2. Using this feasible flow as the initial flow, indicate potential increases and decreases of the flow along each edge on Figure 3.
   3. Use flow augmentation on Figure 3 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. 1. State the value of the maximum flow.
   2. Illustrate your maximum flow on Figure 4.
4. Find a cut with capacity equal to that of the maximum flow. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_1646_1463_280_381}
   \end{figure} Figure 3 \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{b23828c8-01ee-4b5a-b6d2-41b7e27190d6-15_668_1230_1998_404}
   \end{figure}

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}

6. The table below shows the distances, in km, between six towns \(A , B , C , D , E\) and \(F\).

1. Starting from \(A\), use Prim's algorithm to find a minimum connector and draw the minimum spanning tree. You must make your method clear by stating the order in which the arcs are selected.
   (4)
2. 1. Using your answer to part (a) obtain an initial upper hound for the solution of the travelling salesman problem.
   2. Use a short cut to reduce the upper bound to a value less than 680 .
      (4)
3. Starting by deleting \(F\), find a lower bound for the solution of the travelling salesman problem.
   (4)

2.

1. Explain the difference between the classical and practical travelling salesman problems. \includegraphics[max width=\textwidth, alt={}, center]{eabe577b-80d9-45f8-a8e8-0c3b139b96a8-1_691_1297_1014_383} The network in the diagram above shows the distances, in kilometres, between eight McBurger restaurants. An inspector from head office wishes to visit each restaurant. His route should start and finish at \(A\), visit each restaurant at least once and cover a minimum distance.
2. Obtain a minimum spanning tree for the network using Kruskal's algorithm. You should draw your tree and state the order in which the arcs were added.
3. Use your answer to part (b) to determine an initial upper bound for the length of the route.
4. Starting from your initial upper bound and using an appropriate method, find an upper bound which is less than 135 km . State your tour.
   

7. \includegraphics[max width=\textwidth, alt={}, center]{151644c7-edef-448e-ac2a-b374d79f264c-3_738_1052_466_516} The network in the diagram above shows the distances, in km, between eight weather data collection points. Starting and finishing at A, Alice needs to visit each collection point at least once, in a minimum distance.

1. Obtain a minimum spanning tree for the network using Kruskal's algorithm, stating the order in which you select the arcs.
2. Use your answer to part (a) to determine an initial upper bound for the length of the route.
3. Starting from your initial upper bound use short cuts to find an upper bound, which is below 630 km . State the corresponding route.
4. Use the nearest neighbour algorithm starting at B to find a second upper bound for the length of the route.
5. By deleting C, and all of its arcs, find a lower bound for the length of the route.
6. Use your results to write down the smallest interval which you are confident contains the optimal length of the route.
   (2) (Total 16 marks)

1. The table below shows the least costs, in pounds, of travelling between six cities, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

Vicky must visit each city at least once. She will start and finish at A and wishes to minimise the total cost.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network.
   (2)
2. Use your answer to part (a) to help you calculate an initial upper bound for the length of Vicky's route.
   (1)
3. Show that there are two nearest neighbour routes that start from A . You must make your routes and their lengths clear.
4. State the best upper bound from your answers to (b) and (c).
5. Starting by deleting A , and all of its arcs, find a lower bound for the route length.
   

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

1. State the value of the initial flow.
2. 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.
3. Complete the initialisation of the labelling procedure on Diagram 2 in the answer book by entering values on the arcs to S and T and on \(\operatorname { arcs } \mathrm { CD }\), DE , DG , FG, FI and GI.
4. Find the maximum flow through the network. You must list each flow-augmenting route you use, together with its flow.
5. Show your maximum flow on Diagram 3 in the answer book.
6. Prove that your flow is maximal.