Edexcel D1 2019 June — Question 1 7 marks

Exam BoardEdexcel
ModuleD1 (Decision Mathematics 1)
Year2019
SessionJune
Marks7
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicMatchings and Allocation
TypeMaximum matching algorithm application
DifficultyModerate -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.
Spec7.02f Bipartite test: colouring argument7.02r Graph modelling: model and solve problems using graphs

1. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{87f0e571-e708-4ca9-adc7-4ed18e144d32-02_474_501_374_429} \captionsetup{labelformat=empty} \caption{Figure 1}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{87f0e571-e708-4ca9-adc7-4ed18e144d32-02_474_501_374_1133} \captionsetup{labelformat=empty} \caption{Figure 2}
\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
  1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
  2. 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)

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]}}