D1 January 2009 Q4
4.
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.
Figure 2 shows an initial matching.
(a) Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used, and your improved matching. (3)
(b) Explain why it is not possible to find a complete matching. (2)
D now has task 2 added to their possible allocation.
(c) Using the improved matching found in part (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path used and your complete matching. (3)
| Scheme | Marks |
|---|---|
| Alternating path B – 3 = A – 5 change status B = 3 – A = 5 | M1 A1 |
| A = 5 B = 3 C = 2 D = 1 E = 6 F unmatched | A1 |
| (3) |
Notes
(a) 1M1: Path from B to 5.
1A1: Correct path including change status
2A1: CAO my matching, may be drawn but if so 5 lines only and clear.
| Scheme | Marks |
|---|---|
| e.g. C is the only person able to do 2 and the only person able to do 4. Or D, E and F between them can only be allocated to 1 and 6. | B2, 1, 0 |
| (2) |
Notes
(b) 1B1: Close, a correct relevant, productive statement bod generous
2B1: A Good clear answer generous
| Scheme | Marks |
|---|---|
| Alternating path F – 6 = E – 1 = D – 2 = C – 4 change status F = 6 – E = 1 – D = 2 – C = 4 | M1 A1 |
| A = 5 B = 3 C = 4 D = 2 E = 1 F = 6 | A1 |
| (3) | |
| (8 marks) |
Notes
(c) 1M1: Path from F to 4. No ft.
1A1: Correct path penalise lack of change status once only
2A1: CAO may be drawn but if so 6 lines only and clear