AQA D1 (Decision Mathematics 1) 2011 January

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{figure_1}

1. Represent this information in an adjacency matrix. [2]
2. Initially, \(B\) is assigned to task 5, \(D\) to task 2, \(E\) to task 4 and \(F\) to task 3. Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task. [5]

A student is using a quicksort algorithm to rearrange a set of numbers into ascending order. She uses the first number in each list (or sublist) as the pivot. Her correct solution for the first three passes is as follows. Initial list: 10, 7, 4, 22, 13, 16, 19, 5 After 1st pass: 7, 4, 5, 10, 22, 13, 16, 19 After 2nd pass: 4, 5, 7, 10, 13, 16, 19, 22 After 3rd pass: 4, 5, 7, 10, 13, 16, 19, 22

1. State the pivots used for the 2nd pass. [2]
2. Write down the number of comparisons on each of the three passes. [3]
3. Explain whether the student has completed the algorithm. [1]

The following network shows the lengths, in miles, of roads connecting nine villages, \(A\), \(B\), ..., \(I\). \includegraphics{figure_3}

1. 1. Use Prim's algorithm starting from \(E\), showing the order in which you select the edges, to find a minimum spanning tree for the network. [4]
   2. State the length of your minimum spanning tree. [1]
   3. Draw your minimum spanning tree. [2]
2. On a particular day, village \(B\) is cut off, so its connecting roads cannot be used. Find the length of a minimum spanning tree for the remaining eight villages. [2]

The network below shows some paths on an estate. The number on each edge represents the time taken, in minutes, to walk along a path.

1. 1. Use Dijkstra's algorithm on the network to find the minimum walking time from \(A\) to \(J\). [6]
   2. Write down the corresponding route. [1]
2. A new subway is constructed connecting \(C\) to \(G\) directly. The time taken to walk along this subway is \(x\) minutes. The minimum time taken to walk from \(A\) to \(G\) is now reduced, but the minimum time taken to walk from \(A\) to \(J\) is not reduced. Find the range of possible values for \(x\). [3]

\includegraphics{figure_4}

Norris delivers newspapers to houses on an estate. The network shows the streets on the estate. The number on each edge shows the length of the street, in metres. Norris starts from the newsagents located at vertex \(A\), and he must walk along all the streets at least once before returning to the newsagents. \includegraphics{figure_5} The total length of the streets is 1215 metres.

1. Give a reason why it is not possible to start at \(A\), walk along each street once only, and return to \(A\). [1]
2. Find the length of an optimal Chinese postman route around the estate, starting and finishing at \(A\). [5]
3. For an optimal Chinese postman route, state:
   1. the number of times that the vertex \(F\) would occur; [1]
   2. the number of times that the vertex \(H\) would occur. [1]

1. The complete graph \(K_n\) has every one of its \(n\) vertices connected to each of the other vertices by a single edge.
   1. Find the total number of edges in the graph \(K_5\). [1]
   2. State the number of edges in a minimum spanning tree for the graph \(K_5\). [1]
   3. State the number of edges in a Hamiltonian cycle for the graph \(K_5\). [1]
2. A simple graph \(G\) has six vertices and nine edges, and \(G\) is Eulerian. Draw a sketch to show a possible graph \(G\). [2]

Fred delivers bread to five shops, \(A\), \(B\), \(C\), \(D\) and \(E\). Fred starts his deliveries at shop \(B\), and travels to each of the other shops once before returning to shop \(B\). Fred wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the shops. $$\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & - & 3 & 11 & 15 & 5 \\ B & 3 & - & 18 & 12 & 4 \\ C & 11 & 18 & - & 5 & 16 \\ D & 15 & 12 & 5 & - & 10 \\ E & 5 & 4 & 16 & 10 & - \end{array}$$

1. Find the travelling time for the tour \(BACDEB\). [1]
2. Use the nearest neighbour algorithm, starting at \(B\), to find another upper bound for the travelling time for Fred's tour. [3]
3. By deleting \(C\), find a lower bound for the travelling time for Fred's tour. [4]
4. Sketch a network showing the edges that give you the lower bound in part (c) and comment on its significance. [2]

A student is tracing the following algorithm with positive integer values of \(A\) and \(B\). The function INT gives the integer part of a number, eg INT(2.3) = 2 and INT(3.8) = 3. Line 10: Let \(X = 0\) Line 20: Input \(A\), \(B\) Line 30: If INT\((A/2) = A/2\) then go to Line 50 Line 40: Let \(X = X + B\) Line 50: If \(A = 1\) then go to Line 90 Line 60: Let \(A =\) INT\((A/2)\) Line 70: Let \(B = 2 \times B\) Line 80: Go to Line 30 Line 90: Print \(X\) Line 100: End

1. Trace the algorithm in the case where the input values are \(A = 20\) and \(B = 8\). [4]
2. State the purpose of the algorithm. [1]
3. Another student changed Line 50 to Line 50: If \(A = 1\) then go to Line 80 Explain what would happen if this algorithm were traced. [2]

Herman is packing some hampers. Each day, he packs three types of hamper: basic, standard and luxury. Each basic hamper has 6 tins, 9 packets and 6 bottles. Each standard hamper has 9 tins, 6 packets and 12 bottles. Each luxury hamper has 9 tins, 9 packets and 18 bottles. Each day, Herman has 600 tins and 600 packets available, and he must use at least 480 bottles. Each day, Herman packs \(x\) basic hampers, \(y\) standard hampers and \(z\) luxury hampers.

1. In addition to \(x \geqslant 0\), \(y \geqslant 0\) and \(z \geqslant 0\), find three inequalities in \(x\), \(y\) and \(z\) that model the above constraints, simplifying each inequality. [4]
2. On a particular day, Herman packs the same number of standard hampers as luxury hampers.
   1. Show that your answers in part (a) become \(x + 3y \leqslant 100\) \(3x + 5y \leqslant 200\) \(x + 5y \geqslant 80\) [2]
   2. On the grid opposite, draw a suitable diagram to represent Herman's situation, indicating the feasible region. [4]
   3. Use your diagram to find the maximum total number of hampers that Herman can pack on that day. [2]
   4. Find the number of each type of hamper that Herman packs that corresponds to your answer to part (b)(iii). [1]