D1 June 2013 (R) Q1

EdexcelOld spec7 marksAllocation

Figure 1: possible allocations of A to F to tasks 1 to 6 — Figure 1

Figure 2: initial matching B–4, D–2, E–1, F–5 — Figure 2

Figure 1 shows the possible allocations of six people, A, B, C, D, E and F, to six tasks, 1, 2, 3, 4, 5 and 6.

Figure 2 shows an initial matching.

(a) Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching. (3)

(b) Explain why it is not possible to find a complete matching. (1)

After training, task 4 is added to F’s possible allocation and task 6 is added to E’s possible allocation.

(c) Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you used and your complete matching. (3)

Mark scheme (a)

Scheme	Marks
C – 5 = F – 2 = D – 6 change status to give C = 5 – F = 2 – D = 6	M1 A1
Improved matching is (A unmatched) B = 4, C = 5, D = 6, E = 1, F = 2	A1
	(3)

Notes

a1M1 An alternating path (e.g. letter – number – letter – ...) from C to 6 or vice versa

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

a2A1 CAO must follow from the correct stated path. Accept on a clear diagram (with five arcs only).

Mark scheme (b)

Scheme	Marks
E.g. activities 3 and 4 can only be done by B E.g. both A and E can only do activity 1	B1
	(1)

Notes

b1B1 A good, clear, complete, correct answer (all relevant nodes must be referred to and must be correct)

Mark scheme (c)

Scheme	Marks
A – 1 = E – 6 = D – 2 = F – 4 = B – 3	M1
Change status to give A = 1 – E = 6 – D = 2 – F = 4 – B = 3	A1
Complete matching is A = 1, B = 3, C = 5, D = 2, E = 6, F = 4	A1
	(3)
	(7 marks)

Notes

c1M1 An alternating path from A to 3 or vice versa.

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

c2A1 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).