Maximum matching algorithm application

3. \begin{figure}[h] \end{figure} The bipartite graph in Fig. 2 shows the possible allocations of people \(A , B , C , D , E\) and \(F\) to tasks \(1,2,3,4,5\) and 6. An initial matching is obtained by matching the following pairs \(A\) to \(3 , \quad B\) to \(4 , \quad C\) to \(1 , \quad F\) to 5 .

1. Show this matching in a distinctive way on the diagram in the answer book.
2. Use an appropriate algorithm to find a maximal matching. You should state any alternating paths you have used.
   (5)

3. Six newspaper reporters Asif (A), Becky (B), Chris (C), David (D), Emma (E) and Fred (F), are to be assigned to six news stories Business (1), Crime (2), Financial (3), Foreign (4), Local (5) and Sport (6). The table shows possible allocations of reporters to news stories. For example, Chris can be assigned to any one of stories 1, 2 or 4.

1. Show these possible allocations on the bipartite graph on the diagram in the answer book. A possible matching is
   A to 5,
   C to 1 ,
   E to 6,
   F to 4
2. Show this information, in a distinctive way, on the diagram in the answer book.
   (1)
3. Use an appropriate algorithm to find a maximal matching. You should list any alternating paths you have used.
4. Explain why it is not possible to find a complete matching.

1 Answer this question on the insert provided. Mrs Price has bought six T shirts for her children. Each child is to have two shirts.
Amanda would like the green shirt, the pink shirt or the red shirt.
Ben would like the green shirt, the turquoise shirt, the white shirt or the yellow shirt.
Carrie would like the pink shirt, the white shirt or the yellow shirt.

1. On the first diagram in the insert, draw a bipartite graph to show which child would like which shirt. The children are represented as \(A 1 , A 2 , B 1 , B 2 , C 1\) and \(C 2\) and the shirts as \(G , P , R , T , W\) and \(Y\). Initially, Mrs Price puts aside the green shirt and the pink shirt for Amanda, the turquoise shirt and the white shirt for Ben and the yellow shirt for Carrie.
2. Show this incomplete matching on the second diagram in the insert.
3. Write down an alternating path consisting of three arcs to enable the matching to be improved. Use your alternating path to match the children to the shirts.
4. Amanda decides that she does not like the green shirt after all. Which shirts should each child have now?

4. This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: $$\begin{aligned} & \text { Mr. Ahmed } ( A ) \text { - Monday and Wednesday; } \\ & \text { Miss Brown } ( B ) \text { - Monday, Wednesday and Friday; } \\ & \text { Ms. Clough } ( C ) \text { - Monday; } \\ & \text { Mr. Dingle } ( D ) \text { - Tuesday, Wednesday and Thursday; } \\ & \text { Mrs. Evans } ( E ) \text { - Wednesday and Thursday. } \end{aligned}$$ The manager initially suggests that \(A\) might work on Monday, \(B\) on Wednesday and \(D\) on Thursday.

1. Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion.
   (2 marks)
2. Obtain an alternating path, starting at \(C\), and use this to improve the initial matching.
3. Find another alternating path and hence obtain a complete matching.
   (3 marks)

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.

1. List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
2. Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
3. Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching.
   (3)

1

1. Draw a bipartite graph representing the following adjacency matrix.
   (2 marks)

   	\(\boldsymbol { U }\)	\(V\)	\(\boldsymbol { W }\)	\(\boldsymbol { X }\)	\(\boldsymbol { Y }\)	\(\boldsymbol { Z }\)
   \(\boldsymbol { A }\)	1	0	1	0	1	0
   \(\boldsymbol { B }\)	0	1	0	1	0	0
   \(\boldsymbol { C }\)	0	1	0	0	0	1
   \(\boldsymbol { D }\)	0	0	0	1	0	0
   \(\boldsymbol { E }\)	0	0	1	0	1	1
   \(\boldsymbol { F }\)	0	0	0	1	1	0

2. Given that initially \(A\) is matched to \(W , B\) is matched to \(X , C\) is matched to \(V\), and \(E\) is matched to \(Y\), use the alternating path algorithm, from this initial matching, to find a complete matching. List your complete matching.

2 Five people \(A , B , C , D\) and \(E\) are to be matched to five tasks \(R , S , T , U\) and \(V\).
The table shows the tasks that each person is able to undertake.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task \(V , B\) to task \(R , C\) to task \(T\), and \(E\) to task \(U\). Demonstrate, by using an alternating path from this initial matching, how each person can be matched to a task.

