D1 January 2005 Q3

EdexcelOld spec8 marksMinimum Spanning Trees

Figure 2: weighted network on A to J — Figure 2

The network in Figure 2 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.

(a) Find a minimum spanning tree for the network in Figure 2, showing clearly the order in which you selected the arcs for your tree, using

(i) Kruskal’s algorithm, (3)

(ii) Prim’s algorithm, starting from \(A\). (3)

Given that footpaths are already in place along \(AB\) and \(FI\) and so should be included in the spanning tree,

(b) explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.) (2)

Mark scheme (a)

Scheme	Marks
(i) \(FH, AD, DE, CE\), (not \(DC\)), \(\left\{\begin{matrix}BC\\EG\end{matrix}\right.\), (not \(AC\)), \(CF, HI\), (not \(FI\)), \(IJ\) stop	M1 A1 A1
	(3)
(ii) \(AD, DE, EC\), \(\left\{\begin{matrix}BC\\EG\end{matrix}\right.\), \(CF, FH, HI, IJ\) stop.	M1 A1 A1
	(3)

Scheme	Marks
Start off the tree with \(AB\) and \(FI\), then apply Kruskal	B2,1,0
	(2)
	(8 marks)