Maximum matching algorithm application

4 The Head Teacher of a school is allocating five teachers, Amy ( \(A\) ), Ben ( \(B\) ), Celia ( \(C\) ), Duncan ( \(D\) ), and Erica ( \(E\) ), to the five posts of Head of Year 7, 8, 9, 10 and 11. The five teachers are asked which year(s) they would be willing to take. This information is shown below. Amy is willing to take Year 7 or Year 8 . Ben is willing to take Year 7, Year 8 or Year 10. Celia is willing to take Year 8, Year 9 or Year 11. Duncan will take only Year 9.
Erica will take only Year 11.

1. Show this information on a bipartite graph.
2. Initially the Head Teacher assigns Amy to Year 8, Ben to Year 10, Celia to Year 9 and Erica to Year 11. Demonstrate, by using an alternating path from this initial matching, how each teacher can be matched to a year that they are willing to take.

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. Initially, \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5. From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.

1

1. Draw a bipartite graph representing the following adjacency matrix.

   	1	2	3	4	5	6
   \(\boldsymbol { A }\)	1	0	1	0	1	0
   B	0	1	0	1	0	0
   \(\boldsymbol { C }\)	0	1	0	0	0	1
   \(\boldsymbol { D }\)	0	0	0	1	0	0
   E	0	0	1	0	1	1
   \(\boldsymbol { F }\)	0	0	0	1	1	0

2. Initially, \(A\) is matched to \(3 , B\) is matched to \(4 , C\) is matched to 2 , and \(E\) is matched to 5 . Use the maximum matching algorithm, from this initial matching, to find a complete matching. List your complete matching.
   

1 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 adjacency matrix shows the tasks that each of the people is able to undertake.

1. Represent this information in a bipartite graph.
2. Initially, \(A\) is assigned to task 3, \(B\) to task 2, \(C\) to task 4 and \(D\) to task 5 . Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.

1 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]{1258a6d3-558a-46dc-a916-d71f71b175ff-02_1003_547_740_737}

1. Represent this information in an adjacency matrix.
2. Initially, \(B\) is assigned to task 4, \(C\) to task 3, \(D\) to task 1, \(E\) to task 5 and \(F\) to task 6. By using an algorithm from this initial matching, find a complete matching.
   (3 marks)

1 Six people, Andy, Bob, Colin, Dev, Eric and Faisal, are to be allocated to six tasks, \(1,2,3,4,5\) and 6 . The following table shows the tasks that each person is able to undertake.

1. Represent this information on a bipartite graph.
2. Initially, Bob is allocated to task 1, Colin to task 3, Dev to task 5 and Eric to task 2. Demonstrate, by using an alternating path algorithm from this initial matching, how each person can be allocated to a different task.

4. This question should be answered on the sheet provided. The manager of an outdoor centre must staff each activity offered by the centre with an appropriately qualified instructor. The table below shows the sports for which each member of staff is qualified to supervise.

1. Draw a bipartite graph to model this situation. Initially the manager allocates Fatima, Gavin, Iain and Jane to supervise the first sport listed against their names in the table.
2. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how you have applied the algorithm.
   (6 marks)

4. This question should be answered on the sheet provided. The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.

1. Draw a bipartite graph to model this situation. Initially the Prime Minister matches Minister \(P\) to the post of Chancellor, \(Q\) to Foreign Secretary, \(R\) to Defence and \(T\) to Home Secretary.
2. Draw this initial matching.
3. Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used. Minister \(U\), on reflection, now expresses no interest in becoming Foreign Secretary.
4. Explain why no complete matching is now possible.
   (2 marks)

7 Annie (A), Brigid (B), Carla (C) and Diane ( \(D\) ) are hanging wallpaper in a stairwell. They have broken the job down into four tasks: measuring and cutting the paper ( \(M\) ), pasting the paper ( \(P\) ), hanging and then trimming the top end of the paper ( \(H\) ) and smoothing out the air bubbles and then trimming the lower end of the paper ( \(S\) ). They will each do one of these tasks.

• Annie does not like climbing ladders but she is prepared to do tasks \(M , P\) or \(S\)
• Brigid gets into a mess with paste so she is only able to do tasks \(M\) or \(S\)
• Carla enjoys hanging the paper so she wants to do task \(H\) or task \(S\)
• Diane wants to do task \(H\)