1 Five people, \(A , B , C , D\) and \(E\), are to be matched to five tasks, \(J , K , L , M\) and \(N\). The table shows the tasks that each person is able to undertake.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task \(N , B\) to task \(J , C\) to task \(L\), and \(E\) to task \(M\). Complete the alternating path \(D - M \ldots\), from this initial matching, to demonstrate how each person can be matched to a task.
   (3 marks)

2 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake. \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_401_517_429_751} \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_408_520_943_751}

1. Represent this information in an adjacency matrix.
2. Initially, \(B\) is assigned to task \(1 , C\) to task \(2 , D\) to task 4, and \(E\) to task 5 . Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task.

1 Six girls, Alfonsa (A), Bianca (B), Claudia (C), Desiree (D), Erika (E) and Flavia (F), are going to a pizza restaurant. The restaurant provides a special menu of six different pizzas: Margherita (M), Neapolitana (N), Pepperoni (P), Romana (R), Stagioni (S) and Viennese (V). The table shows the pizzas that each girl likes.

1. Show this information on a bipartite graph.
2. Each girl is to eat a different pizza. Initially, the waiter brings six different pizzas and gives Alfonsa the Pepperoni, Bianca the Romana, Claudia the Neapolitana and Erika the Stagioni. The other two pizzas are put in the middle of the table. From this initial matching, use the maximum matching algorithm to obtain a complete matching so that every girl gets a pizza that she likes. List your complete matching.

2 A father is going to give each of his five daughters: Grainne ( \(G\) ), Kath ( \(K\) ), Mary ( \(M\) ), Nicola ( \(N\) ) and Stella ( \(S\) ), one of the five new cars that he has bought: an Audi ( \(A\) ), a Ford Focus ( \(F\) ), a Jaguar ( \(J\) ), a Peugeot ( \(P\) ) and a Range Rover ( \(R\) ). The daughters express preferences for the car that they would like to be given, as shown in the table.

1. Show all these preferences on a bipartite graph.
2. Initially the father allocates the Peugeot to Kath, the Jaguar to Mary, and the Audi to Nicola. Demonstrate, by using alternating paths from this initial matching, how each daughter can be matched to a car which is one of her preferences.
   (6 marks)

1 Five people, \(A , B , C , D\) and \(E\), are to be matched to five tasks, 1, 2, 3, 4 and 5. The table shows which tasks each person can do.

1. Show this information on a bipartite graph.
2. Initially \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5 . Use an alternating path from this initial matching to find a complete matching.

1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 . The following adjacency matrix shows the possible matching of people to tasks.

1. Show this information on a bipartite graph.
2. At first \(F\) insists on being matched to task 4. Explain why, in this case, a complete matching is impossible.
3. To find a complete matching \(F\) agrees to be assigned to either task 4 or task 5. Initially \(B\) is matched to task 3, \(C\) to task 6, \(E\) to task 2 and \(F\) to task 4.
   From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.

1 Five people, \(A , B , C , D\) and \(E\), are to be allocated to five tasks, 1, 2, 3, 4 and 5 . The following bipartite graph shows the tasks that each person is able to undertake. \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-02_441_437_699_797}

1. Represent this information in an adjacency matrix.
2. Initially, \(A\) is allocated to task 3, \(B\) to task 2 and \(C\) to task 4.
   1. Demonstrate, by using an alternating-path algorithm from this initial matching, how each person can be allocated to a different task.
   2. Find a different allocation of people to tasks.

1 A quiz team must answer questions from six different topics, numbered 1 to 6. The team has six players, \(A , B , C , D , E\) and \(F\). Each player can only answer questions on one of the topics. The players list their preferred topics. The bipartite graph shows their choices. \includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-02_711_499_781_760} Initially, \(A\) is allocated topic 2, \(B\) is allocated topic \(3 , C\) is allocated topic 1 and \(F\) is allocated topic 4. By using an alternating path algorithm from this initial matching, find a complete matching.
[0pt] [5 marks]

1 Alfred has bought six different chocolate bars. He wants to give a chocolate bar to each of his six friends. The table gives the names of the friends and indicates which of Alfred's six chocolate bars they like.

1 The famous fictional detective Agatha Parrot is investigating a murder. She has identified six suspects: Mrs Lemon \(( L )\), Prof Mulberry \(( M )\), Mr Nutmeg \(( N )\), Miss Olive \(( O )\), Capt Peach \(( P )\) and Rev Quince \(( Q )\). The table shows the weapons that could have been used by each suspect.

