4.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-4_549_586_285_356}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{552f3296-ad61-448b-8168-6709fb359fa2-4_545_583_287_1128}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}

Six airline pilots, Alice, Dan, Miya, Phil, Sophie and Tom, are to be assigned to six flights, 1, 2, 3, 4, 5 and 6. A bipartite graph showing the possible allocations is shown in Figure 2, and an initial matching is given in Figure 3.

The maximum matching algorithm will be used to obtain a complete matching.
\begin{enumerate}[label=(\alph*)]
\item Starting from A, find an alternating path that leads to an improved matching and list the improved matching that it gives.\\
(3)
\item Using the improved matching found in part (a) as the new initial matching, find a complete matching. You must state any alternating paths you use and list your final complete matching.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1  Q4 [8]}}