5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-06_753_616_246_296}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{50925a06-9a9b-4e50-869a-2dce6680615c-06_751_606_248_1169}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.
- Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching.
- Explain why a complete matching is not possible.
After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
- Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching.