10. & Verity
\end{tabular} \end{center} 2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of five people, Ellen, George, Jo, Lydia and Yi Wen to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.

1. Find an alternating path linking George with 5. List the resulting improved matching this gives.
2. Explain why it is not possible to find a complete matching. George now has task 2 added to his possible allocation.
3. Using the improved matching found in part (a) as the new initial matching, find an alternating path linking Yi Wen with task 1 to find a complete matching. List the complete matching.
   3. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-04_586_1417_205_317} \captionsetup{labelformat=empty} \caption{Figure 3}
   \end{figure} The network in Figure 3 shows the distances, in metres, between 10 wildlife observation points. The observation points are to be linked by footpaths, to form a network along the arcs indicated, using the least possible total length.
4. Find a minimum spanning tree for the network in Figure 3, showing clearly the order in which you selected the arcs for your tree, using
   1. Kruskal's algorithm,
   2. Prim's algorithm, starting from \(A\). Given that footpaths are already in place along \(A B\) and \(F I\) and so should be included in the spanning tree,
5. explain which algorithm you would choose to complete the tree, and how it should be adapted. (You do not need to find the tree.)
   4. \(\quad \begin{array} { l l l l l l l l l l } 650 & 431 & 245 & 643 & 455 & 134 & 710 & 234 & 162 & 452 \end{array}\)
6. The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.
7. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.)
8. Determine whether your solution to part (b) is optimal. Give a reason for your answer.
   5. (a) Explain why a network cannot have an odd number of vertices of odd degree. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-06_615_1143_338_461} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at \(A\). He wishes to minimise the total distance he walks.
9. Use the route inspection algorithm to find which paths, if any, need to be traversed twice.
10. Find the length of Hamish's route.
    [0pt] [The total weight of the network in Figure 4 is 4180 m .]
    (1)
    6. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-07_627_1408_223_331} \captionsetup{labelformat=empty} \caption{Figure 5}
    \end{figure} Figure 5 shows a network of roads. The number on each arc represents the length of that road in km .
11. Use Dijkstra's algorithm to find the shortest route from \(A\) to \(J\). State your shortest route and its length.
12. Explain how you determined the shortest route from your labelled diagram. The road from \(C\) to \(F\) will be closed next week for repairs.
13. Find a shortest route from \(A\) to \(J\) that does not include \(C F\) and state its length.
    7. \begin{figure}[h]
    \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-08_1501_1650_201_210} \captionsetup{labelformat=empty} \caption{Figure 6}
    \end{figure} The captain of the Malde Mare takes passengers on trips across the lake in her boat.
    The number of children is represented by \(x\) and the number of adults by \(y\). Two of the constraints limiting the number of people she can take on each trip are $$x < 10$$ and $$2 \leqslant y \leqslant 10$$ These are shown on the graph in Figure 6, where the rejected regions are shaded out.
14. Explain why the line \(x = 10\) is shown as a dotted line.
15. Use the constraints to write down statements that describe the number of children and the number of adults that can be taken on each trip.
    (3) For each trip she charges \(\pounds 2\) per child and \(\pounds 3\) per adult. She must take at least \(\pounds 24\) per trip to cover costs. The number of children must not exceed twice the number of adults.
16. Use this information to write down two inequalities.
    (2)
17. Add two lines and shading to Diagram 1 in your answer book to represent these inequalities. Hence determine the feasible region and label it R .
    (4)
18. Use your graph to determine how many children and adults would be on the trip if the captain takes:
    1. the minimum number of passengers,
    2. the maximum number of passengers.
       8. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{0f22a56f-ed07-4a9d-bc07-2fa5d69b3d51-10_622_1441_194_312} \captionsetup{labelformat=empty} \caption{Figure 7}
       \end{figure} An engineering project is modelled by the activity network shown in Figure 7. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest time.
19. Calculate the early time and late time for each event. Write these in the boxes in Diagram 1 in the answer book.
20. State the critical activities.
21. Find the total float on activities \(D\) and \(F\). You must show your working.
22. On the grid in the answer book, draw a cascade (Gantt) chart for this project. The chief engineer visits the project on day 15 and day 25 to check the progress of the work. Given that the project is on schedule,
23. which activities must be happening on each of these two days?