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

Computer Science Level pending

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.
×

Problem Loading...

Note Loading...

Set Loading...