complete matching.
(4)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_521_614_450_351}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_509_604_456_1098}
\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.
(b) Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from F to 1. Hence find an improved matching. You must write down the alternating path used and state your improved matching.
(3)
(c) Explain why it is not possible to find a complete matching.
(1)
Worker C has task 1 added to his possible allocations.
(d) Starting from the improved matching found in (b), use the maximum matching algorithm to find a complete matching. You must write down the alternating path used and state your complete matching.