- The organiser of a sponsored walk wishes to allocate each of six volunteers, Alan, Geoff, Laura, Nicola, Philip and Sam to one of the checkpoints along the route. Two volunteers are needed at checkpoint 1 (the start) and one volunteer at each of checkpoint 2, 3, 4 and 5 (the finish). Each volunteer will be assigned to just one checkpoint. The table shows the checkpoints each volunteer is prepared to supervise.
| Name | Checkpoints |
| Alan | 1 or 3 |
| Geoff | 1 or 5 |
| Laura | 2,1 or 4 |
| Nicola | 5 |
| Philip | 2 or 5 |
| Sam | 2 |
Initially Alan, Geoff, Laura and Nicola are assigned to the first checkpoint in their individual list.
- Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
- Starting from this initial matching, use the maximum matching algorithm to find an improved matching. Clearly list any alternating paths you use.
- Explain why it is not possible to find a complete matching.
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 1}
\includegraphics[alt={},max width=\textwidth]{f4258313-53d5-4a88-abf9-c0c7926770e4-3_572_1600_340_276}
\end{figure}
Figure 1 shows a network of roads. The number on each edge gives the time, in minutes, to travel along that road. Avinash wishes to travel from \(S\) to \(T\) as quickly as possible. - Use Dijkstra's algorithm to find the shortest time to travel from \(S\) to \(T\).
(4) - Find a route for Avinash to travel from \(S\) to \(T\) in the shortest time. State, with a reason, whether this route is a unique solution.
On a particular day Avinash must include \(C\) in his route.
- Find a route of minimal time from \(S\) to \(T\) that includes \(C\), and state its time.
(2)
\includegraphics[max width=\textwidth, alt={}, center]{f4258313-53d5-4a88-abf9-c0c7926770e4-4_641_735_294_593} - Describe a practical problem that could be modelled using the network in Fig. 2 and solved using the route inspection algorithm.
- Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
- State whether your answer to part (b) is unique. Give a reason for your answer.
- Find the length of the shortest inspection route that traverses each arc at least once and starts and finishes at the same vertex.
Given that it is permitted to start and finish the inspection at two distinct vertices,
- find which two vertices should be chosen to minimise the length of the route. Give a reason for your answer.