OCR MEI D1 (Decision Mathematics 1) 2007 June

1 Bus routes connect towns A and B and towns A and C .
Train lines connect towns B and D, towns C and D, and towns A and C.
John represents this information in a graph with four nodes, one for each town, in which an arc is drawn for each connection, giving five arcs in all.

1. Draw John's graph.
2. Is John's graph simple? Justify your answer. Jamil represents the information in a graph with five nodes. He uses one node for each of towns A, B and D. Because in town C the bus station and train station are some distance apart, he uses a node labelled C (bus) and a node labelled C (train). Again there are 5 arcs, each representing a connection.
3. Draw Jamil's graph.
4. Is Jamil's graph a tree? Justify your answer.

2 Two hikers each have a 25 litre rucksack to pack. The items to be packed have volumes of 14, 6, 11, 9 and 6 litres.

1. Apply the first fit algorithm to the items in the order given and comment on the outcome.
2. Write the five items in descending order of volume. Apply the first fit decreasing algorithm to find a packing for the rucksacks.
3. The hikers argue that the first fit decreasing algorithm does not produce a fair allocation of volumes to rucksacks. Produce a packing which gives a fairer allocation of volumes between the two rucksacks. Explain why the hikers might not want to use this packing.

3 Use a graphical approach to solve the following LP. $$\begin{aligned} & \text { Maximise } \quad 2 x + 3 y
& \text { subject to } \quad x + 5 y \leqslant 14
& \quad x + 2 y \leqslant 8
& \quad 3 x + y \leqslant 21
& \quad x \geqslant 0
& y \geqslant 0 \end{aligned}$$ Section B (48 marks)

4 Colin is setting off for a day's sailing. The table and the activity network show the major activities that are involved, their durations and their precedences. \includegraphics[max width=\textwidth, alt={}, center]{21ab732d-435e-4f0b-bc88-21ddc2a398c9-3_480_912_555_925}

1. Complete the table in your answer book showing the immediate predecessors for each activity.
2. Find the early time and the late time for each event. Give the project duration and list the critical activities. When he sails on his own Colin can only do one thing at a time with the exception of activity G, motoring out of the harbour.
3. Use the activity network to determine which activities Colin can perform whilst motoring out of the harbour.
4. Find the minimum time to complete the activities when Colin sails on his own, and give a schedule for him to achieve this.
5. Find the minimum time to complete the activities when Colin sails with one other crew member, and give a schedule for them to achieve this.

5 The table shows the weights on the arcs of a network.

1. Draw the network.
2. Apply Dijkstra's algorithm to find the least weight route from G to D. (Do this on the network you drew for part (i).) Give your route and its total weight.
3. Find by inspection the route from \(G\) to \(D\) such that the minimum of the weights for arcs on the route is as large as possible. Give your route and its minimum arc weight. Give an application in which this might be needed.
4. Consider how Dijkstra's algorithm could be modified to solve the problem in part (iii). Explain how to update working values. Explain how to select the next vertex to be permanently labelled.

6 In winter in Metland the weather each day can be classified as dry, wet or snowy. The table shows the probabilities for the next day's weather given the current day's weather. You are to use two-digit random numbers to simulate the winter weather in Metland.

1. Give an efficient rule for using two-digit random numbers to simulate tomorrow's weather if today is
   (A) dry,
   (B) wet,
   (C) snowy.
2. Today is a dry winter's day in Metland. Use the following two-digit random numbers to simulate the next 7 days' weather in Metland. $$\begin{array} { l l l l l l l l l l } 23 & 85 & 98 & 99 & 56 & 47 & 82 & 14 & 03 & 12 \end{array}$$
3. Use your simulation from part (ii) to estimate the proportion of dry days in a Metland winter.
4. Explain how you could use simulation to produce an improved estimate of the proportion of dry days in a Metland winter.
5. Give two criticisms of this model of weather.