1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-2_741_558_370_372}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{a3ca2743-2311-4225-8b78-dcd5eb592704-2_734_561_374_1114}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{figure}
Figure 1 shows the possible allocations of six workers, \(\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 state your improved matching.
- Explain why it is not possible to find a complete matching.
Now, exactly one worker may be trained so that a complete matching becomes possible.
Either worker A can be trained to do task 1 or worker E can be trained to do task 4. - Decide which worker, A or E , should be trained. Give a reason for your answer.
You may now assume that the worker you identified in (c) has been trained.
- Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You must list the alternating path used and state your complete matching.