D1 June 2012 Q2

EdexcelOld spec7 marksAllocation

Figure 1: bipartite graph of possible allocations of C, D, E, F, G to tasks 1 to 5 — Figure 1

Figure 2: initial matching C–3, D–1, E–5, F–2 — Figure 2

Figure 1 shows the possible allocations of five workers, Charles (C), David (D), Ellie (E), Freya (F) and Georgi (G), to five tasks, 1, 2, 3, 4 and 5.

Figure 2 shows an initial matching.

(a) Starting from this initial matching, use the maximum matching algorithm to find a complete matching. State clearly the alternating path that you use and list your final matching. (4)

(b) Find another solution starting from the given initial matching. You should state the alternating path and list the complete matching it gives. (3)

Mark scheme (a)

Scheme

Marks

Either (i) G – 3 = C – 2 = F – 1 = D – 4
or (ii) G – 5 = E – 4
or (iii) G – 5 = E – 1 = D – 4

M1 1A1

Change status
Either (i) G = 3 – C = 2 – F = 1 – D = 4
or (ii) G = 5 – E = 4
or (iii) G = 5 – E = 1 – D = 4

2A1

Giving matchings:

	C	D	E	F	G
(i)	2	4	5	1	3
(ii)	3	1	4	2	5
(iii)	3	4	1	2	5

3A1

(4)

Notes

Mark the candidates best attempt as part (a)

a1M1 Path from G to 4 - or vice versa

a1A1 CAO chosen path clear.

a2A1 Change status step clear stated or shown. [Only accept ‘change status’; ‘c.s.’; sight of the connectives being swapped]

a3A1 CAO must ft from stated path, diagram ok

Mark scheme (b)

Scheme	Marks
Gives another solution	M1 1A1 2A1
	(3)
	(7 marks)

Notes

b1M1 A second path from G to 4 (or vice versa)

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

b2A1 CAO must ft from stated paths, diagram ok.