D1 January 2010 Q1
1.
Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6.
An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5.
(a) Show this initial matching on Diagram 1 in the answer book. (1)
(b) Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching. (5)
| Scheme | Marks |
|---|---|
 | B1 |
| (1) |
Notes
B1 cao preferably just 4 lines, but accept if unambiguous.
| Scheme | Marks |
|---|---|
 | |
| E.g. Path 1 F-4-D-5-E-2 | M1 A1 |
| Path 2 B-3-C-6 | M1 A1 |
| Matching A : 1, B : 3, C : 6, D : 5, E : 2, F : 4 | A1 |
| (5) | |
| (6 marks) |
Notes
M1 attempt at a path from B or F to 2 or 6
A1 correct path – including change status
M1 attempt at a second path from F or B to 6 or 2
A1 correct path – including change status (do not penalise change status twice)
A1 correct matching; must follow from 2 correct paths
Question 1(b) Alternative Solutions
| Path 1 | Path 2 | Matching | ||||||
|---|---|---|---|---|---|---|---|---|
| A | B | C | D | E | F | |||
| 1 | B-3-C-1-A-2 | F-3-B-4-D-5-E-1-C-6 | 2 | 4 | 6 | 5 | 1 | 3 |
| 2 | B-3-C-1-A-2 | F-3-B-4-D-5-E-2-A-1-C-6 | 1 | 4 | 6 | 5 | 2 | 3 |
| 3 | B-3-C-1-A-2 | F-4-D-5-E-1-C-6 | 2 | 3 | 6 | 5 | 1 | 4 |
| 4 | B-3-C-1-A-2 | F-4-D-5-E-2-A-1-C-6 | 1 | 3 | 6 | 5 | 2 | 4 |
| 5 | B-3-C-4-D-5-E-1-A-2 | F-3-B-4-C-6 | 2 | 4 | 6 | 5 | 1 | 3 |
| 6 | B-3-C-4-D-5-E-1-A-2 | F-4-C-6 | 2 | 3 | 6 | 5 | 1 | 4 |
| 7 | B-3-C-6 | F-3-B-4-D-5-E-1-A-2 | 2 | 4 | 6 | 5 | 1 | 3 |
| 8 | B-3-C-6 | F-3-B-4-D-5-E-2 | 1 | 4 | 6 | 5 | 2 | 3 |
| 9 | B-3-C-6 | F-4-D-5-E-1-A-2 | 2 | 3 | 6 | 5 | 1 | 4 |
| 10 | B-3-C-6 | F-4-D-5-E-2 | 1 | 3 | 6 | 5 | 2 | 4 |
| 11 | B-4-D-5-E-2 | F-3-C-6 | 1 | 4 | 6 | 5 | 2 | 3 |
| 12 | B-4-D-5-E-2 | F-4-B-3-C-6 | 1 | 3 | 6 | 5 | 2 | 4 |
| 13 | B-4-D-5-E-1-A-2 | F-3-C-6 | 2 | 4 | 6 | 5 | 1 | 3 |
| 14 | B-4-D-5-E-1-A-2 | F-4-B-3-C-6 | 2 | 3 | 6 | 5 | 1 | 4 |
| 15 | F-3-C-1-A-2 | B-3-F-4-D-5-E-1-C-6 | 2 | 3 | 6 | 5 | 1 | 4 |
| 16 | F-3-C-1-A-2 | B-3-F-4-D-5-E-2-A-1-C-6 | 1 | 3 | 6 | 5 | 2 | 4 |
| 17 | F-3-C-1-A-2 | B-4-D-5-E-1-C-6 | 2 | 4 | 6 | 5 | 1 | 3 |
| 18 | F-3-C-1-A-2 | B-4-D-5-E-2-A-1-C-6 | 1 | 4 | 6 | 5 | 2 | 3 |
| 19 | F-3-C-4-D-5-E-1-A-2 | B-3-F-4-C-6 | 2 | 3 | 6 | 5 | 1 | 4 |
| 20 | F-3-C-4-D-5-E-1-A-2 | B-4-C-6 | 2 | 4 | 6 | 5 | 1 | 3 |
| 21 | F-3-C-6 | B-3-F-4-D-5-E-1-A-2 | 2 | 3 | 6 | 5 | 1 | 4 |
| 22 | F-3-C-6 | B-3-F-4-D-5-E-2 | 1 | 3 | 6 | 5 | 2 | 4 |
| 23 | F-3-C-6 | B-4-D-5-E-1-A-2 | 2 | 4 | 6 | 5 | 1 | 3 |
| 24 | F-3-C-6 | B-4-D-5-E-2 | 1 | 4 | 6 | 5 | 2 | 3 |
| 25 | F-4-D-5-E-2 | B-3-C-6 | 1 | 3 | 6 | 5 | 2 | 4 |
| 26 | F-4-D-5-E-2 | B-4-F-3-C-6 | 1 | 4 | 6 | 5 | 2 | 3 |
| 27 | F-4-D-5-E-1-A-2 | B-3-C-6 | 2 | 3 | 6 | 5 | 1 | 4 |
| 28 | F-4-D-5-E-1-A-2 | B-4-F-3-C-6 | 2 | 4 | 6 | 5 | 1 | 3 |