Initially Annie chooses task \(M\), Brigid task \(S\) and Carla task \(H\).

1. Draw a bipartite graph to show the available pairings between the people and the tasks. Write down an alternating path to improve the initial matching and write down the complete matching from your alternating path. Hanging the wallpaper is part of a bigger decorating project. The table lists the activities involved, their durations and precedences.
2. Maximin value \(=\) Route \(=\)

4 Anya \(( A )\), Ben \(( B )\), Connie \(( C )\), Derek \(( D )\) and Emma \(( E )\) work for a local newspaper. The editor wants them each to write a regular weekly article for the paper. The items needed are: problem page \(( P )\), restaurant review \(( R )\), sports news \(( S )\), theatre review \(( T )\) and weather report \(( W )\). Anya wants to write either the problem page or the restaurant review. She is given the problem page. Ben wants the restaurant review, the sports news or the theatre review. The editor gives him the restaurant review. Connie wants either the theatre review or the weather report. The editor gives her the theatre review. Derek wants the problem page, the sports news or the weather report. He is given the weather report. Emma is only interested in writing the problem page but this has already been given to Anya.

1. Draw a bipartite graph to show the possible pairings between the writers ( \(A , B , C , D\) and \(E\) ) and the articles ( \(P , R , S , T\) and \(W\) ). On your bipartite graph, show who has been given which article by the editor.
2. Construct the shortest possible alternating path, starting from Emma, to find a complete matching between the writers and the articles. Write a list showing which article each writer is given with this complete matching. When the writers send in their articles the editor assigns a sub-editor to each one to check it. The sub-editors can check at most one article each. The table shows how long, in minutes, each sub-editor would typically take to check each article.

   \multirow{8}{*}{Sub-editor}	\multirow{2}{*}{}	Article
   		\(P\)	\(R\)	\(S\)	\(T\)	\(W\)
   	Jeremy ( \(J\) )	56	56	51	57	58
   	Kath ( \(K\) )	53	52	53	54	54
   	Laura ( \(L\) )	57	55	52	58	60
   	Mohammed ( \(M\) )	59	55	53	59	57
   	Natalie ( \(N\) )	57	57	53	59	60
   	Ollie ( \(O\) )	58	56	51	56	57

   The editor wants to find the allocation for which the total time spent checking the articles is as short as possible.
3. Apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the sub-editors and the articles. Explain how each table is formed and write a list showing which sub-editor should be assigned to which article. If each minute of sub-editor time costs \(\pounds 0.25\), calculate the total cost of checking the articles each week.

1 Andy ( \(A\) ), Beth ( \(B\) ), Chelsey ( \(C\) ), Dean ( \(D\) ) and Elly ( \(E\) ) have formed a quiz team. They have entered a quiz in which, as well as team questions, each of them must answer individual questions on a specialist topic. The specialist topics could be any of: food \(( F )\), geography \(( G )\), history \(( H )\), politics ( \(P\) ), science ( \(S\) ) and television ( \(T\) ). The team members do not know which five specialist topics will arise in the quiz. Andy wants to answer questions on either food or television; Beth wants to answer questions on geography, history or science; Chelsey wants to answer questions on geography or television; Dean wants to answer questions on politics or television; and Elly wants to answer questions on history or television.

1. Draw a bipartite graph to show the possible pairings between the team members and the specialist topics. In the quiz, the first specialist topic is food, and Andy is chosen to answer the questions. The second specialist topic is geography, and Beth is chosen. The next specialist topic is history, and Elly is chosen. The fourth specialist topic is science. Beth has already answered questions so Dean offers to try this round. The final specialist topic is television, and Chelsey answers these questions.
2. Draw a second bipartite graph to show these pairings, apart from Dean answering the science questions. Write down an alternating path starting from Dean to show that there would have been a better way to choose who answered the questions had the topics been known in advance. Write down which team member would have been chosen for each specialist topic in this case.
3. In a practice, although the other team members were able to choose topics that they wanted, Beth had to answer the questions on television. Write down which topic each team member answered questions on, and which topic did not arise.

1 Four friends, Amir (A), Bex (B), Cerys (C) and Duncan (D), are visiting a bird sanctuary. They have decided that they each will sponsor a different bird. The sanctuary is looking for sponsors for a kite \(( K )\), a lark \(( L )\), a moorhen \(( M )\), a nightjar \(( N )\), and an owl \(( O )\). Amir wants to sponsor the kite, the nightjar or the owl; Bex wants to sponsor the lark, the moorhen or the owl; Cerys wants to sponsor the kite, the lark or the owl; and Duncan wants to sponsor either the lark or the owl.

