2.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{23cc3c59-35d8-4120-9965-952c0ced5b3d-3_437_399_251_511}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{23cc3c59-35d8-4120-9965-952c0ced5b3d-3_437_401_251_1151}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 1 shows the possible allocations of five employees, Ali (A), Campbell (C), Hugo (H), Janelle (J) and Polly (P), to five tasks 1, 2, 3, 4 and 5.
- Explain why it is not possible to find a complete matching.
It is decided that one of the employees should be trained so that a complete matching becomes possible. There are only enough funds for one employee to be trained.
Two employees volunteer to undergo training. Janelle can be trained to do task 1 or Hugo can be trained to do task 5.
- Decide which employee, Janelle or Hugo, should undergo training. Give a reason for your answer.
You may now assume that the employee you identified in (b) has successfully undergone training.
Figure 2 shows an initial matching.
- Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state the complete matching.