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

1. The table shows the travelling times, in seconds, to walk between seven departments in a college.

1. Use Prim's algorithm, starting at Art, to find the minimum spanning tree for the network represented by the table. 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.
3. State the weight of the tree.

5. \begin{figure}[h] \end{figure} The numbers on the \(17 \operatorname { arcs }\) in the network shown in Figure 5 represent the distances, in km , between nine nodes, A, B, C, D, E, F, G, H and J.

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. Starting at G , use Prim's algorithm to find a minimum spanning tree. You must clearly state the order in which you select the arcs of your tree.
3. Find the weight of the minimum spanning tree. A connected graph V has \(n\) nodes. The sum of the degrees of all the nodes in V is \(m\). The graph T is a minimum spanning tree of V .
4. 1. Write down, in terms of \(m\), the number of arcs in V .
   2. Write down, in terms of \(n\), the number of \(\operatorname { arcs }\) in T .
   3. Hence, write down an inequality, in terms of \(m\) and \(n\), comparing the number of arcs in T and V.

4. \begin{figure}[h] \end{figure} Figure 3 represents a network of tram tracks. The number on each edge represents the length, in miles, of the corresponding track. One day, Sarah wishes to travel from A to F. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to F . State your path and its length. On another day, Sarah wishes to travel from A to F via J.
2. Find a route of minimal length that goes from A to F via J and state its length.
3. Use Prim's algorithm, starting at G , to find the minimum spanning tree for the network. You must clearly state the order in which you select the edges of your tree.
4. State the length, in miles, of the minimum spanning tree.

2. \begin{figure}[h] \end{figure} Figure 3 represents nine computer terminals, A, B, C, D, E, F, G, H and J, at Pearsonby School. The school wishes to connect them to form a single computer network. The number on each arc represents the cost, in pounds, of connecting the corresponding computer terminals.

1. Use Prim's algorithm, starting at B , to find the minimum spanning tree for the computer network. You must clearly state the order in which you select the arcs of your tree.
   (3)
2. State the minimum cost of connecting the nine computer terminals.
   (1) It is discovered that some computer terminals are already connected. There are already direct connections along BD and FJ, as shown in bold in Diagram 1 in the answer book. It is decided to use these connections.
3. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BD and FJ. You must list the arcs in the order that you consider them. In each case, state whether or not you are adding the arcs to your spanning tree.
   (3)
   (Total 7 marks)

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

1. Define the terms
   1. tree,
   2. minimum spanning tree.
2. Use Prim's algorithm, starting at A , to find a minimum spanning tree for the network shown in Figure 1. You must clearly state the order in which you select the arcs of the tree.
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.

3. The table above shows the lengths, in metres, of the paths between nine vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\), G, H and J.

1. Use Prim's algorithm, starting at A , to find a minimum spanning tree for this table of distances. You must clearly state the order in which you select the edges and state its weight. Draw your minimum spanning tree using the vertices in the answer book.
2. State whether your minimum spanning tree is unique. Justify your answer.
3. Use Dijkstra's algorithm to find the length of the shortest path from A to J.

3. \begin{figure}[h] \end{figure} Figure 1 represents the distance, in metres, between eight data collection points, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\), G and H . The data collection points are to be linked by cables.

1. Listing the arcs in the order that you select them, find a minimum spanning tree for the network using
   1. Kruskal's algorithm, stating in addition any arcs you reject,
   2. Prim's algorithm, starting from A .
2. State the minimum amount of cable needed.
3. Draw your minimum spanning tree using the vertices given in Figure 1 in your answer book.

6. (a) Define the terms

1. tree,
2. spanning tree,
3. minimum spanning tree.
   (3)
   (b) State one difference between Kruskal's algorithm and Prim's algorithm, to find a minimum spanning tree.
   (1) \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-08_894_1529_920_322}
   \end{figure} (c) Use Kruskal's algorithm to find the minimum spanning tree for the network shown in Fig. 4. State the order in which you included the arcs. Draw the minimum spanning tree in Diagram 1 in the answer book and state its length.
   (4) \section*{Figure 5}
   \includegraphics[max width=\textwidth, alt={}]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-09_887_1536_342_258}
   Figure 5 models a car park. Currently there are two pay-stations, one at \(E\) and one at \(N\). These two are linked by a cable as shown. New pay-stations are to be installed at \(B , H , A , F\) and \(C\). The number on each arc represents the distance between the pay-stations in metres. All of the pay-stations need to be connected by cables, either directly or indirectly. The current cable between \(E\) and \(N\) must be included in the final network. The minimum amount of new cable is to be used.
   (d) Using your answer to part (c), or otherwise, determine the minimum amount of new cable needed. Use Diagram 2 to show where these cables should be installed. State the minimum amount of new cable needed.
   (3)

