D1 June 2014 Q4

EdexcelOld spec9 marksAllocation

	1^st preference	2^nd preference	3^rd preference
Ashley (A)	T	C	V
Fran (F)	V	T
Jas (J)	C	D
Ned (N)	V
Peter (P)	V
Richard (R)	G	C	K

Six pupils, Ashley (A), Fran (F), Jas (J), Ned (N), Peter (P) and Richard (R), each wish to learn a musical instrument. The school they attend has six spare instruments; a clarinet (C), a trumpet (T), a violin (V), a keyboard (K), a set of drums (D) and a guitar (G). The pupils are asked which instruments they would prefer and their preferences are given in the table above. It is decided that each pupil must learn a different instrument and each pupil needs to be allocated to exactly one of their preferred instruments.

(a) Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of pupils to instruments. (1)

Initially Ashley, Fran, Jas and Richard are each allocated to their first preference.

(b) Show this initial matching on Diagram 2 in the answer book. (1)

(c) Starting with the initial matching from (b), apply the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and give your improved matching. (3)

(d) Explain why a complete matching is not possible. (1)

Fran decides that as a third preference she would like to learn to play the guitar. Peter decides that as a second preference he would like to learn to play the drums.

(e) Starting with the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching. (3)

Scheme	Marks
	B1
	(1)

Scheme	Marks
	B1
	(1)

Mark scheme (c)

Scheme	Marks
Alternating path either N – V = F – T = A – C = J – D or P – V = F – T = A – C = J – D	M1
Change status N = V – F = T – A = C – J = D or P = V – F = T – A = C – J = D	A1
Improved matching A = C, F = T, J = D, N = V, (P unmatched), R = G or A = C, F = T, J = D, (N unmatched), P = V, R = G	A1
	(3)

Notes

c1M1 An alternating path (e.g. letter 1st set – letter 2nd set – letter 1st set - …) from either N or P to D – or vice versa.

c1A1 CAO – a correct path including change status either stated (only accept ‘change (of) status’ or ‘c.s.’) or shown (all symbols e.g. (…-…=…-…) interchanged (…=…-…=…). Chosen path clear.

e.g.

N – V = F – T = A – C = J – D
N = V – F = T – A = C – J = D Scores M1A1 (change status shown)
change status N – V = F – T = A – C = J – D Scores M1A1 (change status stated)
c.s. N – V = F – T = A – C = J – D Scores M1A1 (change status stated)
N – V = F – T = A – C = J – D
c.s. N = V – F = T – A = C – J = D Scores M1A1 (change status stated and shown)
N – V = F – T = A – C = J – D
N = V, F = T, A = C, J = D, … Scores M1A0 (no change status stated or shown)

c2A1 CAO must follow from the correct stated path. Accept on a clear diagram (with five arcs only). Condone lack of P or N being stated as unmatched.

Mark scheme (d)

Scheme	Marks
e.g. both K and G can only be allocated to R e.g. N and P can only be allocated to V	B1
	(1)

Notes

d1B1 CAO (completely correct statement) – do not accept a general statement (specific nodes must be referred to). Note that these need to be checked carefully e.g. V can only be allocated to N and P is B0.

Mark scheme (e)

Scheme	Marks
Alternating path P – D = J – C = A – T = F – G = R – K or N – V = P – D = J – C = A – T = F – G = R – K	M1
Change status P = D – J = C – A = T – F = G – R = K or N = V – P = D – J = C – A = T – F = G – R = K	A1
Complete matching A = T, F = G, J = C, N = V, P = D, R = K	A1
	(3)
	(9 marks)

Notes

e1M1 A second alternating path from either N (if P used in (c)) or P (if N used in (c)) to K (or vice-versa)

e1A1 CAO including change status (stated or shown), chosen path clear.

e2A1 CAO must follow from two correct stated paths (so both previous M marks must have been awarded). Accept on a clear diagram (with six arcs only).