Apply Prim's algorithm from vertex

5 The network shows the lengths, in miles, of roads connecting eleven villages. \includegraphics[max width=\textwidth, alt={}, center]{76bccb26-f2ec-4798-bb6b-89c922f9651a-04_1100_1575_406_251}

1. Use Prim's algorithm, starting from \(A\), to find the minimum spanning tree for the network.
2. State the length of your minimum spanning tree.
3. Draw your minimum spanning tree.
4. A student used Kruskal's algorithm to find the same minimum spanning tree. Find the seventh and eighth edges that the student added to his spanning tree.

4 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A programme of resurfacing some roads is undertaken to ensure that each village can access all other villages along a resurfaced road, while keeping the amount of road to be resurfaced to a minimum. \includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-08_1008_1043_589_497}

1. 1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. Given that Prim's algorithm is used with different start vertices, state the final edge to be added to the minimum spanning tree if:
   1. the start vertex is \(E\);
   2. the start vertex is \(G\).
3. Given that Kruskal's algorithm is used to find the minimum spanning tree, state which edge would be:
   1. the first to be included in the tree;
   2. the last to be included in the tree.

3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_810_501_445_388} \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_812_499_443_1135}

1. 1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. Prim's algorithm from different starting points produces the same minimum spanning tree for this network. State the final edge that would complete the minimum spanning tree using Prim's algorithm:
   1. starting from \(D\);
   2. starting from \(H\).

6 The diagram shows routes between points in a town. The distances are in kilometres. \includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-6_817_1219_319_422}

1. Use an appropriate algorithm to find a set of connecting arcs of minimum total length. Indicate your connecting arcs on the copy of the diagram in your answer book, and give their total length.
2. Give the name of the algorithm you have used, and describe it briefly.
3. Using the second diagram in your answer book, apply Dijkstra's algorithm to find the shortest distances from A to each of the other points. List the connections that are used, and give their total length.

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.

1. The table represents a network that shows the time taken, in minutes, to travel by car between eight villages, \(\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 a minimum spanning tree for this network. You must list the arcs that form your tree in the order in which you select them.
2. Draw your minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.
3. State whether your minimum spanning tree is unique. Justify your answer.

3.
6.4
7.9
8.1
12.19 .3
14.0
15.7
17.4
20.1

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 The list is to be sorted into descending order.
2. 1. Starting at the left-hand end of the list, perform two passes through the list using a bubble sort. Write down the state of the list that results at the end of each pass.
   2. Write down the total number of comparisons and the total number of swaps performed during your two passes.
3. Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear.
4. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33
5. Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer.

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.

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.

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\).

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)

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.

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.

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.

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.

1. The table shows the lengths, in km, of potential rail routes between six towns, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F .

1. Use Prim's algorithm, starting from A , to find a minimum spanning tree for this table. You must list the arcs that form your tree in the order that they are selected.
2. Draw your tree using the vertices given in Diagram 1 in the answer book.
3. State the total weight of your tree.

1 The following network shows the lengths, in miles, of roads connecting 11 villages, \(A , B , \ldots , K\). \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-2_915_1303_591_365}

1. Starting from \(G\) and showing your working at each stage, use Prim's algorithm to find a minimum spanning tree for the network.
2. State the length of your minimum spanning tree.
3. Draw your minimum spanning tree.

7 A company operates a steam railway between six stations. The minimum cost (in euros) of travelling between pairs of stations is shown in the table below.

1. On Figure 1 below, use Prim's algorithm, starting from \(P\), to find a minimum spanning tree for the graph connecting \(P , Q , R , S , T\) and \(U\). State clearly the order in which you select the vertices and draw your minimum spanning tree. \section*{Question 7 continues on page 20} \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1}

   	\(\boldsymbol { P }\)	\(\boldsymbol { Q }\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(\boldsymbol { T }\)	\(\boldsymbol { U }\)
   \(\boldsymbol { P }\)	-	14	7	11	6	12
   \(\boldsymbol { Q }\)	14	-	8	10	9	10
   \(\boldsymbol { R }\)	7	8	-	12	13	15
   \(\boldsymbol { S }\)	11	10	12	-	5	11
   \(\boldsymbol { T }\)	6	9	13	5	-	10
   \(\boldsymbol { U }\)	12	10	15	11	10	-

   \end{table}
2. Another station, \(V\), is opened. The minimum costs (in euros) of travelling to and from \(V\) to each of the other stations are added to the table in part (a), as shown in Figure 2(i) below. Further copies of this table are shown in Figure 2(ii). Arjen is on holiday and he plans to visit each station. He intends to board a train at \(V\) and visit all the other stations, once only, before returning to \(V\).
   1. By first removing \(V\), obtain a lower bound for the minimum travelling cost of Arjen's tour. (You may use Figure 2(i) for your working.)
   2. Use the nearest neighbour algorithm twice, starting each time from \(V\), to find two different upper bounds for the minimum cost of Arjen's tour. State, with a reason, which of your two answers gives the better upper bound. (You may use Figure 2(ii) for your working.)
   3. Hence find an optimal tour of the seven stations. Explain how you know that it is optimal. Answer space for question 7(b) \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2(ii)}

      	\(\boldsymbol { P }\)	\(Q\)	\(\boldsymbol { R }\)	\(\boldsymbol { S }\)	\(T\)	\(\boldsymbol { U }\)	\(V\)
      \(\boldsymbol { P }\)	-	14	7	11	6	12	15
      \(Q\)	14	-	8	10	9	10	18
      \(\boldsymbol { R }\)	7	8	-	12	13	15	14
      \(\boldsymbol { S }\)	11	10	12	-	5	11	14
      \(T\)	6	9	13	5	-	10	17
      \(\boldsymbol { U }\)	12	10	15	11	10	-	12
      \(V\)	15	18	14	14	17	12	-

      \end{table}

This question should be answered on the sheet provided in the answer booklet. A school wishes to link 6 computers. One is in the school office and one in each of rooms \(A\), \(B\), \(C\), \(D\) and \(E\). Cables need to be laid to connect the computers. The school wishes to use a minimum total length of cable. The table shows the shortest distances, in metres, between the various sites.

1. Starting at the school office, use Prim's algorithm to find a minimum spanning tree. Indicate the order in which you select the edges and draw your final tree. [5 marks]
2. Using your answer to part (a), calculate the minimum total length of cable required. [1 mark]

The owners of a sports stadium want to install electric car charging points in each of the stadium's nine car parks. An engineer creates a plan which requires installing electrical connections so that each car park is connected, directly or indirectly, to the stadium's main electricity power supply. The engineer produces the network shown below, where the nodes represent the stadium's main electricity power supply \(X\) and the nine car parks \(A\), \(B\), \(\ldots\), \(I\) \includegraphics{figure_5} Each arc represents a possible electrical connection which could be installed. The weight on each arc represents the time, in hours, it would take to install the electrical connection. The electrical connections can only be installed one at a time. To reduce disruption, the owners of the sports stadium want the required electrical connections to be installed in the minimum possible total time.

1. 1. Determine the electrical connections that should be installed. [2 marks]
   2. Find the minimum possible total time needed to install the required electrical connections. [1 mark]
2. Following the installation of the electrical connections, some of the car parks have an indirect connection to the stadium's main electricity power supply. Give one limitation of this installation. [1 mark]