4 Optical fibre broadband cables are being installed between 5 neighbouring villages. The distance between each pair of villages in metres is shown in the table. The company installing the optical fibre broadband cables wishes to create a network connecting each of the 5 villages using the minimum possible length of cable. Find the minimum length of cable required.
[0pt] [3 marks]

4. \begin{figure}[h] \end{figure} Dijkstra's algorithm has been applied to the network in Figure 2.
A working value has only been replaced at a node if the new working value is smaller.

1. State the length of the shortest path from A to G .
2. Complete the table in the answer book giving the weight of each arc listed. (Note that arc CE and arc EF are not in the table.)
3. State the shortest path from A to G. It is now given that

3. \begin{figure}[h] \end{figure} Figure 2 represents a network of train tracks. The number on each edge represents the length, in kilometres, of the corresponding track.
Dyfan wishes to travel from A to J via C. Dyfan wishes to minimise the distance they travel. Given that Dijkstra's algorithm is to be applied only once to find Dyfan's route,

1. explain why the algorithm should begin at C.
2. Use Dijkstra's algorithm to find the shortest route from A to J via C. State this route and its length.
3. Use Prim's algorithm, starting at C , 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. State the total length, in km , of the minimum spanning tree.

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

1. By adding the arcs from vertex D along with their weights, complete the drawing of the network on Diagram 1 in the answer book.
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. State the weight of the minimum spanning tree.
   

3. \begin{table}[h] \end{table} Table 1 shows the shortest distances, in miles, 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 table of distances. 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|}{}	\(\mathbf { A }\)	\(\mathbf { B }\)	\(\mathbf { C }\)	\(\mathbf { D }\)	\(\mathbf { E }\)	\(\mathbf { F }\)	\(\mathbf { G }\)	\(\mathbf { H }\)
   \(\mathbf { J }\)	31	27	50	29	43	25	49	35

   \captionsetup{labelformat=empty} \caption{Table 2}
   \end{table} Table 2 shows the distances, in miles, between town J and towns A , B , \(\mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H .
   Pranav needs to visit all of the towns, starting and finishing at J, and wishes to minimise the total distance he travels.
3. Starting at J, use the nearest neighbour algorithm to obtain an upper bound for the length of Pranav's route. You must state your route and its length.
4. Starting by deleting J, and all of its edges, find a lower bound for the length of Pranav's route.

6. The following algorithm determines the number of comparisons made when Prim's algorithm is applied to \(\mathrm { K } _ { n }\) Step 1 Start
Step 2 Input the value of \(n\) Step 3 Let \(a = 1\) Step 4 Let \(b = n - 2\) Step 5 Let \(c = b\) Step 6 Let \(a = a + 1\) Step \(7 \quad\) Let \(b = b - 1\) Step 8 Let \(c = c + ( a \times b ) + ( a - 1 )\) Step 9 If \(b > 0\) go to Step 6
Step 10 Output \(C\) Step 11 Stop

1. For \(\mathrm { K } _ { 5 }\), complete the table in the answer book to show the results obtained at each step of the algorithm. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{27586973-89f4-45e1-9cc4-04c4044cd3db-11_595_703_175_680} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} The weights of the ten arcs in Figure 4 are $$\begin{array} { l l l l l l l l l l } 17 & 21 & 24 & 14 & 23 & 13 & 15 & 19 & 28 & 20 \end{array}$$
2. 1. Starting at the left-hand end of the above list, sort the list into ascending order using bubble sort. You need only write down the state of the list at the end of each pass.
   2. Find the total number of comparisons performed during the sort.
3. Find the maximum total number of comparisons required to sort the weights of the 10 arcs of \(\mathrm { K } _ { 5 }\) into ascending order using bubble sort. It is given that the maximum total number of comparisons required to sort the weights of the arcs of \(\mathrm { K } _ { n }\) into ascending order using bubble sort is $$\lambda n ( n - 1 ) ( n + 1 ) ( n - 2 )$$ where \(\lambda\) is a constant.
4. Determine the maximum total number of comparisons required to sort the weights of the arcs of \(\mathrm { K } _ { 50 }\) into ascending order using bubble sort. You must make your method and working clear.

