AQA D1 (Decision Mathematics 1) 2006 June

1 Five people, \(A , B , C , D\) and \(E\), are to be matched to five tasks, 1, 2, 3, 4 and 5. The table shows which tasks each person can do.

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 . Use an alternating path from this initial matching to find a complete matching.

2

1. Use a shuttle sort to rearrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 18 & 2 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$
2. State the number of comparisons and swaps (exchanges) for each of the first three passes.

3 [Figure 1, printed on the insert, is provided for use in part (b) of this question.]
The diagram shows a network of roads. The number on each edge is the length, in kilometres, of the road.
\includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-03_716_1303_559_388}

1. 1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
2. 1. Use Dijkstra's algorithm on Figure 1 to find the shortest distance from \(A\) to \(J\).
   2. A new road, of length \(x \mathrm {~km}\), is built connecting \(I\) to \(J\). The minimum distance from \(A\) to \(J\) is reduced by using this new road. Find, and solve, an inequality for \(x\).

4 The diagram shows a network of roads connecting 6 villages. The number on each edge is the length, in miles, of the road.
\includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-04_670_1298_466_356} Total length of the roads \(= 164\) miles

1. A police patrol car based at village \(A\) has to travel along each road at least once before returning to \(A\). Find the length of an optimal 'Chinese postman' route for the police patrol car.
2. A council worker starts from \(A\) and travels along each road at least once before finishing at \(C\). Find the length of an optimal route for the council worker.
3. A politician is to travel along all the roads at least once. He can start his journey at any village and can finish his journey at any village.
   1. Find the length of an optimal route for the politician.
   2. State the vertices from which the politician could start in order to achieve this optimal route.

5 [Figure 2, printed on the insert, is provided for use in this question.]

1. Gill is solving a travelling salesperson problem.
   1. She finds the following upper bounds: 7.5, 8, 7, 7.5, 8.5. Write down the best upper bound.
   2. She finds the following lower bounds: \(6.5,7,6.5,5,7\). Write down the best lower bound.
2. George is travelling by plane to a number of cities. He is to start at \(F\) and visit each of the other cities at least once before returning to \(F\). The diagram shows the times of flights, in hours, between cities. Where no time is shown, there is no direct flight available.
   \includegraphics[max width=\textwidth, alt={}, center]{63e7775d-2a63-4584-b3be-ce97927bcfcc-05_936_826_1162_589}
   1. Complete Figure 2 to show the minimum times to travel between all pairs of cities.
   2. Find an upper bound for the minimum total flying time by using the route FTPOMF.
   3. Using the nearest neighbour algorithm starting from \(F\), find an upper bound for the minimum total flying time.
   4. By deleting \(F\), find a lower bound for the minimum total flying time.

6 [Figure 3, printed on the insert, is provided for use in this question.]
Ernesto is to plant a garden with two types of tree: palms and conifers.
He is to plant at least 10, but not more than 80 palms.
He is to plant at least 5 , but not more than 40 conifers.
He cannot plant more than 100 trees in total. Each palm needs 20 litres of water each day and each conifer needs 60 litres of water each day. There are 3000 litres of water available each day. Ernesto makes a profit of \(\pounds 2\) on each palm and \(\pounds 1\) on each conifer that he plants and he wishes to maximise his profit. Ernesto plants \(x\) palms and \(y\) conifers.

1. Formulate Ernesto's situation as a linear programming problem.
2. On Figure 3, 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 maximum profit for Ernesto.
4. Ernesto introduces a new pricing structure in which he makes a profit of \(\pounds 1\) on each palm and \(\pounds 4\) on each conifer. Find Ernesto's new maximum profit and the number of each type of tree that he should plant to obtain this maximum profit.

7 A connected graph \(\mathbf { G }\) has \(m\) vertices and \(n\) edges.

1. 1. Write down the number of edges in a minimum spanning tree of \(\mathbf { G }\).
   2. Hence write down an inequality relating \(m\) and \(n\).
2. The graph \(\mathbf { G }\) contains a Hamiltonian cycle. Write down the number of edges in this cycle.
3. In the case where \(\mathbf { G }\) is Eulerian, draw a graph of \(\mathbf { G }\) for which \(m = 6\) and \(n = 12\).