1.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-2_536_476_319_434}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{ba22b22e-c0d5-438d-821b-88619eacdb5d-2_536_474_319_1146}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}

A delivery firm has six vans, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F , available for six deliveries, $1,2,3,4,5$ and 6 . Each van must be assigned to just one delivery.

The bipartite graph shown in Figure 1 shows the possible matchings and Figure 2 shows an initial matching.

A complete matching is required, starting from the given initial matching.
\begin{enumerate}[label=(\alph*)]
\item Explain why it is necessary to use the maximum matching algorithm twice.

There are three possible alternating paths that start at either D or B . One of these is

$$D - 2 = A - 3 = F - 6 = E - 5$$
\item Find the other two alternating paths.
\item List the improved matching generated by using the alternating path

$$D - 2 = A - 3 = F - 6 = E - 5$$
\item Starting from the improved matching found in (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use and your complete matching.
\end{enumerate}

\hfill \mbox{\textit{Edexcel D1 2015 Q1 [6]}}