3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-04_604_506_239_406}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{39bbf9e2-efa7-4f3e-a22d-227f83184abd-04_608_511_242_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 1 shows the possible allocations of six workers, Andrea (A), Baasim (B), Charlie (C), Deirdre (D), Ean (E) and Fen-Fang (F), to six tasks, 1, 2, 3, 4, 5 and 6.
- Write down the technical name given to the type of graph shown in Figure 1.
(1)
Figure 2 shows an initial matching. - Starting from the initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path you used and state your complete matching.
- State a different complete matching from the one found in (b).
- By considering the workers who must be allocated to particular tasks, explain why there are exactly two different complete matchings.