2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J.

1. Use Prim's algorithm, starting at D , to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree.
2. State the weight of the minimum spanning tree found in part (a).
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled.
4. Use your answer to part (b) to calculate an initial upper bound for the length of the historian's route.
5. 1. Use the nearest neighbour algorithm, starting at D , to find an upper bound for the length of the historian's route.
   2. Write down the route which gives this upper bound. Using the nearest neighbour algorithm, starting at F , an upper bound of length 352 miles was found.
6. State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer.
7. By deleting A and all of its arcs, find a lower bound for the length of the historian's route.
   (2) By deleting J and all of its arcs, a lower bound of length 274 miles was found.
8. State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer.

1 Answer this question on the insert provided. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.

3 Answer this question on the insert provided. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-3_492_1006_356_568}

1. This diagram shows a network. The insert has a copy of this network together with a list of the arcs, sorted into increasing order of weight. Use Kruskal's algorithm on the insert to find a minimum spanning tree for this network. Draw your tree and give its total weight.
2. Use your answer to part (i) to find the weight of a minimum spanning tree for the network with vertex \(E\), and all the arcs joined to \(E\), removed. Hence find a lower bound for the travelling salesperson problem on the original network.
3. Show that the nearest neighbour method, starting from vertex \(A\), fails on the original network.
4. Apply the nearest neighbour method, starting from vertex \(B\), to find an upper bound for the travelling salesperson problem on the original network.
5. Apply Dijkstra's algorithm to the copy of the network in the insert to find the least weight path from \(A\) to \(G\). State the weight of the path and give its route.
6. The sum of the weights of all the arcs is 300 . Apply the route inspection algorithm, showing all your working, to find the weight of the least weight closed route that uses every arc at least once. The weights of least weight paths from vertex \(A\) should be found using your answer to part (v); the weights of other such paths should be determined by inspection.

6 Answer this question on the insert provided. The table shows the distances, in miles, along the direct roads between six villages, \(A\) to \(F\). A dash ( - ) indicates that there is no direct road linking the villages.

1. On the table in the insert, use Prim's algorithm to find a minimum spanning tree. Start by crossing out row A. Show which entries in the table are chosen and indicate the order in which the rows are deleted. Draw your minimum spanning tree and state its total weight.
2. By deleting vertex B and the arcs joined to vertex B, calculate a lower bound for the length of the shortest cycle through all the vertices.
3. A pply the nearest neighbour method to the table above, starting from \(F\), to find a cycle that passes through every vertex and use this to write down an upper bound for the length of the shortest cycle through all the vertices.
   {}

2 Answer this question on the insert provided.

1. Use Dijkstra's algorithm to find the least weight route from A to G in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_458_586_525_758} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
   \end{figure}
2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_417_524_1309_786} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

2 Answer this question on the insert provided.

1. Use Dijkstra's algorithm to find the least weight route from \(A\) to \(G\) in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_458_584_525_760} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
   \end{figure}
2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_421_533_1307_779} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

1 Answer this question on the insert provided. The nodes in the unfinished graph in Fig. 1 represent six components, A, B, C, D, E, F and the mains. The components are to be joined by electrical cables to the mains. Each component can be joined directly to the mains, or can be joined via other components. \begin{figure}[h] \end{figure} The total number of connections that the electrician has to make is the sum of the orders of the nodes in the finished graph.

1. Draw arcs representing suitable cables so that the electrician has to make as few connections as possible. Give this number. The electrician has a junction box. This can be represented by an eighth node on the graph.
2. What is the minimum number of connections which the electrician will have to make if he uses the junction box?
3. The electrician has to make more connections if he uses his junction box. Why might he choose to use it anyway? The electrician decides not to use the junction box. He measures each of the distances between pairs of nodes, and records them in a complete graph. He then constructs a minimum connector for his graph to find which nodes to connect.
4. Will this result in the minimum number of connections? Justify your answer.

4 Answer parts (i) and (ii) on the insert provided. Fig. 4 shows a network of roads giving direct connections between a city, C , and 7 towns labelled P to V. The weights on the arcs are distances in kilometres. The local coastline is also shown. \begin{figure}[h] \end{figure}

