| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2019 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.8 This is a standard textbook application of the maximum matching algorithm in D1. Students follow a prescribed algorithm with clear steps (finding alternating paths, updating matchings) on a straightforward bipartite graph. The question requires methodical execution rather than problem-solving insight, making it easier than average A-level maths questions. |
| Spec | 7.02f Bipartite test: colouring argument7.02r Graph modelling: model and solve problems using graphs |
1.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{87f0e571-e708-4ca9-adc7-4ed18e144d32-02_474_501_374_429}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{87f0e571-e708-4ca9-adc7-4ed18e144d32-02_474_501_374_1133}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\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
\begin{enumerate}[label=(\alph*)]
\item Write down the technical name given to the type of diagram shown in Figure 1.
Figure 2 shows an initial matching.
\item Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use and state your improved matching after each iteration.\\
(6)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2019 Q1 [7]}}