D1 June 2014 (R) Q2

EdexcelOld spec7 marksAllocation

Figure 1: bipartite graph joining employees A, C, H, J, P to tasks 1 to 5 — Figure 1

Figure 2: initial matching C to 4, H to 1, J to 5, P to 2 — Figure 2

Figure 1 shows the possible allocations of five employees, Ali (A), Campbell (C), Hugo (H), Janelle (J) and Polly (P), to five tasks 1, 2, 3, 4 and 5.

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

It is decided that one of the employees should be trained so that a complete matching becomes possible. There are only enough funds for one employee to be trained.

Two employees volunteer to undergo training. Janelle can be trained to do task 1 or Hugo can be trained to do task 5.

(b) Decide which employee, Janelle or Hugo, should undergo training. Give a reason for your answer. (2)

You may now assume that the employee you identified in (b) has successfully undergone training.

Figure 2 shows an initial matching.

(c) Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state the complete matching. (3)

Mark scheme (a)

Scheme	Marks
e.g. Activities 1 and 3 both can only be done by Hugo	B2, 1, 0
	(2)

Notes

a1B1: A statement with the correct employees and tasks that attempts a reason why a complete matching is not possible. BOD gets the mark here. Note e.g. ‘Hugo is the only one who can do both 1 and 3’ or ‘Hugo can only do 1 and 3’ are both B1 only.

a2B1: Fully correct, including all pertinent names and activities. No incorrect information given.

Mark scheme (b)

Scheme	Marks
J to 1 should be chosen	M1
e.g. J to 1 would release H to do 3. e.g. if H is retrained then tasks 1 and 3 can still only be done by H.	A1
	(2)

Notes

b1M1: J to 1 selected with a reason given. One of H, 1 or 3 must be mentioned.

b1A1: A correct reason given – must explicitly explain why J with 1 allows a complete matching to occur e.g. H can now do 3, or the candidate explains that if Hugo is re-trained there are still two tasks, 1 and 3, that can only be done by one employee, H.

Mark scheme (c)

Scheme	Marks
A – 2 = P – 4 = C – 5 = J – 1 = H – 3	M1
Change status A = 2 – P = 4 – C = 5 – J = 1 – H = 3	A1
Complete matching: A = 2, C = 5, H = 3, J = 1 and P = 4	A1
	(3)
	(7 marks)

Notes

c1M1: An alternating path from A to 3 (or vice versa).

c1A1: CAO – a correct path including change status either stated or shown. Chosen path clear.

c2A1: CAO must follow from the correct stated path. Accept on a clear diagram (with five arcs only).