AQA D1 (Decision Mathematics 1) 2005 June

1 Use a shuttle sort algorithm to rearrange the following numbers into ascending order, showing the new arrangement after each pass. $$\begin{array} { l l l l l l l l } 23 & 3 & 17 & 4 & 6 & 19 & 14 & 3 \end{array}$$ (5 marks)

2 A father is going to give each of his five daughters: Grainne ( \(G\) ), Kath ( \(K\) ), Mary ( \(M\) ), Nicola ( \(N\) ) and Stella ( \(S\) ), one of the five new cars that he has bought: an Audi ( \(A\) ), a Ford Focus ( \(F\) ), a Jaguar ( \(J\) ), a Peugeot ( \(P\) ) and a Range Rover ( \(R\) ). The daughters express preferences for the car that they would like to be given, as shown in the table.

1. Show all these preferences on a bipartite graph.
2. Initially the father allocates the Peugeot to Kath, the Jaguar to Mary, and the Audi to Nicola. Demonstrate, by using alternating paths from this initial matching, how each daughter can be matched to a car which is one of her preferences.
   (6 marks)

3 A theme park has 11 rides, \(A , B , \ldots K\). The network shows the distances, in metres, between pairs of rides. The rides are to be connected by cabling so that information can be collated. The manager of the theme park wishes to use the minimum amount of cabling.
\includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-03_988_1575_488_248}

1. Use Prim's algorithm, starting from \(A\), to find the minimum spanning tree for the network.
2. State the length of cabling required.
3. Draw your minimum spanning tree.
4. The manager decides that the edge \(A E\) must be included. Find the extra length of cabling now required to give the smallest spanning tree that includes \(A E\).

4

1. In the complete graph \(\mathrm { K } _ { 7 }\), every one of the 7 vertices is connected to each of the other 6 vertices by a single edge. Find or write down:
   1. the number of edges in the graph;
   2. the number of edges in a minimum spanning tree;
   3. the number of edges in a Hamiltonian cycle.
2. 1. Explain why the graph \(\mathrm { K } _ { 7 }\) is Eulerian.
   2. Write down the condition for \(\mathrm { K } _ { n }\) to be Eulerian.
3. A connected graph has 6 vertices and 10 edges. Draw an example of such a graph which is Eulerian.

5 A student is using the following algorithm with different values of \(X\).

1. Trace the algorithm, giving your answers to three decimal places where appropriate:
   1. in the case where the input value of \(X\) is 2 ;
   2. in the case where the input value of \(X\) is - 6 .
2. Another student used the same algorithm but omitted LINE 70. Describe the outcome for this student.

6 Mia is on holiday in Venice. There are five places she wishes to visit: Rialto \(( R )\), St Mark's \(( S )\), Murano ( \(M\) ), Burano ( \(B\) ) and Lido ( \(L\) ). Boat services connect the five places. The table shows the times, in minutes, to travel between the places. Mia wishes to keep her travelling time to a minimum.

1. 1. Find the length of the tour \(S R M B L S\).
   2. Find the length of the tour using the nearest neighbour algorithm starting from \(S\).
2. By deleting Burano ( \(B\) ), find a lower bound for the length of the minimum tour.
3. Sketch a network showing the edges that give the lower bound found in part (b) and comment on its significance.

7 [Figure 1, printed on the insert, is provided for use in this question.]
The diagram shows some of the main roads connecting Royton to London. The numbers on the edges represent the travelling times, in minutes, between adjacent towns. David lives in Royton and is planning to travel along some of the roads to a meeting in London.
\includegraphics[max width=\textwidth, alt={}, center]{a1290c22-f28d-42aa-89d5-10d60ca4741c-06_2196_1479_557_310}

1. 1. Use Dijkstra's algorithm on Figure 1 to find the minimum travelling time from Royton to London.
   2. Write down the route corresponding to this minimum travelling time.
2. On a particular day, before David leaves Royton, he knows that the road connecting Walsall and Marston is closed. Find the minimum extra time required to travel from Royton to London on this day. Write down the corresponding route.

8 [Figure 2, printed on the insert, is provided for use in this question.]
A company makes two types of boxes of chocolates, executive and luxury.
Every hour the company must make at least 15 of each type and at least 35 in total.
Each executive box contains 20 dark chocolates and 12 milky chocolates.
Each luxury box contains 10 dark chocolates and 18 milky chocolates.
Every hour the company has 600 dark chocolates and 600 milky chocolates available.
The company makes a profit of \(\pounds 1.50\) on each executive box and \(\pounds 1\) on each luxury box.
The company makes and sells \(x\) executive boxes and \(y\) luxury boxes every hour.
The company wishes to maximise its hourly profit, \(\pounds P\).

1. Show that one of the constraints leads to the inequality \(2 x + 3 y \leqslant 100\).
2. Formulate the company's situation as a linear programming problem.
3. On Figure 2, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and an objective line.
4. Use your diagram to find the maximum hourly profit.