2. (a) (i) Define the term complete matching.
(ii) Explain the difference between a complete matching and a maximal matching.
(3)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-3_732_563_434_376}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-3_739_563_429_1117}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 1 shows the possible allocations of dancing partners for the Truly Come Ballroom dancing competition. Six women, Annie (A), Bella (B), Chloe (C), Danika (D), Ella (E) and Faith (F), are to be paired with six men, Kieran (K), Lucas (L), Michael (M), Nasir (N), Oliver (O) and Paul (P).
Figure 2 shows an initial matching.
(b) Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and list your improved matching.
(3)
After dance practice, it is decided that Bella could also be paired with Kieran, and Danika could also be paired with Nasir.
(c) Starting with your improved matching from part (b), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and list your final matching.