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.