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

2. The table represents a network that shows the average journey time, in minutes, between eight towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H .

1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
2. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
3. State the weight of the minimum spanning tree.

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.

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

1. Define the terms
   1. tree,
   2. minimum spanning tree.
2. Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Figure 1. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in the minimum spanning tree.
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the minimum spanning tree.

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \section*{Question 2 continued} \section*{D} \begin{verbatim} B $$\mathrm { A }$$ \end{verbatim} \begin{verbatim} \(\stackrel { \bullet } { \text { E } }\) \end{verbatim} \section*{Diagram 1} Weight of the minimum spanning tree: \(\_\_\_\_\)

5. \section*{Question 5 continued} \section*{D} A

• \({ } ^ { \text {B } }\)
• F \(\stackrel { \bullet } { \mathrm { H } }\)

Diagram 1

2. \begin{table}[h] \end{table} Table 1 represents a network that shows the travel times, in minutes, between eight towns, A, B, C, D, E, F, G and H.

1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must clearly state the order in which you select the edges of your tree.
2. State the weight of the minimum spanning tree. \begin{table}[h]

   \cline { 2 - 9 } \multicolumn{1}{c|}{}	A	B	C	D	E	F	G	H
   J	33	37	41	35	\(x\)	40	28	42

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table} Table 2 shows the travel times, in minutes, between town J and towns A, B, C, D, E, F, G and H .
   The journey time between towns E and J is \(x\) minutes where \(x > 28\) A salesperson needs to visit all of the nine towns, starting and finishing at J. The salesperson wishes to minimise the total time spent travelling.
3. Starting at J, use the nearest neighbour algorithm to find an upper bound for the duration of the salesperson's route. Write down the route that gives this upper bound. Using the nearest neighbour algorithm, starting at E, an upper bound of 291 minutes for the salesperson's route was found.
4. State the best upper bound that can be obtained by using this information and your answer to (c). Give the reason for your answer. Starting by deleting J and all of its arcs, a lower bound of 264 minutes for the duration of the salesperson's route was found.
5. Determine the value of \(x\). You must make your method and working clear.

4.

1. State three differences between Prim's algorithm and Kruskal's algorithm for finding a minimum spanning tree.
   (3) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-5_864_1073_386_497} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} [The total weight of the network is 341]
2. Use Prim's algorithm, starting at D , to find a minimum spanning tree for the network shown in Figure 4. You must list the arcs in the order in which you select them.
   (3) Figure 4 models a network of school corridors. The number on each arc represents the length, in metres, of that corridor. The school caretaker needs to inspect each corridor in the school to check that the fire alarms are working correctly. He wants to find a route of minimum length that traverses each corridor at least once and starts and finishes at his office, D.
3. Use the route inspection algorithm to find the corridors that will need to be traversed twice. You must make your method and working clear. The caretaker now decides to start his inspection at G. His route must still traverse each corridor at least once but he does not need to finish at G.
4. Determine the finishing point so that the length of his route is minimised. You must give reasons for your answer and state the length of his route.
   (3)
   

3. \begin{figure}[h] \end{figure} Figure 2 shows a graph G.

1. Write down an example of a cycle on G.
   (1)
2. State, with a reason, whether or not \(\mathrm { P } - \mathrm { Q } - \mathrm { R } - \mathrm { T } - \mathrm { Q } - \mathrm { S }\) is an example of a path on G .
   (2) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6417303d-c42a-4da4-b0fa-fb7718959417-4_618_1406_1336_340} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} The numbers on the \(14 \operatorname { arcs }\) in Figure 3 represent the distances, in km , between eight vertices, \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T } , \mathrm { U } , \mathrm { V }\) and W , in a network.
3. Use Prim's algorithm, starting at P , to find the minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
4. Use Kruskal's algorithm to find the minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to the minimum spanning tree.
5. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. The weight on arc RU is now increased to a value of \(x\). The minimum spanning tree for the network is still unique and includes the same arcs as those found in (e).
6. Write down the smallest interval that must contain \(x\).

2. The table shows the costs, in pounds, of connecting seven computer terminals, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G, to a server, S.

1. Use Prim's algorithm, starting at S , to find the minimum spanning tree for this table of costs. You must clearly state the order in which you select the edges of your tree.
   (3)
2. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. State the minimum cost, in pounds, of connecting the seven computer terminals to the server.
3. Explain why it is not necessary to check for cycles when using Prim's algorithm.

3. \begin{figure}[h] \end{figure} Figure 3 shows a graph G that contains \(17 \operatorname { arcs }\) and 8 vertices.

1. State how many arcs there are in a spanning tree for G .
   (1)
2. Explain why a path on G cannot contain 10 vertices.
   (2)
