3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-04_608_511_242_358}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-04_611_510_242_1201}
\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. Each task must be assigned to only one worker and each worker must be assigned to exactly one task.
Figure 2 shows an initial matching.
- Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from A to 4 . Hence find an improved matching. You should list the alternating path you use, and state your improved matching.
- Explain why it is not possible to find a complete matching.
After training, task 1 is added to worker A's possible allocations.
- Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use, and state your complete matching.
(3)