D1 January 2013 Q3

EdexcelOld spec8 marksAllocation

Figure 2: bipartite graph of possible allocations of C, G, J, N, O, R to tasks 1 to 6 — Figure 2

Figure 3: initial matching G–5, J–6, N–4, R–3 — Figure 3

Figure 2 shows the possible allocations of six workers, Charlie (C), George (G), Jack (J), Nurry (N), Olivia (O) and Rachel (R), to six tasks, 1, 2, 3, 4, 5 and 6.

Figure 3 shows an initial matching.

(a) Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should give the alternating path you use and list your improved matching. (3)

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

After training, Charlie adds task 5 to his possible allocations.

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

Mark scheme (a)

Scheme

Marks

(i) C – 4 = N – 6 = J – 3 = R – 2 or (ii) O – 6 = J – 3 = R – 2

Change status to give
(i) C = 4 – N = 6 – J = 3 – R = 2 or (ii) O = 6 – J = 3 – R = 2

Improved matching is:

	C	G	J	N	O	R
(i)	4	5	3	6		2
(ii)		5	3	4	6	2

(3)

Notes

a1M1 An alternating path (e.g. letter - number - letter - …) from C or O to 2 or vice versa.

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

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

Mark scheme (b)

Scheme	Marks
E.g. Tasks 1 and 5 can only be done by George E.g. Charlie can only do task 4 and Olivia can only do task 6 which means that Nurry can’t be allocated a task as Nurry can only do tasks 4 and 6	B2, 1, 0
	(2)

Notes

b1B1 Correct idea, may be imprecise or muddled (bod gets B1) all relevant nodes must be referred to and must be correct.

b2B1 Good, clear, complete, correct answer (this needs to be checked carefully e.g. G can only do tasks 1 and 5 is B1 only).

Mark scheme (c)

Scheme	Marks
O – 6 = N – 4 = C – 5 = G – 1 or C – 5 = G – 1	M1
Change status to give O = 6 – N = 4 – C = 5 – G = 1 or C = 5 – G = 1	A1
Maximum matching is: C = 5, G = 1, J = 3, N = 4, O = 6, R = 2	A1
	(3)
	(8 marks)

Notes

c1M1 A second alternating path from O or C to 1 (whichever letter (of O or C) that they didn’t use before) or vice versa.

c1A1 CAO including change status (stated or shown), chosen path clear.

c2A1 CAO must follow from two correct stated paths (so both previous M marks must have been awarded). Accept on a clear diagram (with six arcs only).