AQA D1 2007 January — Question 2

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2007
SessionJanuary
TopicMatchings and Allocation

2 Five people \(A , B , C , D\) and \(E\) are to be matched to five tasks \(R , S , T , U\) and \(V\).
The table shows the tasks that each person is able to undertake.
PersonTasks
\(A\)\(R , V\)
\(B\)\(R , T\)
\(C\)\(T , V\)
\(D\)\(U , V\)
\(E\)\(S , U\)
  1. Show this information on a bipartite graph.
  2. Initially, \(A\) is matched to task \(V , B\) to task \(R , C\) to task \(T\), and \(E\) to task \(U\). Demonstrate, by using an alternating path from this initial matching, how each person can be matched to a task.