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.
\begin{enumerate}[label=(\alph*)]
\item 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.
\item Show this initial matching on Diagram 2 in the answer book.
\item 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.
\item 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.
\item 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.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2014 Q4 [9]}}