1.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-02_533_551_365_402}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{1493d74b-e9ef-4c9a-91f6-877c1eaa74e2-02_529_545_365_1098}
\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 the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching.
- Explain why it is not possible to find a complete matching.
After training, task 4 is added to F's possible allocation and task 6 is added to E's possible allocation.
- 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 used and your complete matching.