Maximum matching algorithm application

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Define the term 'bipartite graph'. Figure 1 shows the possible allocations of six people, A , B , C , D , E and F , to six activities, \(1,2,3\), 4, 5 and 6 Figure 2 shows an initial matching.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.

4. (a) Define the term 'alternating path'. \begin{figure}[h] \end{figure} Figure 4 shows the possible allocations of five people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , to five tasks, \(1,2,3,4\) and 5 An initial matching has three people allocated to three of the tasks.
Starting from this initial matching, one possible alternating path that starts at E is $$E - 2 = B - 3 = A - 4 = D - 1$$ (b) Use this information to

1. deduce this initial matching,
2. list the improved matching generated by the given alternating path.
   (c) Starting from the improved matching found in (b), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.

2. Six film critics, Bronwen (B), Greg (G), Jean (J), Mick (M), Renee (R) and Susan (S), must see six films, \(1,2,3,4,5\) and 6 . Each critic must attend a different film and each critic needs to be allocated to exactly one film. The critics are asked which films they would prefer and their preferences are given in the table below.

1. Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of critics to their preferred films. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-03_616_524_1114_767} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 2 shows an initial matching.
2. Starting from the given initial matching, apply the maximum matching algorithm to find an alternating path from G to 3 . Hence find an improved matching. You should list the alternating path that you use, and state your improved matching.
   (3)
3. Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You should list the alternating path that you use, and state your complete matching.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Andrea (A), Baasim (B), Charlie (C), Deirdre (D), Ean (E) and Fen-Fang (F), to six tasks, 1, 2, 3, 4, 5 and 6.

1. Write down the technical name given to the type of graph shown in Figure 1.
   (1) Figure 2 shows an initial matching.
2. Starting from the initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path you used and state your complete matching.
3. State a different complete matching from the one found in (b).
4. By considering the workers who must be allocated to particular tasks, explain why there are exactly two different complete matchings.

2. (a) Define the terms

1. alternating path,
2. complete matching.
   (4) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_521_614_450_351} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_509_604_456_1098} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 1 shows the possible allocations of six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, \(1,2,3,4,5\) and 6. Each task must be assigned to only one worker and each worker must be assigned to exactly one task. Figure 2 shows an initial matching.
   (b) Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from F to 1. Hence find an improved matching. You must write down the alternating path used and state your improved matching.
   (3)
   (c) Explain why it is not possible to find a complete matching.
   (1) Worker C has task 1 added to his possible allocations.
   (d) Starting from the improved matching found in (b), use the maximum matching algorithm to find a complete matching. You must write down the alternating path used and state your complete matching.

5. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.

1. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching.
2. Explain why a complete matching is not possible. After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
3. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching.

4. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 2 shows an initial matching.

1. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used, and your improved matching.
2. Explain why it is not possible to find a complete matching. D now has task 2 added to their possible allocation.
3. Using the improved matching found in part (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path used and your complete matching.
   (3)

1. \begin{figure}[h] \end{figure} Figure 1 shows the possible allocation of six people, Alice (A), Brian (B), Christine (C), David (D), Elizabeth (E) and Freddy (F), to six tasks, 1, 2, 3, 4, 5 and 6. An initial matching is Alice to task 1, Christine to task 3, David to task 4 and Elizabeth to task 5.

1. Show this initial matching on Diagram 1 in the answer book.
   (1)
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths that you use, and give your final matching.
   (5)

4. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} 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.

1. Write down the technical name given to the type of diagram shown in Figure 3.
2. 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.
3. 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.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Define the terms

1. bipartite graph,
2. matching. Figure 3 shows the possible allocations of six people, Charles (C), Emily (E), George (G), Harriet (H), Jack (J) and Shen (S), to six tasks, 1, 2, 3, 4, 5 and 6. Figure 4 shows an initial matching.
3. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you use and state your improved matching. Emily has task 5 added to her possible allocations and Harriet has task 3 added to her possible allocations.
4. Starting from the improved matching found in part (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use and state your improved matching.
   (3)
   (Total 10 marks)

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} 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.

1. 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.
2. Explain why it is not possible to find a complete matching. After training, Charlie adds task 5 to his possible allocations.
3. 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.

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Five tour guides, Alice, Emily, George, Rose and Weidi, need to be assigned to five coach trips, 1, 2, 3, 4 and 5 . A bipartite graph showing their preferences is given in Figure 1 and an initial matching is given in Figure 2.

