Edexcel D1 (Decision Mathematics 1) 2010 June

2. \begin{figure}[h] \end{figure} Figure 1 represents the distances, in metres, between eight vertices, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H , in a network.

1. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
2. Complete Matrix 1 in your answer book, to represent the network.
3. Starting at A, use Prim's algorithm to determine a minimum spanning tree. You must clearly state the order in which you considered the vertices and the order in which you included the arcs.
4. State the weight of the minimum spanning tree.

4. \begin{figure}[h] \end{figure} Figure 2 models a network of tunnels that have to be inspected. The number on each arc represents the length, in km , of that tunnel.
Malcolm needs to travel through each tunnel at least once and wishes to minimise the length of his inspection route.
He must start and finish at A.

1. Use the route inspection algorithm to find the tunnels that will need to be traversed twice. You should make your method and working clear.
   (5)
2. Find a route of minimum length, starting and finishing at A . State the length of your route.
   (3) A new tunnel, CG, is under construction. It will be 10 km long.
   Malcolm will have to include the new tunnel in his inspection route.
3. What effect will the new tunnel have on the total length of his route? Justify your answer.
   (2)

5. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6.
Figure 4 shows an initial matching.

1. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching.
2. Explain why a complete matching is not possible. After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
3. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching.

6. \begin{figure}[h] \end{figure} Figure 5 shows a network of cycle tracks within a national park. The number on each arc represents the time taken, in minutes, to cycle along the corresponding track.

1. Use Dijkstra's algorithm to find the quickest route from S to T . State your quickest route and the time it takes.
   (6)
2. Explain how you determined your quickest route from your labelled diagram.
   (2)
3. Write down the quickest route from E to T.
   (1)

7. \begin{figure}[h] \end{figure} Keith organises two types of children's activity, 'Sports Mad' and 'Circus Fun'. He needs to determine the number of times each type of activity is to be offered. Let \(x\) be the number of times he offers the 'Sports Mad' activity. Let \(y\) be the number of times he offers the 'Circus Fun' activity. Two constraints are
and $$\begin{aligned} & x \leqslant 15
& y > 6 \end{aligned}$$ These constraints are shown on the graph in Figure 6, where the rejected regions are shaded out.

1. Explain why \(y = 6\) is shown as a dotted line.
   (1) Two further constraints are $$\begin{aligned} 3 x & \geqslant 2 y
   \text { and } \quad 5 x + 4 y & \geqslant 80 \end{aligned}$$
2. Add two lines and shading to Diagram 1 in the answer book to represent these inequalities. Hence determine the feasible region and label it R . Each 'Sports Mad' activity costs \(\pounds 500\).
   Each 'Circus Fun' activity costs \(\pounds 800\).
   Keith wishes to minimise the total cost.
3. Write down the objective function, C , in terms of \(x\) and \(y\).
4. Use your graph to determine the number of times each type of activity should be offered and the total cost. You must show sufficient working to make your method clear.

8. \begin{figure}[h] \end{figure} A 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 possible time.

1. Complete Diagram 2 in the answer book to show the early and late event times.
2. State the critical activities.
3. On Grid 1 in the answer book, draw a cascade (Gantt) chart for this project.
4. Use your cascade chart to determine a lower bound for the number of workers needed. You must justify your answer.