AQA D1 (Decision Mathematics 1)

3

1. 1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The numbers on each edge represent the distances, in miles, between pairs of vertices.
   \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-004_1294_1118_785_445}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your spanning tree.
   3. Draw your spanning tree.

4 The diagram shows the feasible region of a linear programming problem.
\includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-005_1349_1395_408_294}

1. On the feasible region, find:
   1. the maximum value of \(2 x + 3 y\);
   2. the maximum value of \(3 x + 2 y\);
   3. the minimum value of \(- 2 x + y\).
2. Find the 5 inequalities that define the feasible region.

5 [Figure 1, printed on the insert, is provided for use in this question.]
The network shows the times, in minutes, to travel between 10 towns.
\includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-006_412_1561_568_233}

1. Use Dijkstra's algorithm on Figure 1 to find the minimum time to travel from \(A\) to \(J\).
   (6 marks)
2. State the corresponding route.
   (1 mark)

7 Stella is visiting Tijuana on a day trip. The diagram shows the lengths, in metres, of the roads near the bus station.
\includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-007_1539_1162_495_424} Stella leaves the bus station at \(A\). She decides to walk along all of the roads at least once before returning to \(A\).

1. Explain why it is not possible to start from \(A\), travel along each road only once and return to \(A\).
2. Find the length of an optimal 'Chinese postman' route around the network, starting and finishing at \(A\).
3. At each of the 9 places \(B , C , \ldots , J\), there is a statue. Find the number of times that Stella will pass a statue if she follows her optimal route.