OCR A Level: Decision 1 - Prim's Algorithm [June 2007 Q6]

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. $(\text{i})$ 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.

$(\text{ii})$ 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.

$(\text{iii})$ Apply 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.

---

Input the upper bound, in miles, as your answer.

---

There are 6 marks available for part (i), 3 marks for part (ii) and 4 marks for part (iii).

In total, this question is worth 18.1% of all available marks in the paper.

---

This is part of the set OCR A Level Problems .