D1 June 2019 Q1

EdexcelOld spec7 marksAllocation

Figure 1: bipartite graph joining people A to F to tasks 1 to 6 — Figure 1

Figure 2: initial matching A to 3, C to 5, E to 6, F to 1 — Figure 2

Figure 1 shows the possible allocations of six people, A, B, C, D, E and F, to six tasks, 1, 2, 3, 4, 5 and 6

(a) Write down the technical name given to the type of diagram shown in Figure 1. (1)

Figure 2 shows an initial matching.

(b) Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use and state your improved matching after each iteration. (6)

Scheme	Marks
Bipartite (graph)	B1
	(1)

Mark scheme (b)

Scheme	Marks
e.g. (see below for alternatives)
First alternating path: B – 6 = E – 5 = C – 4	M1
Change status to give: B = 6 – E = 5 – C = 4	A1
Improved matching: A = 3, B = 6, C = 4, (D unmatched), E = 5, F = 1	A1
Second alternating path: D – 3 = A – 5 = E – 1 = F – 2	M1
Change status to give: D = 3 – A = 5 – E = 1 – F = 2	A1
Complete matching: A = 5, B = 6, C = 4, D = 3, E = 1, F = 2	A1
	(6)
	7 marks

Notes

Possible 1^st paths	A	B	C	D	E	F	Subsequent 2^nd paths
B – 6 – E – 5 – C – 4	3	6	4	-	5	1	D – 3 – A – 5 – E – 1 – F – 2
B – 6 – E – 1 – F – 2	3	6	5	-	1	2	D – 3 – A – 5 – C – 4
D – 3 – A – 5 – C – 4	5	-	4	3	6	1	B – 6 – E – 1 – F – 2

b1M1: An alternating path (e.g. letter 1^st set – number 2^nd set – letter 1^st set – …) from B to 4 (or vice-versa) or B to 2 (or vice-versa) or D to 4 (or vice-versa)

b1A1: 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

b2A1: CAO – improved matching - must follow from the correct stated path. Accept either stated or on a clear diagram (with five arcs only). Please check the top of the second page as many candidates will draw either the improved or complete matching on the nodes provided there

b2M1: An alternating path from D to 2 or D to 4 or B to 2 (or vice-versa in each case) (must be consistent with their first alternating path)

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

b4A1: CAO (complete matching) 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)

SC for (b): some candidates are writing AP2 and AP3 from the first list next to each other with no improved matching and so it is not clear if they are applying the algorithm correctly e.g.

alternating path:
B – 6 = E – 1 = F – 2; D – 3 = A – 5 = C = 4
Change status:
B = 6 – E = 1 – F = 2; D = 3 – A = 5 – C = 4
Complete matching
A = 5, B = 6, C = 4, D = 3, E = 1, F = 2

This would scored M1 A0 A0 M1 A0 A1 (neither chosen path is clear – are they choosing two APs from the first list or does one follow the other (reading across the page) – either way it is not clear)