1. Draw a bipartite graph to show which friend wants to sponsor which birds. Amir chooses to sponsor the kite and Bex chooses the lark. Cerys then chooses the owl and Duncan is left with no bird that he wants.
2. Write down the shortest possible alternating path starting from the nightjar, and hence write down one way in which all four friends could have chosen birds that they wanted to sponsor.
3. List a way in which all four friends could have chosen birds they wanted to sponsor, with the owl not being chosen.

1 Five film studies students need to review five different films for an assignment, but only have one evening left before the assignment is due in. They decide that they will share the work out so that each of them reviews just one film. Jack \(( J )\) wants to review a horror movie; Karen \(( K )\) wants to review an animated film; Lee \(( L )\) wants to review a film that is suitable for family viewing; Mark ( \(M\) ) wants to review an action adventure film and Nikki ( \(N\) ) wants to review anything that is in 3D. The film "Somewhere" ( \(S\) ) has been classified as a horror movie and is being shown in 3D; "Tornado Terror" ( \(T\) ) has been classified as an action adventure film that is suitable for family viewing; "Underwater" \(( U )\) is an animated action adventure film; "Vampires" ( \(V\) ) is an animated horror movie that is suitable for family viewing and "World" ( \(W\) ) is an animated film.

1. Draw a bipartite graph to show which student ( \(J , K , L , M , N\) ) wants to review which films ( \(S , T , U\), \(V , W\) ). Initially Jack says that he will review "Somewhere", Karen then chooses "Underwater" and Lee chooses "Tornado Terror", but this would leave both Mark and Nikki with films that they do not want.
2. Write down the shortest possible alternating path starting from Nikki, and hence write down an improved, but still incomplete, matching.
3. From this incomplete matching, write down the shortest possible alternating path starting from "World", and hence write down a complete matching between the students and the films.
4. Show that this is the only possible complete matching between the students and the films.

1 A TV soap opera has five main characters, Alice ( \(A\) ), Bob ( \(B\) ), Charlie ( \(C\) ), Dylan ( \(D\) ) and Etty ( \(E\) ). A different character is scheduled to play the lead in each of the next five episodes. Alice, Dylan and Etty are all in the episode about the fire ( \(F\) ), but Bob and Charlie are not. Alice and Bob are the only main characters in the episode about the gas leak ( \(G\) ). Alice, Charlie and Etty are the only main characters in the episode about the house break-in (H). The episode about the icy path (I) stars Alice and Charlie only. The episode about the jail break ( \(J\) ) does not star any of the main characters who were in the episodes about the fire or the house break-in.

1. Draw a bipartite graph to show which main characters ( \(A , B , C , D , E\) ) are in which of the next five episodes \(( F , G , H , I , J )\). The writer initially decides to make Alice play the lead in the episode about the fire, Bob in the episode about the gas leak and Charlie in the episode about the house break-in.
2. Write down the shortest possible alternating path starting from Dylan. Hence draw the improved, but still incomplete, matching that results.
3. From this incomplete matching, write down the shortest possible alternating path starting from the character who still has no leading part allocated. Hence draw the complete matching that results.
4. By starting with the episode about the jail break, explain how you know that this is the only possible complete matching between the characters and the episodes.

2 A talent contest has five contestants. In the first round of the contest each contestant must sing a song chosen from a list. No two contestants may sing the same song. Adam (A) chooses to sing either song 1 or song 2; Bex (B) chooses 2 or 4; Chris (C) chooses 3 or 5; Denny (D) chooses 1 or 3; Emma (E) chooses 3 or 4.

