OCR MEI D1 (Decision Mathematics 1) 2010 January

1 The table shows the activities involved in a project, their durations and their precedences.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the critical activities.

2 The vertices of a graph are to be coloured using the following rules:

• all vertices are to be coloured
• no two vertices joined by an edge are to have the same colour.

The following graph has been coloured with four colours.
\includegraphics[max width=\textwidth, alt={}, center]{71ca9c4e-573b-43b7-910d-4bd610af6b27-2_357_883_1683_591} Kempe's rule allows for colours to be swapped. The rule is:

• choose two colours
• draw the subgraph consisting of the vertices coloured with these two colours, together with the edges that connect them
• in any connected part of this subgraph consisting of two or more vertices, the two colours can be swapped.
  1. Use Kempe's rule, choosing the colours blue and red.

Show that the graph can then be coloured with two colours.

Why does Kempe's rule not constitute an algorithm for colouring graphs?

3 Consider the following graph in which the arcs are straight lines.
\includegraphics[max width=\textwidth, alt={}, center]{71ca9c4e-573b-43b7-910d-4bd610af6b27-3_928_938_317_566}

1. Explain how you know that the graph is simple.
2. Explain how you know that the graph is not connected.
3. On the copy of the graph in your answer book, add as many arcs as you can whilst keeping it both simple and not connected. Give the number of arcs which you have added.
4. Imagine that a new graph is produced in which two vertices are connected if there is no connection between them, direct or indirect, on the original graph. How many arcs would this new graph have?

4 An air charter company has the following rules for selling seats on a flight.

1. The total number of seats sold must not exceed 120.
2. There must be at least 100 seats sold, or the flight will be cancelled.
3. For every child seat sold there must be a seat sold for a supervising adult.
   1. Define two variables so that the three constraints can be formulated in terms of your variables. Formulate the three constraints in terms of your variables.
   2. Graph your three inequalities from part (i).
   The price for a child seat is \(\pounds 50\) and the price for an adult seat is \(\pounds 100\).
4. Find the maximum income available from the flight, and mark and label the corresponding point on your graph.
5. Find the minimum income available from a full plane, and mark and label the corresponding point on your graph.
6. Find the minimum income available from the flight, and mark and label the corresponding point on your graph.
7. At \(\pounds 100\) for an adult seat and \(\pounds 50\) for a child seat the company would prefer to sell 100 adult seats and no child seats rather than have a full plane with 60 adults and 60 children. What would be the minimum price for a child's seat for that not to be the case, given that the adult seat price remains at \(\pounds 100\) ?

5 The matrix shows the distances in miles between towns where direct routes exist.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest route from A to F . Give the route and its length.
3. Use Kruskal's algorithm to find a minimum connector for the network, showing your working. Draw your connector and give its total length.
4. How much shorter would AD have to be if it were to be included in
   (A) a shortest route from A to F ,
   (B) a minimum connector?

6 An apple tree has 6 apples left on it. Each day each remaining apple has a probability of \(\frac { 1 } { 3 }\) of falling off the tree during the day.

1. Give a rule for using one-digit random numbers to simulate whether or not a particular apple falls off the tree during a given day.
2. Use the random digits given in your answer book to simulate how many apples fall off the tree during day 1 . Give the total number of apples that fall during day 1 .
3. Continue your simulation from the end of day 1 , which you simulated in part (ii), for successive days until there are no apples left on the tree. Use the same list of random digits, continuing from where you left off in part (ii). During which day does the last apple fall from the tree? Now suppose that at the start of each day the gardener picks one apple from the tree and eats it.
4. Repeat your simulation with the gardener picking the lowest numbered apple remaining on the tree at the start of each day. Give the day during which the last apple falls or is picked. Use the same string of random digits, a copy of which is provided for your use in this part of the question.
5. How could your results be made more reliable?