1. Draw a bipartite graph to represent this information. Put the weapons on the left-hand side and the suspects on the right-hand side. Agatha Parrot is convinced that all six suspects were involved, and that each used a different weapon. She originally thinks that the axe handle was used by Prof Mulberry, the broomstick by Miss Olive, the drainpipe by Mrs Lemon, the fence post by Mr Nutmeg and the golf club by Capt Peach. However, this would leave the hammer for Rev Quince, which is not a possible pairing.
2. Draw a second bipartite graph to show this incomplete matching.
3. Construct the shortest possible alternating path from \(H\) to \(Q\) and hence find a complete matching. Write down which suspect used each weapon.
4. Find a different complete matching in which none of the suspects used the same weapon as in the matching from part (iii).

This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: Mr. Ahmed (A) -- Monday and Wednesday; Miss Brown (B) -- Monday, Wednesday and Friday; Ms. Clough (C) -- Monday; Mr. Dingle (D) -- Tuesday, Wednesday and Thursday; Mrs. Evans (E) -- Wednesday and Thursday. The manager initially suggests that A might work on Monday, B on Wednesday and D on Thursday.

1. Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion. [2 marks]
2. Obtain an alternating path, starting at C, and use this to improve the initial matching. [3 marks]
3. Find another alternating path and hence obtain a complete matching. [3 marks]

Ann, Bryn, Daljit, Gareth and Nickos have all joined a new committee. Each of them is to be allocated to one of five jobs 1, 2, 3, 4 or 5. The table shows each member's preferences for the jobs. Initially Ann, Bryn, Daljit and Gareth are allocated the first job in their lists shown in the table.

1. Draw a bipartite graph to model the preferences shown in the table and indicate, in a distinctive way, the initial allocation of jobs. [2]
2. Use the matching improvement algorithm to find a complete matching, showing clearly your alternating path. [3]
3. Find a second alternating path from the initial allocation. [1]

At Tesafe supermarket there are 5 trainee staff, Homan \((H)\), Jenna \((J)\), Mary \((M)\), Tim \((T)\) and Yoshie \((Y)\). They each must spend one week in each of 5 departments, Delicatessen \((D)\), Frozen foods \((F)\), Groceries \((G)\), Pet foods \((P)\), Soft drinks \((S)\). Next week every department requires exactly one trainee. The table below shows the departments in which the trainees have yet to spend time. Initially \(H\), \(J\), \(M\) and \(T\) are allocated to the first department in their list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. [2] Starting from this matching,
2. use the maximum matching algorithm to find a complete matching. You must make clear your alternating path and your complete matching. [4]

\includegraphics{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.

1. Indicate this initial matching in a distinctive way on the bipartite graph drawn 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 you use. [5]

\includegraphics{figure_1} 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.

1. Explain why it is necessary to perform the maximum matching algorithm twice in order to try to obtain a complete matching. [1]
2. Use the maximum matching algorithm twice to obtain a complete matching. List clearly the alternating paths you use. [6]

\includegraphics{figure_1} \includegraphics{figure_2} Figure 1 shows the possible allocations of five people, Ellen, George, Jo, Lydia and Yi Wen to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.

1. Find an alternating path linking George with 5. List the resulting improved matching this gives. (3)
2. Explain why it is not possible to find a complete matching. (1)

George now has task 2 added to his possible allocation.

1. Using the improved matching found in part (a) as the new initial matching, find an alternating path linking Yi Wen with task 1 to find a complete matching. List the complete matching. (3)

(Total 7 marks)

Six workers \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\) are to be matched to six tasks 1, 2, 3, 4, 5 and 6. The table below shows the tasks that each worker is able to do.

Worker	Tasks
A	2, 3, 5
B	1, 3, 4, 5
C	2
D	3, 6
E	2, 4, 5
F	1

A bipartite graph showing this information is drawn in the answer booklet. Initially, \(A\), \(B\), \(D\) and \(E\) are allocated to tasks 2, 1, 3 and 5 respectively. Starting from the given initial matching, use the matching improvement algorithm to find a complete matching, showing your alternating paths clearly. [5]

The organiser of a sponsored walk wishes to allocate each of six volunteers, Alan, Geoff, Laura, Nicola, Philip and Sam to one of the checkpoints along the route. Two volunteers are needed at checkpoint 1 (the start) and one volunteer at each of checkpoint 2, 3, 4 and 5 (the finish). Each volunteer will be assigned to just one checkpoint. The table shows the checkpoints each volunteer is prepared to supervise. Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. [2]
2. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use. [3]
3. Explain why it is not possible to find a complete matching. [2]