AQA D1 (Decision Mathematics 1) 2006 January

1

1. Draw a bipartite graph representing the following adjacency matrix.
   (2 marks)

   	\(\boldsymbol { U }\)	\(V\)	\(\boldsymbol { W }\)	\(\boldsymbol { X }\)	\(\boldsymbol { Y }\)	\(\boldsymbol { Z }\)
   \(\boldsymbol { A }\)	1	0	1	0	1	0
   \(\boldsymbol { B }\)	0	1	0	1	0	0
   \(\boldsymbol { C }\)	0	1	0	0	0	1
   \(\boldsymbol { D }\)	0	0	0	1	0	0
   \(\boldsymbol { E }\)	0	0	1	0	1	1
   \(\boldsymbol { F }\)	0	0	0	1	1	0

2. Given that initially \(A\) is matched to \(W , B\) is matched to \(X , C\) is matched to \(V\), and \(E\) is matched to \(Y\), use the alternating path algorithm, from this initial matching, to find a complete matching. List your complete matching.

2 Use the quicksort algorithm to rearrange the following numbers into ascending order. Indicate clearly the pivots that you use. $$\begin{array} { l l l l l l l l } 18 & 23 & 12 & 7 & 26 & 19 & 16 & 24 \end{array}$$

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]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-03_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]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-04_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]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-05_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)

6 Two algorithms are shown. \section*{Algorithm 1} \section*{Algorithm 2} In the case where the input values are \(P = 400 , R = 5\) and \(T = 3\) :

1. trace Algorithm 1;
2. trace Algorithm 2.

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]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-06_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.

8 Salvadore is visiting six famous places in Barcelona: La Pedrera \(( L )\), Nou Camp \(( N )\), Olympic Village \(( O )\), Park Guell \(( P )\), Ramblas \(( R )\) and Sagrada Familia \(( S )\). Owing to the traffic system the time taken to travel between two places may vary according to the direction of travel. The table shows the times, in minutes, that it will take to travel between the six places.

1. Find the total travelling time for:
   1. the route \(L N O L\);
   2. the route \(L O N L\).
2. Give an example of a Hamiltonian cycle in the context of the above situation.
3. Salvadore intends to travel from one place to another until he has visited all of the places before returning to his starting place.
   1. Show that, using the nearest neighbour algorithm starting from Sagrada Familia \(( S )\), the total travelling time for Salvadore is 145 minutes.
   2. Explain why your answer to part (c)(i) is an upper bound for the minimum travelling time for Salvadore.
   3. Salvadore starts from Sagrada Familia ( \(S\) ) and then visits Ramblas ( \(R\) ). Given that he visits Nou Camp \(( N )\) before Park Guell \(( P )\), find an improved upper bound for the total travelling time for Salvadore.

9 A factory makes three different types of widget: plain, bland and ordinary. Each widget is made using three different machines: \(A , B\) and \(C\). Each plain widget needs 5 minutes on machine \(A , 12\) minutes on machine \(B\) and 24 minutes on machine \(C\). Each bland widget needs 4 minutes on machine \(A , 8\) minutes on machine \(B\) and 12 minutes on machine \(C\). Each ordinary widget needs 3 minutes on machine \(A\), 10 minutes on machine \(B\) and 18 minutes on machine \(C\). Machine \(A\) is available for 3 hours a day, machine \(B\) for 4 hours a day and machine \(C\) for 9 hours a day. The factory must make:
more plain widgets than bland widgets;
more bland widgets than ordinary widgets.
At least \(40 \%\) of the total production must be plain widgets.
Each day, the factory makes \(x\) plain, \(y\) bland and \(z\) ordinary widgets.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), writing your answers with simplified integer coefficients.
(8 marks)