| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2005 |
| Session | June |
| Marks | 8 |
| 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 bipartite graphs. Part (a) requires mechanical execution of finding alternating paths from the initial matching (routine D1 procedure), and part (b) asks for a simple explanation about why a constraint prevents a complete matching. The question involves no novel problem-solving—just direct application of a well-practiced algorithm with straightforward reasoning. |
| Spec | 7.02l Planar graphs: planarity, subdivision, contraction7.02n Kuratowski's theorem: K_5 and K_{3,3} subdivisions |
| Answer | Marks | Guidance |
|---|---|---|
| \(E - 4 = B - 2 = D - 1 = A - 3 = C - 5\) choose states to give matching: \(A = 3, B = 2, C = 5, D = 1, E = 4\) | M1, A1 | |
| \(E - 4 = B - 2 = D - 3 = C - 5\) choose states to give matching: \(A = 1, B = 2, C = 5, D = 3, E = 4\) | M1, A1 |
| Answer | Marks | Guidance |
|---|---|---|
| e.g. Reference to \(B + E\) and \(4 + 2\) | B2, 1, 0 |
| Answer | Marks |
|---|---|
| @5(b) M1 | 1st path E to S |
| A1 | c.a.o + c.s. |
| A1 | matching c.a.o must be clear, must ∧ |
| M1 | 2nd path E to S |
| A1 | c.a.o + c.s. (does not penalise [ones) |
| A1 | matching c.a.o must be clear, must ∧ |
| B2 | full clear explanation B, E, 2 and L listed. (+0) o.e – list of alternatives |
| B1 | Pallid 3 and 4 reject L, may be explanation confused, superflauo filmy or omg ineffective. 'b.o.ad get B1' |
## Part (a)
| $E - 4 = B - 2 = D - 1 = A - 3 = C - 5$ choose states to give matching: $A = 3, B = 2, C = 5, D = 1, E = 4$ | M1, A1 | |
| $E - 4 = B - 2 = D - 3 = C - 5$ choose states to give matching: $A = 1, B = 2, C = 5, D = 3, E = 4$ | | M1, A1 |
## Part (b)
| e.g. Reference to $B + E$ and $4 + 2$ | | B2, 1, 0 |
### Notes
| **@5(b) M1** | 1st path E to S | | |
| **A1** | c.a.o + c.s. | | |
| **A1** | matching c.a.o must be clear, must ∧ | | |
| **M1** | 2nd path E to S | | |
| **A1** | c.a.o + c.s. (does not penalise [ones) | | |
| **A1** | matching c.a.o must be clear, must ∧ | | |
| **B2** | full clear explanation B, E, 2 and L listed. (+0) o.e – list of alternatives | | |
| **B1** | Pallid 3 and 4 reject L, may be explanation confused, superflauo filmy or omg ineffective. 'b.o.ad get B1' | | |
---\includegraphics{figure_3}
\includegraphics{figure_4}
A film critic, Verity, must see five films A, B, C, D and E over two days.
The films are being shown at five special critics' preview times:
\begin{align}
1 &\text{ (Monday 4 pm),}\\
2 &\text{ (Monday 7 pm),}\\
3 &\text{ (Tuesday 1 pm),}\\
4 &\text{ (Tuesday 4 pm),}\\
5 &\text{ (Tuesday 7 pm).}
\end{align}
The bipartite graph in Figure 3 shows the times at which each film is showing.
Initially Verity intends to see
\begin{align}
&\text{Film A on Monday at 4 pm,}\\
&\text{Film B on Tuesday at 4 pm,}\\
&\text{Film C on Tuesday at 1 pm,}\\
&\text{Film D on Monday at 7 pm.}
\end{align}
This initial matching is shown in Figure 4.
Using the maximum matching algorithm and the given initial matching,
\begin{enumerate}[label=(\alph*)]
\item find two distinct alternating paths and complete the matchings they give. [6]
\end{enumerate}
Verity's son is very keen to see film D, but he can only go with his mother to the showing on Monday at 7 pm.
\begin{enumerate}[label=(\alph*)]
\setcounter{enumi}{1}
\item Explain why it will not be possible for Verity to take her son to this showing and still see all five films herself. [2]
\end{enumerate}
(Total 8 marks)
\hfill \mbox{\textit{Edexcel D1 2005 Q5 [8]}}