D1 June 2015 Q5

EdexcelOld spec10 marksMinimum Spanning Trees

Figure 5: weighted network with nine nodes A to J and 17 arcs — Figure 5

The numbers on the 17 arcs in the network shown in Figure 5 represent the distances, in km, between nine nodes, A, B, C, D, E, F, G, H and J.

(a) Use Kruskal’s algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. (3)

(b) Starting at G, use Prim’s algorithm to find a minimum spanning tree. You must clearly state the order in which you select the arcs of your tree. (3)

A connected graph V has \(n\) nodes. The sum of the degrees of all the nodes in V is \(m\). The graph T is a minimum spanning tree of V.

(d)

(i) Write down, in terms of \(m\), the number of arcs in V.

(ii) Write down, in terms of \(n\), the number of arcs in T.

(iii) Hence, write down an inequality, in terms of \(m\) and \(n\), comparing the number of arcs in T and V. (3)

Mark scheme (a)

Scheme	Marks
Kruskal: BC, AB, (not AC), DE, CD, DF, (not \(\begin{smallmatrix}\text{BF}\\ \text{CE}\end{smallmatrix}\)), EJ, FH, (not HJ), (not BD), GH	M1 A1 A1
	(3)

Notes

a1M1: Kruskal’s – first four arcs BC, AB, DE, CD,…(or weights 6, 7, 10, 11, …) chosen correctly in order and at least one rejection seen at some point

a1A1: All eight arcs BC, AB, DE, CD, DF, EJ, FH, GH (or weights 6, 7, 10, 11, 13, 15, 16, 20) chosen correctly in order and no additional arcs

a2A1: CSO All selections and rejections correct (in correct order and at the correct time) – do not accept weights only for this mark

Listing all the arcs in order and then listing those arcs in the tree in the correct order is fine for full marks (this implies that rejections are correct and at the correct time)
Listing all the arcs in order and just drawing the MST is M0

Mark scheme (b)

Scheme	Marks
Prim: GH, FH, DF, DE; CD, BC; AB, EJ	M1; A1; A1
	(3)

Notes

b1M1: First four arcs correctly chosen in order (GH, FH, DF, DE, … or weights 20, 16, 13, 10,…) or first five nodes{G, H, F, D, E,…} correctly chosen in order. If any rejections seen at any point then M1 (max) only. Order of nodes may be seen at the top of a matrix/table {-, -, -, 4, 5, 3, 1, 2, - }

a1A1: Prim’s - first six arcs correctly chosen in order (GH, FH, DF, DE, CD, BC,… or weights 20, 16, 13, 10, 11, 6,…) or all nine nodes{G, H, F, D, E, C, B, A, J} correctly chosen in order.. Order of nodes may be seen at the top of a matrix so for the first two marks accept {8, 7, 6, 4, 5, 3, 1, 2, 9} (no missing numbers)

a2A1: CSO - all arcs correctly stated and chosen in the correct order. They must be considering arcs for this final mark (do not accept a list of the weights of each arc, nodes or numbers across the top of the matrix unless the correct list of arcs (in the correct order) is also seen)

Misread: Starting at a node other than G scores M1 only – must have the first four arcs (or five nodes or numbers) correct (and in the correct order) – condone rejections seen for this mark

Starting at	Minimum arcs required for M1	Nodes	Order
A	AB BC CD DE	ABCDE	12345----
B	BC AB CD DE	BCADE	31245----
C	CB AB CD DE	CBADE	32145----
D	DE CD BC AD	DECBA	54312----
E	ED CD BC AD	EDCBA	54321----
F	FD DE CD BC	FDECB	-54231---
H	HF DF DE CD	HFDEC	--5342-1-
J	JE DE CD BC	JEDCB	-5432---1

Scheme	Marks
98 (km)	B1
	(1)

Mark scheme (d)

Scheme	Marks
(i) \(\dfrac{m}{2}\)	B1
(ii) \(n - 1\)	B1
(iii) \(m \geqslant 2(n - 1)\) (oe)	B1
	(3)
	(10 marks)

Notes

diB1: CAO (oe e.g. \(0.5m\))

diiB1: CAO

diiiB1: CAO (oe, for example, \(n - 1 \leqslant \dfrac{1}{2}m\)) – must include correct bracketing (if required) – do not accept strict inequality