Apply Prim's algorithm in matrix form

3 A group of eight friends, \(A , B , C , D , E , F , G\) and \(H\), keep in touch by sending text messages. The cost, in pence, of sending a message between each pair of friends is shown in the following table. One of the group wishes to pass on a piece of news to all the other friends, either by a direct text or by the message being passed on from friend to friend, at the minimum total cost.

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 table.
   2. Draw your minimum spanning tree.
   3. Find the minimum total cost.
2. Person \(H\) leaves the group. Find the new minimum total cost.

4 [Answer this question on the insert provided.]
A competition challenges teams to hike across a moor, visiting each of eight peaks, in the quickest possible time. The teams all start at peak \(A\) and finish at peak \(H\), but other than this the peaks may be visited in any order. The estimated journey times, in hours, between peaks are shown in the table. A dash in the table means that there is no direct route between two peaks.

1. Use Prim's algorithm on the table in the insert 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. What can you deduce from this answer about the quickest possible time needed to complete the challenge?
2. On the insert, draw a network to represent the information given in the table above. A team decides to visit each peak exactly once on the hike from peak \(A\) to peak \(H\).
3. Explain why the team cannot use the arc \(A C\).
4. Explain why the team must use the arc \(E F\).
5. There are only two possible routes that the team can use. Find both routes and determine which is the quicker route.

2 Five rooms, \(A , B , C , D , E\), in a building need to be connected to a computer network using expensive cabling. Rob wants to find the cheapest way to connect the rooms by finding a minimum spanning tree for the cable lengths. The length of cable, in metres, needed to connect each pair of rooms is given in the table below.

1. Apply Prim's algorithm in matrix (table) form, starting at vertex \(A\) and showing all your working. Write down the order in which arcs were added to the tree. Draw the resulting tree and state the length of cable needed. A sixth room, \(F\), is added to the computer network. The distances from \(F\) to each of the other rooms are \(A F = 32 , B F = 29 , C F = 31 , D F = 35 , E F = 30\).
2. Use your answer to part (i) to write down a lower bound for the length of the minimum tour that visits every vertex of the extended network, finishing where it starts. Apply the nearest neighbour method, starting from vertex \(A\), to find an upper bound for the length of this tour.

1 The arc weights for a network on a complete graph with six vertices are given in the following table. Apply Prim's algorithm to the table in the Printed Answer Book. Start by crossing out the row for \(A\) and choosing an entry from the column for \(A\). Write down the arcs used in the order that they are chosen. Draw the resulting minimum spanning tree and give its total weight.

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.

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.

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.

7 A complete graph on five vertices is weighted to form a network, as given in the weighted matrix below.

1. Apply Prim's algorithm to the copy of this weighted matrix in the Printed Answer Booklet to construct a minimum spanning tree for the five vertices.
   Draw your minimum spanning tree, stating the order in which you built the tree and giving its total weight.
2. (a) Using only the arcs in the minimum spanning tree, which vertex should be chosen to find the smallest total of the weights of the paths from that vertex to each of the other vertices?
   (b) State the minimum total for this vertex.
3. Show that the total number of comparisons needed to find a minimum spanning tree for a \(5 \times 5\) matrix is 16 .
4. If a computer takes 4 seconds to find a minimum spanning tree for a network with 100 vertices, how long would it take to find a minimum spanning tree for a network with 500 vertices?

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.

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)?

	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)
\(A\)	\(-\)	48	117	92	\(-\)	\(-\)	\(-\)
\(B\)	48	\(-\)	\(-\)	\(-\)	\(-\)	63	55
\(C\)	117	\(-\)	\(-\)	28	\(-\)	\(-\)	85
\(D\)	92	\(-\)	28	\(-\)	58	132	\(-\)
\(E\)	\(-\)	\(-\)	\(-\)	58	\(-\)	124	\(-\)
\(F\)	\(-\)	63	\(-\)	132	124	\(-\)	\(-\)
\(G\)	\(-\)	55	85	\(-\)	\(-\)	\(-\)	\(-\)

The table shows the lengths, in metres, of the paths between seven vertices \(A\), \(B\), \(C\), \(D\), \(E\), \(F\) and \(G\) in a network N.

1. Use Prim's algorithm, starting at \(A\), to solve the minimum connector problem for this table of distances. You must clearly state the order in which you selected the edges of your tree, and the weight of your final tree. Draw your tree using the vertices given in Diagram 1 in the answer book. [5]
2. Draw N using the vertices given in Diagram 2 in the answer book. [3]
3. Solve the Route Inspection problem for N. You must make your method of working clear. State a shortest route and find its length. (The weight of N is 802.) [7]

$$\begin{array}{c|c|c|c|c|c} & M & A & B & C & D & E \\ \hline M & - & 215 & 170 & 290 & 210 & 305 \\ \hline A & 215 & - & 275 & 100 & 217 & 214 \\ \hline B & 170 & 275 & - & 267 & 230 & 200 \\ \hline C & 290 & 100 & 267 & - & 180 & 220 \\ \hline D & 210 & 217 & 230 & 180 & - & 245 \\ \hline E & 305 & 214 & 200 & 220 & 245 & - \end{array}$$ The table shows the cost, in pounds, of linking five automatic alarm sensors, \(A,B,C,D\) and \(E\), and the main reception, \(M\).

1. Use Prim's algorithm, starting from \(M\), to find a minimum spanning tree for this table of costs. You must list the arcs that form your tree in the order that they are selected. [3]
2. Draw your tree using the vertices given in Diagram 1 in the answer book. [1]
3. Find the total weight of your tree. [1]
4. Explain why it is not necessary to check for cycles when using Prim's algorithm. [2]

(Total 7 marks)