D1 June 2007 Q2

EdexcelOld spec7 marksAllocation

Figure 1: bipartite graph joining workers A, E, H, J, L, M to tasks 1a, 1b, 2, 3, 4, 5 — Figure 1

Figure 2: initial matching A-1a, E-1b, H-3, J-5, M-2 — Figure 2

Six workers, Annie, Emma, Hannah, Jerry, Louis and Morand, are to be assigned to five tasks, 1,2,3,4 and 5.

For safety reasons, task 1 must be done by two people working together.

A bipartite graph showing the possible allocations of the workers is given in Figure 1 and an initial matching is given in Figure 2.

The maximum matching algorithm will be used to obtain a complete matching.

(a) Although there are five tasks, six vertices have been created on the right hand side of each bipartite graph. Explain why this is necessary when applying this algorithm. (2)

(b) Find an alternating path and the complete matching it gives. (3)

Hannah is now unable to do task 5 due to health reasons.

Scheme	Marks
To obtain a complete matching the number of vertices on each side must be equal.	B2, 1, 0
	(2)

Scheme	Marks
e.g. L – 3 = H – 5 = J – 1a = A – 4	M1 A1
c.s. L = 3 – H = 5 – J = 1a – A = 4
A = 4 H = 5 L = 3 E = 1b J = 1a M = 2	A1
	(3)

Scheme	Marks
H and L can now both only do 3. So a complete matching is not possible (other answers possible)	B2, 1, 0
	(2)
	(7 marks)