1. Draw a bipartite graph to show this information. Put the contestants (A, B, C, D and E) on the left hand side and the songs ( \(1,2,3,4\) and 5 ) on the right hand side. The contest organisers propose to give Adam song 1, Bex song 2 and Chris song 3.
2. Explain why this would not be a satisfactory way to allocate the songs.
3. Construct the shortest possible alternating path that starts from song 5 and brings Denny (D) into the allocation. Hence write down an allocation in which each of the five contestants is given a song that they chose.
4. Find a different allocation in which each of the five contestants is given a song that they chose. Emma is knocked out of the contest after the first round. In the second round the four remaining contestants have to act in a short play. They will each act a different character in the play, chosen from a list of five characters. The table below shows how suitable each contestant is for each character as a score out of 10 (where 0 means that the contestant is completely unsuitable and 10 means that they are perfect to play that character).

   \multirow{2}{*}{}	Character
   	Fire Chief	Gardener	Handyman	Juggler	King
   Adam	4	9	7	0	7
   Bex	6	8	3	8	0
   Chris	7	4	5	2	7
   Denny	6	6	2	7	1

   The Hungarian Algorithm is to be used to find the matching with the greatest total score. Before the Hungarian Algorithm can be used, each score is subtracted from 10 and then a dummy row of zeroes is added at the bottom of the table.
5. Explain why the scores could not be used as given in the table and explain why a dummy row is needed.
6. Apply the Hungarian Algorithm, showing your working carefully, to match the contestants to characters.

1

1. A café sells five different types of filled roll. Mr King buys one of each to take home to his family. The family consists of Mr King's daughter Fiona ( \(F\) ), his mother Gwen ( \(G\) ), his wife Helen ( \(H\) ), his son Jack ( \(J\) ) and Mr King ( \(K\) ). The table shows who likes which rolls.

   		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
   Avocado and bacon	\(( A )\)	\(\checkmark\)		\(\checkmark\)
   Beef and horseradish	\(( B )\)		\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
   Chicken and stuffing	\(( C )\)		\(\checkmark\)		\(\checkmark\)
   Duck and plum sauce	\(( D )\)			\(\checkmark\)		\(\checkmark\)
   Egg and tomato	\(( E )\)	\(\checkmark\)

   1. Draw a bipartite graph to represent this information. Put the fillings ( \(A , B , C , D\) and \(E\) ) on the left-hand side and the members of the family ( \(F , G , H , J\) and \(K\) ) on the right-hand side. Fiona takes the avocado roll; Gwen takes the beef roll; Helen takes the duck roll and Jack takes the chicken roll.
   2. Draw a second bipartite graph to show this incomplete matching.
   3. Construct the shortest possible alternating path from \(E\) to \(K\) and hence find a complete matching. State which roll each family member has with this complete matching.
   4. Find a different complete matching.
2. Mr King decides that the family should eat more fruit. Each family member gives a score out of 10 to five fruits. These scores are subtracted from 10 to give the values below. \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Family member}

   		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
   Lemon	\(L\)	8	8	8	8	1
   Mandarin	\(M\)	4	8	6	4	2
   Nectarine	\(N\)	9	9	9	7	1
   Orange	\(O\)	4	6	5	4	3
   Peach	\(P\)	6	9	7	5	0

   \end{table} The smaller entries in each column correspond to fruits that the family members liked most.
   Mr King buys one of each of these five fruits. Each family member is to be given a fruit.
   Apply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working clearly. Which family member should be given which fruit?

1 Adam, Barbara and their children Charlie, Donna, Edward and Fiona all want cereal for breakfast. The only cereal in the house is a pack of six individual portions of different cereals. The table shows which family members like each of the cereals in the pack.

1. Draw a bipartite graph to represent this information. Adam gives the cornflakes to Fiona, the oatie bits to Edward, the rice pips to Donna, the choco pips to Charlie and the wheat biscs to Barbara. However, this leaves the honey footballs for Adam, 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 6 to \(A\) and hence find a complete matching between the cereals and the family members. Write down which family member is given each cereal with this complete matching.
4. Adam decides that he wants cornflakes. Construct an alternating path starting at \(A\), based on your answer to part (iii) but with Adam being matched to the cornflakes, to find another complete matching. Write down which family member is given each cereal with this matching.

1 The six cadets in Red Team have been told to guard a building through the night, starting at 2200 hours and finishing at 0800 hours the next day. Each will be on duty for either one hour or three hours and will then hand over to the next cadet. The table shows which duty each cadet has offered to take. \begin{table}[h] \end{table}

