| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2014 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Complete vs maximal matching definitions |
| Difficulty | Easy -1.3 This question tests pure recall of definitions and mechanical application of a standard algorithm with no problem-solving required. The maximum matching algorithm is a routine procedure taught in D1, and students simply follow the steps to find alternating paths. No insight, proof, or novel reasoning is needed—just memorization and execution. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Complete matching: a matching where every member of set X is paired with a single member of set Y and vice versa | B1 | Must mention pairing/one-to-one |
| Difference: a maximal matching has as large a number of edges as possible without necessarily pairing all vertices; a complete matching pairs all vertices | B1, B1 | Must mention 'all' compared to 'at most' (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Alternating path: \(C - L = A - O\) | M1 | An alternating path from C to O or K (or vice versa) |
| Change status: \(C = L - A = O\) | A1 | Correct path including change of status stated or shown |
| Improved matching: \(A=O,\ B=M,\ C=L,\ E=N,\ F=P\) | A1 | CAO must follow from correct stated path (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Alternating path: \(D - M = B - K\) | M1 | Alternating path from D to K or O (whichever not used in (b)) |
| Change status: \(D = M - B = K\) | A1 | Correct path including change of status stated or shown |
| Complete matching: \(A=O,\ B=K,\ C=L,\ D=M,\ E=N,\ F=P\) | A1 | CAO must follow from two correct stated paths (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Path 1 | Path 2 | A |
| C-L-A-O | D-M-B-K | O |
| C-L-A-O | D-N-E-K | O |
| C-L-A-K | D-M-B-K-A-O | O |
| C-L-A-K | D-N-E-K-A-O | O |
# Question 2:
## Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Complete matching: a matching where **every** member of set X is paired with a single member of set Y and vice versa | B1 | Must mention pairing/one-to-one |
| Difference: a maximal matching has as **large** a number of edges as possible without necessarily pairing all vertices; a complete matching pairs **all** vertices | B1, B1 | Must mention 'all' compared to 'at most' **(3)** |
## Part (b)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Alternating path: $C - L = A - O$ | M1 | An alternating path from C to O or K (or vice versa) |
| Change status: $C = L - A = O$ | A1 | Correct path including change of status stated **or** shown |
| Improved matching: $A=O,\ B=M,\ C=L,\ E=N,\ F=P$ | A1 | CAO must follow from correct stated path **(3)** |
## Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Alternating path: $D - M = B - K$ | M1 | Alternating path from D to K or O (whichever not used in (b)) |
| Change status: $D = M - B = K$ | A1 | Correct path including change of status stated **or** shown |
| Complete matching: $A=O,\ B=K,\ C=L,\ D=M,\ E=N,\ F=P$ | A1 | CAO must follow from two correct stated paths **(3)** |
**Valid complete matchings:**
| Path 1 | Path 2 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| C-L-A-O | D-M-B-K | O | K | L | M | N | P |
| C-L-A-O | D-N-E-K | O | M | L | N | K | P |
| C-L-A-K | D-M-B-K-A-O | O | K | L | M | N | P |
| C-L-A-K | D-N-E-K-A-O | O | M | L | N | K | P |
---2. (a) (i) Define the term complete matching.\\
(ii) Explain the difference between a complete matching and a maximal matching.\\
(3)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-3_732_563_434_376}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4609ffb5-d270-4ff3-aa44-af8442a38b66-3_739_563_429_1117}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of dancing partners for the Truly Come Ballroom dancing competition. Six women, Annie (A), Bella (B), Chloe (C), Danika (D), Ella (E) and Faith (F), are to be paired with six men, Kieran (K), Lucas (L), Michael (M), Nasir (N), Oliver (O) and Paul (P).
Figure 2 shows an initial matching.\\
(b) Use the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and list your improved matching.\\
(3)
After dance practice, it is decided that Bella could also be paired with Kieran, and Danika could also be paired with Nasir.\\
(c) Starting with your improved matching from part (b), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and list your final matching.\\
\hfill \mbox{\textit{Edexcel D1 2014 Q2 [9]}}