3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-3_743_625_758_269}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{bd6edbd4-1ec0-4c7e-bd39-b88f96bf52fb-3_746_608_758_1142}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
Figure 2 shows the possible allocations of six workers, Charlie (C), George (G), Jack (J), Nurry (N), Olivia (O) and Rachel (R), to six tasks, \(1,2,3,4,5\) and 6.
Figure 3 shows an initial matching.
- Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should give the alternating path you use and list your improved matching.
- Explain why it is not possible to find a complete matching.
After training, Charlie adds task 5 to his possible allocations.
- Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. Give the alternating path you use and list your complete matching.