D1 June 2009 Q3

EdexcelOld spec7 marksAllocation

Figure 1: bipartite graph joining workers C, E, H, M, R, S to tasks 1 to 6 — Figure 1

Figure 2: initial matching C-3, M-2, R-5, S-1 — Figure 2

Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6.

Figure 2 shows an initial matching.

(a) List an alternating path, starting at H and ending at 4. Use your path to find an improved matching. List your improved matching. (3)

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

Simon (S) now has task 3 added to his possible allocation.

(c) Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching. (3)

Mark scheme (a)

Scheme	Marks
H – 2 = M – 5 = R – 4 change status to give	M1 A1
C = 3 (E unmatched) H = 2 M = 5 R = 4 S = 1	A1
	(3)

Notes

(a) 1M1: Path from H to 4

1A1: correct path and change status

2A1: CAO must follow from correct path.

Scheme	Marks
e.g. C is the only person who can do 3 and the only person who can do 6	B1
	(1)

Mark scheme (c)

Scheme	Marks
e.g. E – 5 = M – 2 = H – 1 = S – 3 = C – 6 change status to give	M1 A1
C = 6 E = 5 H = 1 M = 2 R = 4 S = 3	A1
	(3)
	(7 marks)

Notes

1A1: CAO do not penalise lack of change status a second time.

2A1: CAO must follow from a correct path