3.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-04_608_511_242_358}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{8c9bce2c-4156-4bf6-8d02-9e01d6f11948-04_611_510_242_1201}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\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.
\begin{enumerate}[label=(\alph*)]
\item 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.
\item Explain why it is not possible to find a complete matching.

After training, task 1 is added to worker A's possible allocations.
\item 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)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2017 Q3 [7]}}