D1 January 2007 Q2

EdexcelOld spec7 marksAllocation

2.

Figure 1: bipartite graph joining Ellen, George, Jo, Lydia, Yi Wen with tasks 1 to 5
Figure 1
Figure 2: initial matching Ellen to 2, Jo to 3, Lydia to 4
Figure 2

Figure 1 shows the possible allocations of five people, Ellen, George, Jo, Lydia and Yi Wen to five tasks, 1, 2, 3, 4 and 5.

Figure 2 shows an initial matching.

(a) Find an alternating path linking George with 5. List the resulting improved matching this gives. (3)
(b) Explain why it is not possible to find a complete matching. (1)

George now has task 2 added to his possible allocation.

(c) Using the improved matching found in part (a) as the new initial matching, find an alternating path linking Yi Wen with task 1 to find a complete matching. List the complete matching. (3)
‹ Previous51 of 59 in AllocationNext ›