AQA D1 (Decision Mathematics 1) 2007 January

1 The following network shows the lengths, in miles, of roads connecting nine villages.
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-02_856_1251_568_374}

1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
2. Find the length of your minimum spanning tree.
3. Draw your minimum spanning tree.
4. State the number of other spanning trees that are of the same length as your answer in part (a).

2 Five people \(A , B , C , D\) and \(E\) are to be matched to five tasks \(R , S , T , U\) and \(V\).
The table shows the tasks that each person is able to undertake.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task \(V , B\) to task \(R , C\) to task \(T\), and \(E\) to task \(U\). Demonstrate, by using an alternating path from this initial matching, how each person can be matched to a task.

3 Mark is driving around the one-way system in Leicester. The following table shows the times, in minutes, for Mark to drive between four places: \(A , B , C\) and \(D\). Mark decides to start from \(A\), drive to the other three places and then return to \(A\). Mark wants to keep his driving time to a minimum.

1. Find the length of the tour \(A B C D A\).
2. Find the length of the tour \(A D C B A\).
3. Find the length of the tour using the nearest neighbour algorithm starting from \(A\).
4. Write down which of your answers to parts (a), (b) and (c) gives the best upper bound for Mark's driving time.

4

1. A student is using a bubble sort to rearrange seven numbers into ascending order.
   Her correct solution is as follows:

   Initial list	18	17	13	26	10	14	24
   After 1st pass	17	13	18	10	14	24	26
   After 2nd pass	13	17	10	14	18	24	26
   After 3rd pass	13	10	14	17	18	24	26
   After 4th pass	10	13	14	17	18	24	26
   After 5th pass	10	13	14	17	18	24	26

   Write down the number of comparisons and swaps on each of the five passes.
2. Find the maximum number of comparisons and the maximum number of swaps that might be needed in a bubble sort to rearrange seven numbers into ascending order.

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

1. 1. Trace the algorithm in the case where \(A = 2\) and \(B = 3\).
   2. Trace the algorithm in the case where \(A = 6\) and \(B = 8\).
2. State the purpose of the algorithm.
3. Write down the final value of \(C\) in the case where \(A = 200\) and \(B = 300\).

6 [Figure 1, printed on the insert, is provided for use in this question.]
Dino is to have a rectangular swimming pool at his villa.
He wants its width to be at least 2 metres and its length to be at least 5 metres.
He wants its length to be at least twice its width.
He wants its length to be no more than three times its width.
Each metre of the width of the pool costs \(\pounds 1000\) and each metre of the length of the pool costs \(\pounds 500\). He has \(\pounds 9000\) available. Let the width of the pool be \(x\) metres and the length of the pool be \(y\) metres.

1. Show that one of the constraints leads to the inequality $$2 x + y \leqslant 18$$
2. Find four further inequalities.
3. On Figure 1, draw a suitable diagram to show the feasible region.
4. Use your diagram to find the maximum width of the pool. State the corresponding length of the pool.

7 [Figure 2, printed on the insert, is provided for use in this question.]
The network shows the times, in seconds, taken by Craig to walk along walkways connecting ten hotels in Las Vegas.
\includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-07_1435_1267_525_351} The total of all the times in the diagram is 2280 seconds.

1. 1. Craig is staying at the Circus ( \(C\) ) and has to visit the Oriental ( \(O\) ). Use Dijkstra's algorithm on Figure 2 to find the minimum time to walk from \(C\) to \(O\).
   2. Write down the corresponding route.
2. 1. Find, by inspection, the shortest time to walk from \(A\) to \(M\).
   2. Craig intends to walk along all the walkways. Find the minimum time for Craig to walk along every walkway and return to his starting point.

8

1. The diagram shows a graph \(\mathbf { G }\) with 9 vertices and 9 edges.
   \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_188_204_411_708}
   \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_184_204_415_1105}
   \includegraphics[max width=\textwidth, alt={}, center]{e47eb41e-0a4b-4865-a8ff-6c9978495ee0-08_183_204_612_909}
   1. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make a connected graph. Draw an example of such a graph.
   2. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Hamiltonian. Draw an example of such a graph.
   3. State the minimum number of edges that need to be added to \(\mathbf { G }\) to make the graph Eulerian. Draw an example of such a graph.
2. A complete graph has \(n\) vertices and is Eulerian.
   1. State the condition that \(n\) must satisfy.
   2. In addition, the number of edges in a Hamiltonian cycle for the graph is the same as the number of edges in an Eulerian trail. State the value of \(n\).