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.