1. Draw a bipartite graph to represent this information. Amir suggests that he should take the 2200 duty, hand over to Becca at 0100 , she can hand over to Chris at 0200 , and Dan can take the 0400 duty. However, this leaves Emma and Finn to cover the 0300 and 0500 duties, and neither of them wants either of these.
2. Write down the shortest possible alternating path starting at the 0500 duty and hence write down an improved but still incomplete matching between the cadets and the duties.
3. Augment this second incomplete matching by writing down a shortest possible alternating path, this time starting from one of the cadets, to form a complete matching between the cadets and the duties. Write down which cadet should take which duty.

1 Six students are choosing their tokens for a board game. The bipartite graph in Fig. 1 shows which token each student is prepared to have. \begin{figure}[h] \end{figure} Initially Ezra takes the flat iron, Jonah the old boot, Lily the racing car and Molly the scottie dog. This leaves Adele and Noah with tokens that they do not want. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at A and finishes at either B or T . Hence write down a matching that only excludes Noah and one of the tokens.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at N and finishes at whichever of B and T has still not been taken. Hence write down a complete matching between the students and the tokens.
3. By starting at B on Fig. 1, show that there are exactly two complete matchings between the students and the tokens.

1 The infamous fictional detective Agatha Parrot is working on a case and decides to invite each of the four suspects to visit her for tea. She will invite one suspect to tea on Sunday (S), another on Monday (M), another on Tuesday (T) and the final suspect on Wednesday (W).

• Beryl Batty (B) could come to tea on Sunday or Monday but she is away for a few days after that.
• Colonel Chapman (C) could come to tea on Sunday or Tuesday, but is busy on the other days.
• Dimitri Delacruz (D) could only come to tea on Monday or Wednesday.
• Erina El-Sayed (E) could come to tea on Sunday, Monday or Tuesday, but will be away on Wednesday.
  1. Draw a bipartite graph to show which suspects could come to tea on which day.

Agatha initially intended to invite Beryl to tea on Sunday, Dimitri on Monday and Colonel Chapman on Tuesday. However this would mean that Erina would not be able to come to tea, as she will be away on Wednesday.

Draw a second bipartite graph to show this incomplete matching.

Working from this incomplete matching, find the shortest possible alternating path, starting at Erina, to achieve a breakthrough. Write down which suspect is invited on which day with this matching. Before issuing invitations, Agatha overhears Erina making arrangements to go to tea with the vicar one day. She knows that Erina will not want to accept two invitations to tea on the same day. Unfortunately, Agatha does not know which day Erina has arranged to go to tea with the vicar, other than that it was not Sunday. Agatha invites Erina to tea on Sunday and the others when she can. After having tea with all four suspects she considers what they have said and invites them all back on Friday. She then accuses the person who came to tea on Monday of being guilty.

Who does Agatha accuse of being guilty?

1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable. \begin{figure}[h] \end{figure} Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
3. Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.

1 [Answer this question on the insert provided.]
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.

• Arthur wants to use lavender, orange or tangerine.
• Bridget wants to use lavender, mauve or pink.
• Carlos wants to use pink or scarlet.
• Davinder wants to use mauve or pink.
• Eric wants to use lavender or orange.
• Ffion wants to use mauve.

Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.

1. Draw a bipartite graph on the insert, showing which neighbours ( \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.
2. By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
3. Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Amrit (A), Bernard (B), Cameron (C), David (D), Emily (E) and Francis (F), to six tasks, 1, 2, 3, 4, 5 and 6

1. Explain why it is not possible to find a complete matching. Figure 2 shows an initial matching. Starting from this initial matching,
2. find the two alternating paths that start at C .
3. List the two improved matchings generated by using the two alternating paths found in (b). After training, task 5 is added to Bernard's possible allocation.
   Starting from either of the two improved matchings found in (c),
4. use the maximum matching algorithm to obtain a complete matching. You must list the additional alternating path that you use, and state the complete matching.
   (3)

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \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. 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 state your improved matching.
2. Explain why it is not possible to find a complete matching. Now, exactly one worker may be trained so that a complete matching becomes possible.
   Either worker A can be trained to do task 1 or worker E can be trained to do task 4.
3. Decide which worker, A or E , should be trained. Give a reason for your answer. You may now assume that the worker you identified in (c) has been trained.
4. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You must list the alternating path used 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, \(\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.

1. Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from A to 4 . Hence find an improved matching. You should list the alternating path you use, and state your improved matching.
2. Explain why it is not possible to find a complete matching. After training, task 1 is added to worker A's possible allocations.
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 use, and state your complete matching.
   (3)