D1 January 2008 Q1

EdexcelOld spec9 marksAllocation

1.

(a) Define the terms
(i) alternating path, (2)
(ii) matching. (2)
Figure 1: bipartite graph joining teachers A to E to stalls 1 to 5
Figure 1
Figure 2: initial matching A-2, B-4, C-3
Figure 2

At a school fair, five teachers, \(A\), \(B\), \(C\), \(D\) and \(E\), are to supervise five stalls, 1, 2, 3, 4 and 5.

A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.

(b) Use the maximum matching algorithm twice to obtain a complete matching.
List clearly the alternating paths you use. (5)
‹ Previous48 of 59 in AllocationNext ›