| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2001 |
| Session | January |
| 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 bipartite matching with alternating paths. The question provides explicit step-by-step guidance (draw graph, find specific alternating path starting at C, find another path), requiring only routine application of the matching algorithm with no problem-solving insight or novel reasoning needed. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| (a) | B1 | Diagram showing matching between days {A, B, C, D, E} and {Monday, Tuesday, Wednesday, Thursday, Friday} |
| B1(2) | ||
| (b) | M1 A1 | From \(C - M = A - W = B - F\) (break through), changing status gives \(C = M - A = W - B - F\) |
| A1(3) | Matching now: \(D = \text{Th}, C = M, A = W, B = F\) | |
| (c) | M1 A1 | From \(E - \text{Th} = D - \text{Tu}\), changing status gives \(E = \text{Th} - D = \text{Tu}\) |
| A1(3) | So complete matching is \(A = W, B = F, C = M, D = \text{Tu}, E = \text{Th}\) |
(a) | B1 | Diagram showing matching between days {A, B, C, D, E} and {Monday, Tuesday, Wednesday, Thursday, Friday} |
| B1(2) | |
(b) | M1 A1 | From $C - M = A - W = B - F$ (break through), changing status gives $C = M - A = W - B - F$ |
| A1(3) | Matching now: $D = \text{Th}, C = M, A = W, B = F$ |
(c) | M1 A1 | From $E - \text{Th} = D - \text{Tu}$, changing status gives $E = \text{Th} - D = \text{Tu}$ |
| A1(3) | So complete matching is $A = W, B = F, C = M, D = \text{Tu}, E = \text{Th}$ |
---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:
Mr. Ahmed (A) -- Monday and Wednesday;
Miss Brown (B) -- Monday, Wednesday and Friday;
Ms. Clough (C) -- Monday;
Mr. Dingle (D) -- Tuesday, Wednesday and Thursday;
Mrs. Evans (E) -- Wednesday and Thursday.
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. [3 marks]
\item Find another alternating path and hence obtain a complete matching. [3 marks]
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2001 Q4 [8]}}