2. Six film critics, Bronwen (B), Greg (G), Jean (J), Mick (M), Renee (R) and Susan (S), must see six films, \(1,2,3,4,5\) and 6 . Each critic must attend a different film and each critic needs to be allocated to exactly one film. The critics are asked which films they would prefer and their preferences are given in the table below.
| Critic | Preference |
| B | \(2,3,6\) |
| G | 1 |
| J | \(2,5,6\) |
| M | 1,5 |
| R | \(2,4,6\) |
| S | 3,5 |
- Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of critics to their preferred films.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-03_616_524_1114_767}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 2 shows an initial matching. - Starting from the given initial matching, apply the maximum matching algorithm to find an alternating path from G to 3 . Hence find an improved matching. You should list the alternating path that you use, and state your improved matching.
(3) - Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You should list the alternating path that you use, and state your complete matching.