D1 June 2018 Q5

EdexcelOld spec6 marksAllocation

Figure 3: bipartite graph joining workers C, D, H, R, S to tasks 1 to 5 — Figure 3

Figure 3 shows the possible allocations of five workers, Cole (C), Dorothy (D), Harold (H), Richard (R) and Stephen (S), to five tasks, 1, 2, 3, 4 and 5.

In an initial matching, each of three workers is allocated to a different task.

For this initial matching, there are three possible alternating paths that start at C.

One alternating path is

C − 3 = S − 4 = D − 5

A second alternating path is

C − 1 = H − 2

(a) Use this information to deduce the initial matching. (1)

(b) Find the third alternating path that starts at C. (1)

(d) Starting from the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching. (3)

Scheme	Marks
Initial matching: (C unmatched), D = 4, H = 1, (R unmatched), S = 3	B1
	(1)

Mark scheme (b)

Scheme	Marks
Alternating path: C – 1 = H – 3 = S – 4 = D – 5	B1
	(1)

Notes

b1B1: CAO (alternating path) – allow any unambiguous notation e.g. C – 1 – H – 3 – S – 4 – D – 5 but do not allow C – 1, H – 3, S – 4, D – 5 (as this is not a path but a matching)

Scheme	Marks
Improved matching: C = 3, D = 5, H = 1, (R unmatched), S = 4	B1
	(1)

Mark scheme (d)

Scheme	Marks
Alternating path: R – 4 = S – 3 = C – 1 = H – 2	M1
Change status to give: R = 4 – S = 3 – C = 1 – H = 2	A1
Complete matching: C = 1, D = 5, H = 2, R = 4, S = 3	A1
	(3)
	(6 marks)

Notes

d1M1: An alternating path (e.g. letter 1st set – number 2nd set – letter 1st set – …) from R to 2 (or vice-versa)

d1A1: CAO – a correct path including change status either stated (only accept ‘change (of) status’ or ‘c.s’ but not, e.g.‘change state’) or shown (all symbols e.g. (… – … = … – …) interchanged (… = …. – … = …)) Chosen path clear

d2A1: CAO – complete matching - must follow from the correct stated path. Accept either stated or on a clear diagram (with five arcs only)