4.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ef029462-ffed-4cdf-87bc-56c8a13d671f-4_540_626_244_316}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{ef029462-ffed-4cdf-87bc-56c8a13d671f-4_531_613_246_1128}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 2 shows an initial matching.
- Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used, and your improved matching.
- Explain why it is not possible to find a complete matching.
D now has task 2 added to their possible allocation.
- Using the improved matching found in part (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path used and your complete matching.
(3)