AQA D1 (Decision Mathematics 1) 2012 June

1 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake.
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-02_1003_547_740_737}

1. Represent this information in an adjacency matrix.
2. Initially, \(B\) is assigned to task 4, \(C\) to task 3, \(D\) to task 1, \(E\) to task 5 and \(F\) to task 6. By using an algorithm from this initial matching, find a complete matching.
   (3 marks)

2 A student is using a shuttle sort algorithm to rearrange a set of numbers into ascending order. Her correct solution for the first three passes is as follows.

3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\).
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_810_501_445_388}
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-06_812_499_443_1135}

1. 1. Use Prim's algorithm starting from \(A\), showing the order in which you select the edges, to find a minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.
2. Prim's algorithm from different starting points produces the same minimum spanning tree for this network. State the final edge that would complete the minimum spanning tree using Prim's algorithm:
   1. starting from \(D\);
   2. starting from \(H\).

4 The edges on the network below represent some major roads in a city. The number on each edge is the minimum time taken, in minutes, to drive along that road.

1. 1. Use Dijkstra's algorithm on the network to find the shortest possible driving time from \(A\) to \(J\).
   2. Write down the corresponding route.
2. A new ring road is to be constructed connecting \(A\) to \(J\) directly. Find the maximum length of this new road from \(A\) to \(J\) if the time taken to drive along it, travelling at an average speed of \(90 \mathrm {~km} / \mathrm { h }\), is to be no more than the time found in part (a)(i). } \section*{(a)(i)} \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-08_912_1276_1053_429}

5 The network below shows some streets in a town. The number on each edge shows the length of that street, in metres. Leaflets are to be distributed by a restaurant owner, Tony, from his restaurant located at vertex \(B\). Tony must start from his restaurant, walk along all the streets at least once, before returning to his restaurant.
\includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-10_643_1353_625_340} The total length of the streets is 2430 metres.

1. Find the length of an optimal Chinese postman route for Tony.
2. Colin also wishes to distribute some leaflets. He starts from his house at \(H\), walks along all the streets at least once, before finishing at the restaurant at \(B\). Colin wishes to walk the minimum distance. Find the length of an optimal route for Colin.
3. David also walks along all the streets at least once. He can start at any vertex and finish at any vertex. David also wishes to walk the minimum distance.
   1. Find the length of an optimal route for David.
   2. State the vertices from which David could start in order to achieve this optimal route.

6 The complete graph \(K _ { n } ( n > 1 )\) has every one of its \(n\) vertices connected to each of the other vertices by a single edge.

1. Draw the complete graph \(K _ { 4 }\).
2. 1. Find the total number of edges for the graph \(K _ { 8 }\).
   2. Give a reason why \(K _ { 8 }\) is not Eulerian.
3. For the graph \(K _ { n }\), state in terms of \(n\) :
   1. the total number of edges;
   2. the number of edges in a minimum spanning tree;
   3. the condition for \(K _ { n }\) to be Eulerian;
   4. the condition for the number of edges of a Hamiltonian cycle to be equal to the number of edges of an Eulerian cycle.

7 Rupta, a sales representative, has to visit six shops, \(A , B , C , D , E\) and \(F\). Rupta starts at shop \(A\) and travels to each of the other shops once, before returning to shop \(A\). Rupta wishes to keep her travelling time to a minimum. The table shows the travelling times, in minutes, between the shops.

8 The following algorithm finds an estimate of the value of the number represented by the symbol e:

1. Trace the algorithm.
2. A student miscopied Line 70 . His line was
   Line 70 Go to Line 10
   Explain what would happen if his algorithm were traced.

9 Ollyin is buying new pillows for his hotel. He buys three types of pillow: soft, medium and firm. He must buy at least 100 soft pillows and at least 200 medium pillows.
He must buy at least 400 pillows in total.
Soft pillows cost \(\pounds 4\) each. Medium pillows cost \(\pounds 3\) each. Firm pillows cost \(\pounds 4\) each.
He wishes to spend no more than \(\pounds 1800\) on new pillows.
At least \(40 \%\) of the new pillows must be medium pillows.
Ollyin buys \(x\) soft pillows, \(y\) medium pillows and \(z\) firm pillows.

1. In addition to \(x \geqslant 0 , y \geqslant 0\) and \(z \geqslant 0\), find five inequalities in \(x , y\) and \(z\) that model the above constraints.
2. Ollyin decides to buy twice as many soft pillows as firm pillows.
   1. Show that three of your answers in part (a) become $$\begin{aligned} 3 x + 2 y & \geqslant 800
      2 x + y & \leqslant 600
      y & \geqslant x \end{aligned}$$
   2. On the grid opposite, draw a suitable diagram to represent Ollyin's situation, indicating the feasible region.
   3. Use your diagram to find the maximum total number of pillows that Ollyin can buy.
   4. Find the number of each type of pillow that Ollyin can buy that corresponds to your answer to part (b)(iii).
      \includegraphics[max width=\textwidth, alt={}]{1258a6d3-558a-46dc-a916-d71f71b175ff-20_2256_1707_221_153}