| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | November |
| Marks | 6 |
| 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 (likely the Hungarian algorithm or alternating path method) on a small bipartite graph. The question provides an initial matching and asks students to apply a well-defined algorithm they've learned, requiring only methodical execution of the procedure rather than problem-solving insight or novel reasoning. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation7.02f Bipartite test: colouring argument |
| Answer | Marks | Guidance |
|---|---|---|
| Add A to 3, B to 4, C to 1 and F to 5 in a distinctive way | B1 | (1 mark total) |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. \(D-3=A-1=C-4=B-2\) | M1 | |
| C.S. \(D=3-A=1-C=4-B=2\) | A1 | (2) |
| \(E-5=F-6\) | M1 | |
| C.S. \(E=5-F=6\) | A1 | |
| \(A=1 \quad B=2 \quad C=4 \quad D=3 \quad E=5 \quad F=6\) | A1 | (3) |
# Question 3:
## Part (a)
Add A to 3, B to 4, C to 1 and F to 5 in a distinctive way | B1 | (1 mark total)
## Part (b)
e.g. $D-3=A-1=C-4=B-2$ | M1 |
C.S. $D=3-A=1-C=4-B=2$ | A1 | (2)
$E-5=F-6$ | M1 |
C.S. $E=5-F=6$ | A1 |
$A=1 \quad B=2 \quad C=4 \quad D=3 \quad E=5 \quad F=6$ | A1 | (3)
**Total: 6 marks**
---3.
\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\includegraphics[alt={},max width=\textwidth]{75ea31c7-11e7-4dd9-9312-4cf32bba622b-04_1488_677_342_612}
\end{center}
\end{figure}
The bipartite graph in Fig. 2 shows the possible allocations of people $A , B , C , D , E$ and $F$ to tasks $1,2,3,4,5$ and 6.
An initial matching is obtained by matching the following pairs
$A$ to $3 , \quad B$ to $4 , \quad C$ to $1 , \quad F$ to 5 .
\begin{enumerate}[label=(\alph*)]
\item Show this matching in a distinctive way on the diagram in the answer book.
\item Use an appropriate algorithm to find a maximal matching. You should state any alternating paths you have used.\\
(5)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q3 [6]}}