Easy -1.2 This is a straightforward application of a standard D1 algorithm with clear step-by-step instructions. Part (a) requires simple recall of definitions (4 marks), while parts (b) and (c) involve mechanical application of the maximum matching algorithm following a prescribed method. The question provides the initial matching and explicitly tells students what to find, requiring no problem-solving insight or novel approach—just careful execution of a learned procedure.
\end{figure}
At a hotel, six guests, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , are to be allocated to six rooms, \(1,2,3,4,5\) and 6 . Each room needs to be allocated to exactly one guest.
A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.
(b) Starting from the initial matching given in Figure 2, apply the maximum matching algorithm to find an alternating path from F to 5 . Hence find an improved matching. You must list the alternating path that you use and state your improved matching.
(3)
Guest C now has room 5 added to his possible allocations.
(c) Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You must list the alternating path that you use and state your complete matching.
\begin{enumerate}
\item (a) Define the terms\\
(i) bipartite graph,\\
(ii) alternating path.\\
(4)
\end{enumerate}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-02_624_526_653_347}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{65fb7699-4301-47d2-995d-713ee33020c8-02_611_519_662_1192}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
At a hotel, six guests, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F , are to be allocated to six rooms, $1,2,3,4,5$ and 6 . Each room needs to be allocated to exactly one guest.
A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.\\
(b) Starting from the initial matching given in Figure 2, apply the maximum matching algorithm to find an alternating path from F to 5 . Hence find an improved matching. You must list the alternating path that you use and state your improved matching.\\
(3)
Guest C now has room 5 added to his possible allocations.\\
(c) Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You must list the alternating path that you use and state your complete matching.\\
\hfill \mbox{\textit{Edexcel D1 2017 Q1 [10]}}