2. At Tesafe supermarket there are 5 trainee staff, Homan \(( H )\), Jenna \(( J )\), Mary \(( M )\), Tim \(( T )\) and Yoshie ( \(Y\) ). They each must spend one week in each of 5 departments, Delicatessen ( \(D\) ), Frozen foods \(( F )\), Groceries \(( G )\), Pet foods \(( P )\), Soft drinks \(( S )\). Next week every department requires exactly one trainee. The table below shows the departments in which the trainees have yet to spend time.
| Trainee | Departments |
| \(H\) | \(D , F , P\) |
| \(J\) | \(G , D , F\) |
| \(M\) | \(S , P , G\) |
| \(T\) | \(F , S , G\) |
| \(Y\) | \(D\) |
Initially \(H , J , M\) and \(T\) are allocated to the first department in their list.
- Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
Starting from this matching,
- use the maximum matching algorithm to find a complete matching. You must make clear your alternating path and your complete matching.
(4)