5.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5fa867a2-0a3d-4f0b-9f9c-15584f2be5c0-06_730_597_269_315}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5fa867a2-0a3d-4f0b-9f9c-15584f2be5c0-06_722_583_274_1160}
\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.