AQA D1 (Decision Mathematics 1) 2008 June

1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 .
The following adjacency matrix shows the possible matching of people to tasks.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5. From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.

2

1. Use a quick sort to rearrange the following letters into alphabetical order. You must indicate the pivot that you use at each pass.
   P
   B
   M
   N
   J
   K
   R
   D
   (5 marks)
2. 1. Find the maximum number of swaps needed to rearrange a list of 8 numbers into ascending order when using a bubble sort.
      (1 mark)
   2. A list of 8 numbers was rearranged into ascending order using a bubble sort. The maximum number of swaps was needed. What can be deduced about the original list of numbers?
      (1 mark)

3

1. 1. State the number of edges in a minimum spanning tree of a network with 11 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 11 vertices, \(A , B , \ldots , K\). The number on each edge represents the distance, in miles, between a pair of vertices.
   \includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-03_1468_1239_721_404}
   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 David, a tourist, wishes to visit five places in Rome: Basilica ( \(B\) ), Coliseum ( \(C\) ), Pantheon ( \(P\) ), Trevi Fountain ( \(T\) ) and Vatican ( \(V\) ). He is to start his tour at one of the places, visit each of the other places, before returning to his starting place. The table shows the times, in minutes, to travel between these places. David wishes to keep his travelling time to a minimum.

1. 1. Find the total travelling time for the tour TPVBCT.
   2. Find the total travelling time for David's tour using the nearest neighbour algorithm starting from \(T\).
   3. Explain why your answer to part (a)(ii) is an upper bound for David's minimum total travelling time.
2. 1. By deleting \(B\), find a lower bound for the total travelling time for the minimum tour.
   2. Explain why your answer to part (b)(i) is a lower bound for David's minimum total travelling time.
3. Sketch a network showing the edges that give the lower bound found in part (b)(i) and comment on its significance.

5 The diagram shows a network of sixteen roads on a housing estate. The number on each edge is the length, in metres, of the road. The total length of the sixteen roads is 1920 metres. \begin{figure}[h] \end{figure}

1. Chris, an ice-cream salesman, travels along each road at least once, starting and finishing at the point \(A\). Find the length of an optimal 'Chinese postman' route for Chris.
2. Pascal, a paperboy, starts at \(A\) and walks along each road at least once before finishing at \(D\). Find the length of an optimal route for Pascal.
3. Millie is to walk along all the roads at least once delivering leaflets. She can start her journey at any point and she can finish her journey at any point.
   1. Find the length of an optimal route for Millie.
   2. State the points from which Millie could start in order to achieve this optimal route.

6 [Figure 1, printed on the insert, is provided for use in this question.]
A factory makes two types of lock, standard and large, on a particular day.
On that day:
the maximum number of standard locks that the factory can make is 100 ;
the maximum number of large locks that the factory can make is 80 ;
the factory must make at least 60 locks in total;
the factory must make more large locks than standard locks.
Each standard lock requires 2 screws and each large lock requires 8 screws, and on that day the factory must use at least 320 screws. On that day, the factory makes \(x\) standard locks and \(y\) large locks.
Each standard lock costs \(\pounds 1.50\) to make and each large lock costs \(\pounds 3\) to make.
The manager of the factory wishes to minimise the cost of making the locks.

1. Formulate the manager's situation as a linear programming problem.
2. On Figure 1, draw a suitable diagram to enable the problem to be solved graphically, indicating the feasible region and the direction of the objective line.
3. Find the values of \(x\) and \(y\) that correspond to the minimum cost. Hence find this minimum cost.

7 [Figure 2, printed on the insert, is provided for use in this question.]
The following network has eight vertices, \(A , B , \ldots , H\), and edges connecting some pairs of vertices. The number on each edge is its weight. The weights on the edges \(E H\) and \(G H\) are functions of \(x\) and \(y\).
\includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-07_1170_1705_596_164} Given that there are three routes from \(A\) to \(H\) with the same minimum weight, use Dijkstra's algorithm on Figure 2 to find:

1. this minimum weight;
2. the values of \(x\) and \(y\).