Edexcel D1 — Question 4

Exam BoardEdexcel
ModuleD1 (Decision Mathematics 1)
PaperDownload PDF ↗
TopicMatchings and Allocation
TypeBipartite graph definition or properties
DifficultyModerate -0.5 This is a standard textbook application of bipartite matching with alternating paths. While it requires understanding the algorithm, the question provides explicit step-by-step guidance (draw graph, find specific alternating path from C, find another path), making it more routine than problem-solving. The small size (5 workers, 5 days) keeps complexity manageable, placing it slightly below average difficulty.
Spec7.02b Graph terminology: tree, simple, connected, simply connected7.02e Bipartite graphs: K_{m,n} notation
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: 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.
  1. 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)
  2. Obtain an alternating path, starting at \(C\), and use this to improve the initial matching.
    (3 marks)
  3. Find another alternating path and hence obtain a complete matching.
    (3 marks)
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:

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  Q4}}
This paper (4 questions)
View full paper
Q4 Q5 Q6 Q7