3. Determine the number of arcs that would need to be added to G to make G a complete graph with 8 vertices.
   (1) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_684_1326_1420_370} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} Figure 4 shows a weighted graph.
4. Use Prim's algorithm, starting at C , to find the minimum spanning tree for the weighted graph. You must clearly state the order in which you select the arcs of the tree.
   (3)
5. State the weight of the minimum spanning tree.
   (1)

2. \begin{figure}[h] \end{figure} Figure 1 represents a network of roads between ten villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }\) and K . The number on each edge represents the length, in kilometres, of the corresponding road. The local council needs to find the shortest route from A to J.

1. Use Dijkstra's algorithm to find the shortest route from A to J. State the route and its length. During the winter, the council needs to ensure that all ten villages are accessible by road even if there is heavy snow. The council wishes to minimise the total length of road it needs to keep clear.
2. Use Prim's algorithm, starting at A , to find a minimum connector for the five villages \(\mathrm { A } , \mathrm { B }\), C, D and E. You must clearly state the order in which you select the edges of your minimum connector.
3. Use Kruskal's algorithm to find a minimum connector for the five villages \(\mathrm { F } , \mathrm { G } , \mathrm { H } , \mathrm { J }\) and K . You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in your minimum connector.
4. Calculate the total length of road that the council must keep clear of snow to ensure that all ten villages are accessible.

1. The table below shows the distances, in metres, between six vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , in a network.

1. Draw the weighted network using the vertices given in Diagram 1 in the answer book.
2. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the edges in the order that you consider them and state whether you are adding them to your minimum spanning tree.
3. Draw the minimum spanning tree on Diagram 2 in the answer book and state its total weight.
   

7. The network represented by the table shows the least distances, in km, between eight museums, A, B, C, D, E, F, G and H. A tourist wants to visit each museum at least once, starting and finishing at A. The tourist wishes to minimise the total distance travelled. The shortest distance between A and D is \(x \mathrm {~km}\) where \(32 \leqslant x \leqslant 35\)

1. Using Prim's algorithm, starting at A , obtain a minimum spanning tree for the network. You must clearly state the order in which you select the arcs of your tree.
2. Use your answer to (a) to determine an initial upper bound for the length of the tourist's route.
3. Starting at A, use the nearest neighbour algorithm to find another upper bound for the length of the tourist's route. Write down the route that gives this upper bound. The nearest neighbour algorithm starting at E gives a route of $$\mathrm { E } - \mathrm { H } - \mathrm { A } - \mathrm { D } - \mathrm { G } - \mathrm { C } - \mathrm { B } - \mathrm { F } - \mathrm { E }$$
4. State which of these two nearest neighbour routes gives the better upper bound. Give reasons for your answer. Starting by deleting A, and all of its arcs, a lower bound of 235 km for the length of the route is found.
5. Determine the smallest interval that must contain the optimal length of the tourist's route. You must make your method and working clear.

4. \begin{figure}[h] \end{figure} [The total weight of the network is 494]
Direct roads between nine factories, A, B, C, D, E, F, G, H and J, are represented in Figure 3. The number on each arc represents the lengths, in kilometres, of the corresponding road.
The table below shows the shortest distances, in kilometres, between the nine factories. \section*{Table of shortest distances}

1. Starting at A, use Prim's algorithm to find a minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree.
   (3)
2. State the weight of the minimum spanning tree.
   (1) A route is needed that minimises the total distance to traverse each road at least once. The route must start at E and finish at F .
3. Determine the length of this route. You must give a reason for your answer. It is now decided to start the route at C and finish the route at A . The route must include every road at least once and must still minimise the total distance travelled.
4. By considering the pairings of all relevant nodes, find the roads that need to be traversed twice. Naoko needs to visit all nine factories, starting and finishing at the same factory, and wishes to minimise the total distance travelled.
5. Starting at B, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Naoko's route. Write down the cycle, obtained from the table of shortest distances, which gives this upper bound.
6. By deleting C and all of its arcs, use the values in the table of shortest distances to find a lower bound for the length of Naoko's route.

3. The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H. Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form the tree in the order in which you select them.
2. State the weight of the minimum spanning tree.
3. Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy's route.
4. Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.
5. State the best upper bound that can be obtained by using your answers to (c) and (d).
6. Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy's route. You must make your method and working clear.
7. Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy's route.

2. \begin{figure}[h] \end{figure} Figure 1 represents the distances, in metres, between eight vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H , in a network.

1. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
2. Complete Matrix 1 in your answer book, to represent the network.
3. Starting at A, use Prim's algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs.
4. State the weight of the minimum spanning tree.

