| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Maximum matching algorithm application |
| Difficulty | Moderate -0.5 This is a standard textbook application of the alternating path algorithm for maximum matching in bipartite graphs. The setup is straightforward, the alternating paths are relatively easy to identify (C is only available Monday, forcing a clear path), and the question guides students through the process step-by-step. While it requires understanding of the algorithm, it involves minimal problem-solving beyond mechanical application of a taught procedure. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02e Bipartite graphs: K_{m,n} notation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Each arc contributes 1 to the orders of two nodes, so sum of orders = \(2 \times\) (number of arcs) | B1 | Must clearly link order of nodes to arcs |
| Sum of orders is even, therefore there must be an even number of vertices of odd order; cannot have an odd number of vertices of odd order | B1 | Must state sum of nodes is even together with correct conclusion |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Start at D, end at E (or vice versa) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(A(C)B + D(BC)E = 120 + 300 = 420\) | M1 | Three distinct pairings of the correct four odd nodes |
| \(A(CB)D + B(C)E = 290 + 130 = 420\) | A1 | Any two rows correct including pairings and totals |
| \(A(C)E + BD = 150 + 170 = 320^*\) | A1 | All three rows correct including pairings and totals |
| Repeat arcs AC, CE and BD | A1 | CAO — arcs clearly stated (not just in working) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Length \(= 2090 + 320 + 130 = 2540\) m | M1, A1 | CAO (2540); correct answer implies both marks |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Finishing point is D | B1 | CAO |
| Difference \(= 2540 - (2090 + 130 + 130) = 190\) m | M1, A1 | CAO (190) — condone lack of units |
# Question 4:
## Part (a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Each arc contributes 1 to the orders of two nodes, so sum of orders = $2 \times$ (number of arcs) | B1 | Must clearly link order of nodes to arcs |
| Sum of orders is even, therefore there must be an even number of vertices of odd order; cannot have an odd number of vertices of odd order | B1 | Must state sum of nodes is even together with correct conclusion |
## Part (b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Start at D, end at E (or vice versa) | B1 | |
## Part (c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $A(C)B + D(BC)E = 120 + 300 = 420$ | M1 | Three distinct pairings of the correct four odd nodes |
| $A(CB)D + B(C)E = 290 + 130 = 420$ | A1 | Any two rows correct including pairings **and** totals |
| $A(C)E + BD = 150 + 170 = 320^*$ | A1 | All three rows correct including pairings **and** totals |
| Repeat arcs AC, CE and BD | A1 | CAO — arcs clearly stated (not just in working) |
## Part (d):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Length $= 2090 + 320 + 130 = 2540$ m | M1, A1 | CAO (2540); correct answer implies both marks |
## Part (e):
| Answer | Marks | Guidance |
|--------|-------|----------|
| Finishing point is D | B1 | CAO |
| Difference $= 2540 - (2090 + 130 + 130) = 190$ m | M1, A1 | CAO (190) — condone lack of units |
---4. This question should be answered on the sheet provided in the answer booklet.
A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings:
$$\begin{aligned}
& \text { Mr. Ahmed } ( A ) \text { - Monday and Wednesday; } \\
& \text { Miss Brown } ( B ) \text { - Monday, Wednesday and Friday; } \\
& \text { Ms. Clough } ( C ) \text { - Monday; } \\
& \text { Mr. Dingle } ( D ) \text { - Tuesday, Wednesday and Thursday; } \\
& \text { Mrs. Evans } ( E ) \text { - Wednesday and Thursday. }
\end{aligned}$$
The manager initially suggests that $A$ might work on Monday, $B$ on Wednesday and $D$ on Thursday.
\begin{enumerate}[label=(\alph*)]
\item Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion.\\
(2 marks)
\item Obtain an alternating path, starting at $C$, and use this to improve the initial matching.
\item Find another alternating path and hence obtain a complete matching.\\
(3 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q4}}