1. Use Dijkstra's algorithm on the insert to find the shortest distances from each of the towns to the city, C. List those distances and give the shortest route from P to C and from V to C. [8]
2. Use Kruskal's algorithm to find a minimum connector for the network. List the order in which you include arcs and give the length of your connector. A bridge is built giving a direct road between P and Q of length 12 km .
3. What effect does the bridge have on the shortest distances from the towns to the city? (You do not need to use an algorithm to answer this part of the question.)
4. What effect does the bridge have on the minimum connector for the network? (You do not need to use an algorithm to answer this part of the question.)
5. Before the bridge was built it was possible to travel from P to C using every road once and only once. With the bridge in place, it is possible to travel from a different town to C using every road once and only once. Give this town and justify your answer.

5 Answer this question on the insert provided. Table 5 specifies a road network connecting 7 towns, A, B, \(\ldots\), G. The entries in Table 5 give the distances in miles between towns which are connected directly by roads. \begin{table}[h] \end{table}

1. Using the copy of Table 5 in the insert, apply the tabular form of Prim's algorithm to the network, starting at vertex A. Show the order in which you connect the vertices. Draw the resulting tree, give its total length and describe a practical application.
2. The network in the insert shows the information in Table 5. Apply Dijkstra's algorithm to find the shortest route from A to E. Give your route and its length.
3. A tunnel is built through a hill between A and B , shortening the distance between A and B to 6 miles. How does this affect your answers to parts (i) and (ii)?

2. \begin{figure}[h] \end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.

1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
2. State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
3. 1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
   2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
4. State the new minimum cost of connecting the nine buildings.

4
15
7

1. Use the bubble sort algorithm to perform ONE complete pass towards sorting these numbers into ascending order. The original list is now to be sorted into descending order.
2. Use a quick sort to obtain the sorted list, giving the state of the list after each complete pass. You must make your pivots clear. The numbers are to be packed into bins of size 26
3. Calculate a lower bound for the minimum number of bins required. You must show your working.
   2. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-3_549_1175_260_443} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} Figure 1 represents nine buildings, A, B, C, D, E, F, G, H and I, recently bought by Newberry Enterprises. The company wishes to connect the alarm systems between the buildings to form a single network. The number on each arc represents the cost, in pounds, of connecting the alarm systems between the buildings.
   1. Use Prim's algorithm, starting at A , to find the minimum spanning tree for this network. You must list the arcs that form your tree in the order that you select them.
   2. State the minimum cost of connecting the alarm systems in the nine buildings. It is discovered that some alarm systems are already connected. There are connections along BC and EF, as shown in bold in Diagram 1 in the answer book. Since these already exist, it is decided to use these arcs as part of the spanning tree.
   3. 1. Use Kruskal's algorithm to find the minimum spanning tree that includes arcs BC and EF . You must list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your spanning tree.
      2. Explain why Kruskal's algorithm is a better choice than Prim's algorithm in this case. Since arcs BC and EF already exist, there is no cost for these connections.
      3. State the new minimum cost of connecting the nine buildings.
         3. \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_547_413_260_504} \captionsetup{labelformat=empty} \caption{Figure 2}
         \end{figure} \begin{figure}[h]
         \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-4_549_412_258_1146} \captionsetup{labelformat=empty} \caption{Figure 3}
         \end{figure} Figure 2 shows the possible allocations of six people, Beth (B), Charlie (C), Harry (H), Karam (K), Sam (S) and Theresa (T), to six tasks 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.
   4. Define the term 'matching'.
      (2)
   5. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path that you use, and state the improved matching.
      (3) After training, a possible allocation for Harry is task 6, and an additional possible allocation for Karam is task 1.
   6. Starting from the matching found in (b), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.
      (3)
      4. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{e3ac0632-9560-4cb8-99dd-8f4bf28315f4-5_814_1303_251_390} \captionsetup{labelformat=empty} \caption{Figure 4
      [0pt] [The total weight of the network is 367 metres]}
      \end{figure} Figure 4 represents a network of water pipes. The number on each arc represents the length, in metres, of that water pipe. A robot will travel along each pipe to check that the pipe is in good repair.
      The robot will travel along each pipe at least once. It will start and finish at A and the total distance travelled must be minimised.
   7. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You must make your method and working clear.
   8. Write down the length of a shortest inspection route. A new pipe, IJ, of length 35 m is added to the network. This pipe must now be included in a new minimum inspection route starting and finishing at A .
   9. Determine if the addition of this pipe will increase or decrease the distance the robot must travel. You must give a reason for your answer.