2. Prim's algorithm finds a minimum spanning tree for a connected graph.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
2. Name an alternative algorithm for finding a minimum spanning tree. \begin{table}[h]

   	Cambridge	London	Norwich	Oxford	Portsmouth	Salisbury	York
   Cambridge (C)	-	60	62	81	132	139	156
   London (L)	60	-	116	56	74	88	211
   Norwich (N)	62	116	-	144	204	201	181
   Oxford (O)	81	56	144	-	84	63	184
   Portsmouth (P)	132	74	204	84	-	43	269
   Salisbury (S)	139	88	201	63	43	-	248
   York (Y)	156	211	181	184	269	248	-

   \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{table} Figure 2 shows the distances by road, in miles, between seven cities.
3. 1. Use Prim's algorithm, starting at London, to find the minimum spanning tree for these cities. You must clearly state the order in which you selected the edges of your tree, and the weight of the final tree.
   2. Draw your tree using the vertices given in Diagram 2 in the answer book.
      (5)

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

1. Use Kruskal's algorithm to find a minimum spanning tree for the network shown in Figure 2. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
   (3)
2. Starting at A, use Prim's algorithm to find a minimum spanning tree for the network in Figure 2. You must clearly state the order in which you include the arcs in your tree.
   (3)
3. Draw a minimum spanning tree for the network in Figure 2 using the vertices given in Diagram 1 of the answer book. State the weight of the minimum spanning tree.
   (2) A new spanning tree is required which includes the arcs DI and HG, and which has the lowest possible total weight.
4. Explain which algorithm you would choose to complete the tree, and how the algorithm should be adapted. (You do not need to find the tree.)

1. \begin{figure}[h] \end{figure} Figure 1 represents the distances, in km, between eight vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H in a network.

1. Use Kruskal's algorithm to find the minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
   (3)
2. Starting at A, use Prim's algorithm to find the minimum spanning tree. You must clearly state the order in which you selected the arcs of your tree.
   (3)
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.
4. State the weight of the tree.
   (1)

5. \begin{figure}[h] \end{figure} [The weight of the network is 379]
Figure 5 represents the roads in a highland wildlife conservation park. The vertices represent warden stations. The number on each arc gives the length, in km , of the corresponding road. During the winter months the park is closed. It is only necessary to ensure road access to the warden stations.

1. Use Prim's algorithm, starting at A , to find a minimum connector for the network in Figure 5. You must state the order in which you include the arcs.
2. Given that it costs \(\pounds 80\) per km to keep the selected roads open in winter, calculate the minimum cost of ensuring road access to all the warden stations. At the end of winter, Ben inspects all the roads before the park re-opens. He needs to travel along each road at least once. He will start and finish at A, and wishes to minimise the length of his route.
3. Use the route inspection algorithm to find the roads that will be traversed twice. You must make your method and working clear.
4. Find the length of the shortest inspection route. If Ben starts and finishes his inspection route at different warden stations, a shorter inspection route is possible.
5. Determine the two warden stations Ben should choose as his starting and finishing points in order that his route has minimum length. Give a reason for your answer and state the length of the route.

2. \begin{figure}[h] \end{figure} Figure 1 shows 7 locations \(A , B , C , D , E , F\) and \(G\) which are to be connected by pipelines. The arcs show the possible routes. The number on each arc gives the cost, in thousands of pounds, of laying that particular section.

1. Use Kruskal's algorithm to obtain a minimum spanning tree for the network, giving the order in which you selected the arcs.
   (4)
2. Draw your minimum spanning tree and find the least cost of the pipelines.
   (3)

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

1. State two differences between Kruskal's algorithm and Prim's algorithm for finding a minimum spanning tree.
   (2)
2. Listing the arcs in the order that you consider them, find a minimum spanning tree for the network in Figure 4, using
   1. Prim's algorithm,
   2. Kruskal's algorithm.
      (6)

3. The table shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G.

1. Complete the drawing of the network in Diagram 1 of the answer book by adding the necessary arcs from vertex D together with their weights.
2. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
3. Draw the minimum spanning tree using the vertices provided in Diagram 2 in the answer book.
4. State the weight of the minimum spanning tree.

2. The table shows the average journey time, in minutes, between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you selected them.
2. Draw your tree using the vertices given in Diagram 1 in the answer book.
3. Find the weight of your minimum spanning tree. Kruskal's algorithm may also be used to find a minimum spanning tree.
4. State three differences between Prim's algorithm and Kruskal's algorithm.

3. The table shows the times, in days, needed to repair the network of roads between six towns, A, B, C, D, E and F, following a flood.

1. Use Prim's algorithm, starting at A , to find the minimum connector for this network. You must list the arcs that form your tree in the order that you selected them.
2. Draw your minimum connector using the vertices given in Diagram 1 in the answer book.
3. Add arcs from D, E and F to Diagram 2 in the answer book, so that it shows the network of roads shown by the table.
4. Use Kruskal's algorithm to find the minimum connector. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum connector.
5. State the minimum time needed, in days, to reconnect the six towns.