D1 June 2010 Q5

EdexcelOld spec8 marksAllocation

5.

Figure 3: bipartite graph; A to 2 and 4; C to 5; E to 2 and 3; G to 3; J to 5; S to 1, 4 and 6
Figure 3
Figure 4: initial matching A to 2, E to 3, J to 5, S to 4
Figure 4

Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.

(a) Use the maximum matching algorithm once to find an improved matching.
You must state the alternating path used and your improved matching. (3)
(b) Explain why a complete matching is not possible. (2)

After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.

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