D1 January 2006 Q1

EdexcelOld spec7 marksAllocation

1.

Figure 1: bipartite graph joining taxis A to F with journeys 1 to 6
Figure 1
Figure 2: initial matching A to 5, B to 2, C to 3, D to 6
Figure 2

A taxi firm has six taxis \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\), available for six journeys, 1, 2, 3, 4, 5 and 6, which are booked for 9 a.m. tomorrow.

The bipartite graph shown in Figure 1 shows the possible matchings.

Initially \(A\), \(B\), \(C\) and \(D\) are matched to 5, 2, 3 and 6 respectively, as indicated in Figure 2.

(a) Explain why it is necessary to perform the maximum matching algorithm twice in order to try to obtain a complete matching. (1)
(b) Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use. (6)
‹ Previous56 of 59 in AllocationNext ›