D1 January 2011 Q4

EdexcelOld spec7 marksAllocation

Figure 3: bipartite graph; A to 2 and 5; B to 1, 3 and 6; D to 2 and 5; J to 3; K to 1, 4 and 6; M to 2 and 5 — Figure 3

Figure 4: initial matching A to 2, B to 3, K to 6, M to 5 — Figure 4

Six workers, Anthony, Beth, David, Jacob, Kantola and Miri, are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6.

Figure 3 shows the possible allocations of the workers, and an initial matching is shown in Figure 4.

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

(b) Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and your improved matching. (3)

Anthony now agrees to add task 6 to his possible allocations.

(c) Starting with your improved matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching. (3)

Scheme	Marks
Bipartite graph	B1

Mark scheme (b)

Scheme	Marks
e.g. J – 3 = B – 6 = K – 1	M1
Change status J = 3 – B = 6 – K = 1	A1
A = 2 B = 6 (D unmatched) J = 3 K = 1 M = 5	A1
	(3)

Notes

1M1: Path from J to 1 or 4 (or vice versa)

1A1: CAO including change status (stated or shown), chosen path clear.

2A1: CAO must ft from stated path, diagram ok

Alternative answers (b)

Path	A B D J K M
J – 3 – B – 1	2 1 – 3 6 5
J – 3 – B – 6 – K – 1	2 6 – 3 1 5
J – 3 – B – 6 – K – 4	2 6 – 3 4 5

Mark scheme (c)

Scheme	Marks
e.g. D – 2 = A – 6 = B – 1 = K – 4	M1
Change status D = 2 – A = 6 – B = 1 – K = 4	A1
A = 6 B = 1 D = 2 J = 3 K = 4 M = 5	A1
	(3)
	(7 marks)

Notes

1M1: Path from D to 4 or 1 (or vice versa)

1A1: CAO including change status (stated or shown),but only penalise once per question, chosen path clear.

2A1: CAO must ft from stated paths, diagram ok. Must have both M’s.

Alternative answers (c)

Path	A B D J K M
D – 2 – A – 6 – K – 4 D – 5 – M – 2 – A – 6 – K – 4	6 1 2 3 4 5 6 1 5 3 4 2
D – 2 – A – 6 – B – 1 – K – 4 D–5–M– 2 – A – 6 – B – 1– K – 4	6 1 2 3 4 5 6 1 5 3 4 2
D – 2 – A – 6 – B – 1 D – 5 – M – 2 – A – 6 – B – 1	6 1 2 3 4 5 6 1 5 3 4 2