| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2018 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Easy -1.2 This is a straightforward application of the maximum matching algorithm with clear step-by-step instructions. Part (a) tests basic definitions (recall), parts (b) and (d) require following a standard algorithm procedure, and part (c) asks for simple observation. The question provides an initial matching and guides students through each step, making it easier than average A-level questions which typically require more independent problem-solving. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A path from an unmatched vertex in one set to an unmatched vertex in the other set which alternately uses arcs not in/in the matching | B2,1,0 | Unmatched to unmatched (vertices need not be explicitly mentioned for B mark but B0 if arcs or sets implied); must mention arcs/edges (not lines); must show understanding of 'alternating' |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A matching where every member of set X is paired with a single member of set Y and vice-versa | B2,1,0 | 'Pairing' or 'one to one' (or 1-1) only; 'all' (oe) and 'set' must be mentioned |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Alternating path: \(F-3=A-5=B-6=D-2=E-1\) | M1 | Alternating path from F to 1 or vice-versa |
| Change status: \(F=3-A=5-B=6-D=2-E=1\) | A1 | Correct path with change status stated or shown |
| Improved matching: \(A=5, B=6, (C=), D=2, E=1, F=3\) | A1 | Must follow from correct stated path; accept on clear diagram (five arcs only) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| e.g. F can only do task 3 so therefore A has to do task 5 as A can only do 5 and 3, and so therefore C has no task as C can only do task 5 | B1 | CAO – one completely correct statement; specific nodes must be referred to |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Alternating path: \(C-1=E-2=D-6=B-4\) | M1 | Alternating path from C to 4 or vice-versa |
| Change status: \(C=1-E=2-D=6-B=4\) | A1 | Correct path with change status stated or shown |
| Complete matching: \(A=5, B=4, C=1, D=6, E=2, F=3\) | A1 | Must follow from two correct stated paths (both previous M marks awarded); accept on clear diagram (six arcs only) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Alternating path \(F-3=A-5=B-4\) and change of status | M1, A1 | |
| Improved matching \(A=5, B=4, D=6, E=2, F=3\) | A1 | Max three marks across (b) and (d) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Alternating path from C to 4 OR C to 1 | M1 | |
| \(C-5=B-4\) OR \(C-5=B-6=D-2=E-1\) with change of status | A1 | |
| A0 | ||
| In (d): \(F-3=A-5=C-1\) following their path | M1 | |
| A0, A0 | Max three marks across (b) and (d) |
# Question 2:
## Part (a)(i):
| Answer | Mark | Guidance |
|--------|------|----------|
| A path from an unmatched vertex in one set to an unmatched vertex in the other set which alternately uses arcs not in/in the matching | B2,1,0 | Unmatched to unmatched (vertices need not be explicitly mentioned for B mark but B0 if arcs or sets implied); must mention arcs/edges (not lines); must show understanding of 'alternating' |
## Part (a)(ii):
| Answer | Mark | Guidance |
|--------|------|----------|
| A matching where every member of set X is paired with a single member of set Y and vice-versa | B2,1,0 | 'Pairing' or 'one to one' (or 1-1) only; 'all' (oe) and 'set' must be mentioned |
## Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Alternating path: $F-3=A-5=B-6=D-2=E-1$ | M1 | Alternating path from F to 1 or vice-versa |
| Change status: $F=3-A=5-B=6-D=2-E=1$ | A1 | Correct path with change status stated or shown |
| Improved matching: $A=5, B=6, (C=), D=2, E=1, F=3$ | A1 | Must follow from correct stated path; accept on clear diagram (five arcs only) |
## Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| e.g. F can only do task 3 so therefore A has to do task 5 as A can only do 5 and 3, and so therefore C has no task as C can only do task 5 | B1 | CAO – one completely correct statement; specific nodes must be referred to |
## Part (d):
| Answer | Mark | Guidance |
|--------|------|----------|
| Alternating path: $C-1=E-2=D-6=B-4$ | M1 | Alternating path from C to 4 or vice-versa |
| Change status: $C=1-E=2-D=6-B=4$ | A1 | Correct path with change status stated or shown |
| Complete matching: $A=5, B=4, C=1, D=6, E=2, F=3$ | A1 | Must follow from two correct stated paths (both previous M marks awarded); accept on clear diagram (six arcs only) |
## Special Cases (b) and (d):
### Alternating path from F to 4:
| Answer | Mark | Guidance |
|--------|------|----------|
| Alternating path $F-3=A-5=B-4$ and change of status | M1, A1 | |
| Improved matching $A=5, B=4, D=6, E=2, F=3$ | A1 | Max three marks across (b) and (d) |
### Alternating path from C to 4 or C to 1:
| Answer | Mark | Guidance |
|--------|------|----------|
| Alternating path from C to 4 OR C to 1 | M1 | |
| $C-5=B-4$ OR $C-5=B-6=D-2=E-1$ with change of status | A1 | |
| | A0 | |
| In (d): $F-3=A-5=C-1$ following their path | M1 | |
| | A0, A0 | Max three marks across (b) and (d) |
---2. (a) Define the terms
\begin{enumerate}[label=(\roman*)]
\item alternating path,
\item complete matching.\\
(4)
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_521_614_450_351}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-03_509_604_456_1098}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
Figure 1 shows the possible allocations of six workers, $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F , to six tasks, $1,2,3,4,5$ and 6. Each task must be assigned to only one worker and each worker must be assigned to exactly one task.
Figure 2 shows an initial matching.\\
(b) Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from F to 1. Hence find an improved matching. You must write down the alternating path used and state your improved matching.\\
(3)\\
(c) Explain why it is not possible to find a complete matching.\\
(1)
Worker C has task 1 added to his possible allocations.\\
(d) Starting from the improved matching found in (b), use the maximum matching algorithm to find a complete matching. You must write down the alternating path used and state your complete matching.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2018 Q2 [11]}}