1. Use the maximum matching algorithm, starting with vertex G , to increase the number of matchings. State the alternating path you used.
2. List the improved matching you found in (a).
3. Explain why a complete matching is not possible. Weidi agrees to be assigned to coach trip 3, 4 or 5.
4. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching.
   (3)

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} 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.

1. 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.
   (4)
2. Find another solution starting from the given initial matching. You should state the alternating path and list the complete matching it gives.
   (3)

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.

1. 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.
2. 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.
3. 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.

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} 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.

1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
2. 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.
   (6)

4. Six pupils, Ashley (A), Fran (F), Jas (J), Ned (N), Peter (P) and Richard (R), each wish to learn a musical instrument. The school they attend has six spare instruments; a clarinet (C), a trumpet (T), a violin (V), a keyboard (K), a set of drums (D) and a guitar (G). The pupils are asked which instruments they would prefer and their preferences are given in the table above. It is decided that each pupil must learn a different instrument and each pupil needs to be allocated to exactly one of their preferred instruments.

1. Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of pupils to instruments. Initially Ashley, Fran, Jas and Richard are each allocated to their first preference.
2. Show this initial matching on Diagram 2 in the answer book.
3. Starting with the initial matching from (b), apply the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and give your improved matching.
4. Explain why a complete matching is not possible. Fran decides that as a third preference she would like to learn to play the guitar. Peter decides that as a second preference he would like to learn to play the drums.
5. Starting with the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching.

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} A delivery firm has six vans, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { 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.

1. 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$$
2. Find the other two alternating paths.
3. List the improved matching generated by using the alternating path $$D - 2 = A - 3 = F - 6 = E - 5$$
4. 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.

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. 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.
2. 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.

5. \begin{figure}[h] \end{figure} Figure 3 shows the possible allocations of five workers, Cole (C), Dorothy (D), Harold (H), Richard (R) and Stephen (S), to five tasks, 1, 2, 3, 4 and 5. In an initial matching, each of three workers is allocated to a different task. For this initial matching, there are three possible alternating paths that start at C . One alternating path is $$C - 3 = S - 4 = D - 5$$ A second alternating path is $$\mathrm { C } - 1 = \mathrm { H } - 2$$

1. Use this information to deduce the initial matching.
2. Find the third alternating path that starts at C .
3. List the improved matching generated by using the alternating path \(\mathrm { C } - 3 = \mathrm { S } - 4 = \mathrm { D } - 5\)
4. Starting from the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.
   (3)

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, \(1,2,3\), 4, 5 and 6

1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
2. 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.
   (6)

4. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Six airline pilots, Alice, Dan, Miya, Phil, Sophie and Tom, are to be assigned to six flights, 1, 2, 3, 4, 5 and 6. A bipartite graph showing the possible allocations is shown in Figure 2, and an initial matching is given in Figure 3. The maximum matching algorithm will be used to obtain a complete matching.

1. Starting from A, find an alternating path that leads to an improved matching and list the improved matching that it gives.
   (3)
2. Using the improved matching found in part (a) as the new initial matching, find a complete matching. You must state any alternating paths you use and list your final complete matching.

3. At a water sports centre there are five new instructors. Ali (A), George ( \(G\) ), Jo ( \(J\) ), Lydia ( \(L\) ) and Nadia \(( N )\). They are to be matched to five sports, canoeing \(( C )\), scuba diving \(( D )\), surfing \(( F )\), sailing ( \(S\) ) and water skiing ( \(W\) ). The table indicates the sports each new instructor is qualified to teach. Initially, \(A , G , J\) and \(L\) are each matched to the first sport in their individual list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must clearly list any alternating paths used. Given that on a particular day \(J\) must be matched to \(D\),
3. explain why it is no longer possible to find a complete matching. \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-4_720_1305_391_236} Figure 2 models an underground network of pipes that must be inspected for leaks. The nodes \(A\), \(B , C , D , E , F , G\) and \(H\) represent entry points to the network. The number on each arc gives the length, in metres, of the corresponding pipe. Each pipe must be traversed at least once and the length of the inspection route must be minimised.