Matchings

Define the terms

bipartite graph,

alternating path.

At a hotel, six guests, A, B, C, D, E and F, are to be allocated to six rooms, 1, 2, 3, 4, 5 and 6. Each room needs to be allocated to exactly one guest. A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.

Starting from the initial matching given in Figure 2, apply the maximum matching algorithm to find an alternating path from F to 5. Hence find an improved matching. You must list the alternating path that you use and state your improved matching.

Guest C now has room 5 added to his possible allocations.

Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You must list the alternating path that you use and state your complete matching.

Define the term ‘bipartite graph’.

Figure 1 shows the possible allocations of five people, Larry (L), Monisha (M), Nina (N), Phil (P) and Theo (T), to five activities, A, B, C, D and E. Figure 2 shows an initial matching.

Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path you use and state your complete matching.

A delivery firm has six vans, A, B, C, D, E and F, available for six deliveries, 1, 2, 3, 4, 5 and 6. Each van must be assigned to just one delivery. The bipartite graph shown in Figure 1 shows the possible matchings and Figure 2 shows an initial matching. A complete matching is required, starting from the given initial matching.

Explain why it is necessary to use the maximum matching algorithm twice.

There are three possible alternating paths that start at either D or B. One of these is D – 2 = A – 3 = F – 6 = E – 5

Find the other two alternating paths.

List the improved matching generated by using the alternating path D – 2 = A – 3 = F – 6 = E – 5

Starting from the improved matching found in (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use and your complete matching.

Figure 1 shows the possible allocations of six people, Alex (A), Ben (B), Harriet (H), Izzy (I), Leo (L) and Rowan (R), to six tasks, 1, 2, 3, 4, 5 and 6.

Write down the technical name given to the type of diagram shown in Figure 1.

Figure 2 shows an initial matching.

Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use, and state your improved matching after each iteration.

Figure 1 shows the possible allocations of six people, A, B, C, D, E and F, to six tasks, 1, 2, 3, 4, 5

Figure 2 shows an initial matching.

Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching.

Explain why it is not possible to find a complete matching.

After training, task 4 is added to F’s possible allocation and task 6 is added to E’s possible allocation.

Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you used and your complete matching.

Figure 2 shows the possible allocations of six workers, Charlie (C), George (G), Jack (J), Nurry (N), Olivia (O) and Rachel (R), to six tasks, 1, 2, 3, 4, 5 and 6. Figure 3 shows an initial matching.

Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should give the alternating path you use and list your improved matching.

Explain why it is not possible to find a complete matching.

After training, Charlie adds task 5 to his possible allocations.

Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. Give the alternating path you use and list your complete matching.

Figure 1 shows the possible allocations of five workers, Charles (C), David (D), Ellie (E), Freya (F) and Georgi (G), to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.

Starting from this initial matching, use the maximum matching algorithm to find a complete matching. State clearly the alternating path that you use and list your final matching.

Find another solution starting from the given initial matching. You should state the alternating

Figure 3 shows the possible allocations of five workers, Adam (A), Catherine (C), Harriet (H), Josh (J) and Richard (R) to five tasks, 1, 2, 3, 4 and 5. Figure 4 shows an initial matching. There are three possible alternating paths that start at A. One of them is A – 3 = R – 4 = C – 5

Find the other two alternating paths that start at A.

List the improved matching generated by using the alternating path A – 3 = R – 4 = C – 5.

Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path used and your final matching.

Six workers, Anthony, Beth, David, Jacob, Kantola and Miri, are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. Figure 3 shows the possible allocations of the workers, and an initial matching is shown in Figure 4.

Write down the technical name given to the type of diagram shown in Figure 3.

Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and your improved matching.

Anthony now agrees to add task 6 to his possible allocations.

Starting with your improved matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching.