AQA D1 (Decision Mathematics 1) 2010 June

1. Draw a bipartite graph representing the following adjacency matrix. [2 marks] $$\begin{array}{c|ccccc} & 1 & 2 & 3 & 4 & 5 \\ \hline A & 1 & 0 & 0 & 0 & 1 \\ B & 0 & 1 & 1 & 1 & 0 \\ C & 0 & 1 & 1 & 1 & 0 \\ D & 1 & 0 & 0 & 0 & 1 \\ E & 1 & 0 & 0 & 0 & 1 \\ \end{array}$$
2. If \(A\), \(B\), \(C\), \(D\) and \(E\) represent five people and 1, 2, 3, 4 and 5 represent five tasks to which they are to be assigned, explain why a complete matching is impossible. [2 marks]

1. 1. Use a bubble sort to rearrange the following numbers into ascending order, showing the list of numbers after each pass. 6 \quad 2 \quad 3 \quad 5 \quad 4 [3 marks]
   2. Write down the number of comparisons on the first pass. [1 mark]
2. 1. Use a shuttle sort to rearrange the following numbers into ascending order, showing the list of numbers after each pass. 6 \quad 2 \quad 3 \quad 5 \quad 4 [4 marks]
   2. Write down the number of comparisons on the first pass. [1 mark]

The network shows 10 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. \includegraphics{figure_3}

1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 towns. [6 marks]
2. State the length of your minimum spanning tree. [1 mark]
3. Draw your minimum spanning tree. [3 marks]
4. If Prim's algorithm, starting at \(B\), had been used to find the minimum spanning tree, state which edge would have been the final edge to complete the minimum spanning tree. [1 mark]

The network below shows 13 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges. The total of all the times is 384 minutes.

1. Use Dijkstra's algorithm on the network below, starting from \(M\), to find the minimum time to travel from \(M\) to each of the other towns. [7 marks]
2. 1. Find the travelling time of an optimum Chinese postman route around the network, starting and finishing at \(M\). [6 marks]
   2. State the number of times that the vertex \(F\) would appear in a corresponding route. [1 mark]

\includegraphics{figure_4}

Phil, a squash coach, wishes to buy some equipment for his club. In a town centre, there are six shops, \(G\), \(I\), \(N\), \(R\), \(S\) and \(T\), that sell the equipment. The time, in seconds, to walk between each pair of shops is shown in the table. Phil intends to check prices by visiting each of the six shops before returning to his starting point. $$\begin{array}{c|cccccc} & G & I & N & R & S & T \\ \hline G & - & 81 & 82 & 86 & 72 & 76 \\ I & 81 & - & 80 & 82 & 68 & 73 \\ N & 82 & 80 & - & 84 & 70 & 74 \\ R & 86 & 82 & 84 & - & 74 & 70 \\ S & 72 & 68 & 70 & 74 & - & 64 \\ T & 76 & 73 & 74 & 70 & 64 & - \\ \end{array}$$

1. Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time. [4 marks]
2. Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a). [1 mark]
3. By deleting \(S\), find a lower bound for Phil's minimum walking time. [5 marks]

Phil is to buy some squash balls for his club. There are three different types of ball that he can buy: slow, medium and fast. He must buy at least 190 slow balls, at least 50 medium balls and at least 50 fast balls. He must buy at least 300 balls in total. Each slow ball costs £2.50, each medium ball costs £2.00 and each fast ball costs £2.00. He must spend no more than £1000 in total. At least 60% of the balls that he buys must be slow balls. Phil buys \(x\) slow balls, \(y\) medium balls and \(z\) fast balls.

1. Find six inequalities that model Phil's situation. [4 marks]
2. Phil decides to buy the same number of medium balls as fast balls.
   1. Show that the inequalities found in part (a) simplify to give $$x \geq 190, \quad y \geq 50, \quad x + 2y \geq 300, \quad 5x + 8y \leq 2000, \quad y \leq \frac{1}{3}x$$ [2 marks]
   2. Phil sells all the balls that he buys to members of the club. He sells each slow ball for £3.00, each medium ball for £2.25 and each fast ball for £2.25. He wishes to maximise his profit. On Figure 1 on page 14, draw a diagram to enable this problem to be solved graphically, indicating the feasible region and the direction of an objective line. [7 marks]
   3. Find Phil's maximum possible profit and state the number of each type of ball that he must buy to obtain this maximum profit. [4 marks]

A student is testing a numerical method for finding an approximation for \(\pi\). The algorithm that the student is using is as follows. Line 10 \quad Input \(A\), \(B\), \(C\), \(D\), \(E\) Line 20 \quad Let \(A = A + 2\) Line 30 \quad Let \(B = -B\) Line 40 \quad Let \(C = \frac{B}{A}\) Line 50 \quad Let \(D = D + C\) Line 60 \quad Let \(E = (D - 3.14)^2\) Line 70 \quad If \(E < 0.05\) then go to Line 90 Line 80 \quad Go to Line 20 Line 90 \quad Print '\(\pi\) is approximately', \(D\) Line 100 \quad End Trace the algorithm in the case where the input values are $$A = 1, \quad B = 4, \quad C = 0, \quad D = 4, \quad E = 0$$ [6 marks]

A simple connected graph has six vertices.

1. One vertex has degree \(x\). State the greatest and least possible values of \(x\). [2 marks]
2. The six vertices have degrees $$x - 2, \quad x - 2, \quad x, \quad 2x - 4, \quad 2x - 4, \quad 4x - 12$$ Find the value of \(x\), justifying your answer. [2 marks]