Sameer is trying to design a road system to connect six towns, A, B, C, D, E and F. The possible roads and the costs of building them are shown in the graph below. Each vertex represents a town, each edge represents a road and the weight of each edge is the cost of building that road. He needs to design the lowest cost road system that will connect the six towns.

(a)     Name an algorithm which will allow Sameer to find the lowest cost road system.

(b)     Find the lowest cost road system and state the cost of building it. Show clearly the steps of the algorithm.

(a)     EITHER

Prim’s algorithm     A1

OR

Kruskal’s algorithm     A1

[1 mark]

(b)     EITHER

using Prim’s algorithm, starting at A

lowest cost road system contains roads AC, CD, CF, FE and AB     A1

cost is 20     A1

OR

using Kruskal’s algorithm

lowest cost road system contains roads CD, CF, FE, AC and AB     A1

cost is 20     A1

Note: Accept alternative correct solutions.

[7 marks]

Total [8 marks]

Most candidates were able to name an algorithm to find the lowest cost road system and then were able apply the algorithm. All but the weakest candidates were able to make a meaningful start to this question. In 1(b) some candidates lost marks by failing to indicate the order in which edges were added.