D1 June 2011 Q4

EdexcelOld spec7 marksAllocation

Figure 3: bipartite graph; A to 1 and 3; C to 3, 4 and 5; H to 1, 2 and 3; J to 4; R to 3 and 4 — Figure 3

Figure 4: initial matching C to 4, H to 1, R to 3 — Figure 4

Figure 3 shows the possible allocations of five workers, Adam (A), Catherine (C), Harriet (H), Josh (J) and Richard (R) to five tasks, 1, 2, 3, 4 and 5.

Figure 4 shows an initial matching.

There are three possible alternating paths that start at A.
One of them is

A – 3 = R – 4 = C – 5

(a) Find the other two alternating paths that start at A. (3)

(b) List the improved matching generated by using the alternating path A – 3 = R – 4 = C – 5. (1)

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

Mark scheme (a)

Scheme	Marks
[Given A – 3 = R – 4 = C – 5 ] A – 1 = H – 2	M1 A1
A – 1 = H – 3 = R – 4 = C – 5	A1
	(3)

Notes

(a)M1 Path from A to 2 or 5 - or vice versa

1A1 One correct path selected OR tree showing the missing two paths only.

2A1 Both correct paths listed separately

Scheme	Marks
A = 3, C = 5, H = 1, (J unmatched), R = 4	B1
	(1)

Mark scheme (c)

Scheme	Marks
Alternating path : J – 4 = R – 3 = A – 1 = H – 2	M1
Change status : J = 4 – R = 3 – A = 1 – H = 2	A1
A = 1, C = 5, H = 2, J = 4, R = 3	A1
	(3)
	(7 marks)

Notes

(c)M1 Path from J to 2 – or vice versa

1A1 Correct path including change status

2A1 CAO must follow through from stated path.