D1 January 2005 Q1

EdexcelOld spec6 marksAllocation

1.

Figure 1: bipartite graph joining A, D, J, P, S, T to tasks 1 to 6
Figure 1

The bipartite graph in Figure 1 shows a mapping between six people, Andy (\(A\)), David (\(D\)), Joan (\(J\)), Preety (\(P\)), Sally (\(S\)) and Trevor (\(T\)), and six tasks 1, 2, 3, 4, 5 and 6.

The initial matching is \(A\) to 2, \(D\) to 1, \(J\) to 3 and \(P\) to 4.

(a) Indicate this initial matching in a distinctive way on the bipartite graph drawn 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 you use. (5)
‹ Previous59 of 59 in Allocation