AQA D1 (Decision Mathematics 1) 2010 June

1

1. Draw a bipartite graph representing the following adjacency matrix.

   	1	2	3	4	5
   \(\boldsymbol { A }\)	1	0	0	0	1
   \(\boldsymbol { B }\)	0	1	1	1	0
   \(\boldsymbol { C }\)	0	1	1	1	0
   \(\boldsymbol { D }\)	1	0	0	0	1
   \(\boldsymbol { E }\)	1	0	0	0	1

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)
   \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-03_2484_1709_223_153}

2

1. 1. Use a bubble sort to rearrange the following numbers into ascending order, showing the list of numbers after each pass. $$\begin{array} { l l l l l } 6 & 2 & 3 & 5 & 4 \end{array}$$
   2. Write down the number of comparisons on the first pass.
2. 1. Use a shuttle sort to rearrange the following numbers into ascending order, showing the list of numbers after each pass. $$\begin{array} { l l l l l } 6 & 2 & 3 & 5 & 4 \end{array}$$
   2. Write down the number of comparisons on the first pass.
      \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-05_2484_1709_223_153}

3 The network shows 10 towns. The times, in minutes, to travel between pairs of towns are indicated on the edges.
\includegraphics[max width=\textwidth, alt={}, center]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-06_1299_1308_406_367}

1. Use Kruskal's algorithm, showing the order in which you select the edges, to find a minimum spanning tree for the 10 towns.
2. State the length of your minimum spanning tree.
3. Draw your minimum spanning tree.
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) \includegraphics[max width=\textwidth, alt={}, center]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-07_2484_1709_223_153}
   \includegraphics[max width=\textwidth, alt={}, center]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-08_2486_1724_221_143}
   \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-09_2484_1709_223_153}

5 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.

1. Use the nearest neighbour algorithm starting from \(S\) to find an upper bound for Phil's minimum walking time.
2. Write down a tour starting from \(N\) which has a total walking time equal to your answer to part (a).
3. By deleting \(S\), find a lower bound for Phil's minimum walking time.
   \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-11_2484_1709_223_153}

6 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 \(\pounds 2.50\), each medium ball costs \(\pounds 2.00\) and each fast ball costs \(\pounds 2.00\). He must spend no more than \(\pounds 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.
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 \geqslant 190 , y \geqslant 50 , x + 2 y \geqslant 300,5 x + 8 y \leqslant 2000 , y \leqslant \frac { 1 } { 3 } x$$
   2. Phil sells all the balls that he buys to members of the club. He sells each slow ball for \(\pounds 3.00\), each medium ball for \(\pounds 2.25\) and each fast ball for \(\pounds 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.
      \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-13_2484_1709_223_153}
      \includegraphics[max width=\textwidth, alt={}, center]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-15_2484_1709_223_153}
      \(7 \quad\) 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 Input \(A , B , C , D , E\)
      Line 20 Let \(A = A + 2\)
      Line 30 Let \(B = - B\)
      Line \(40 \quad\) Let \(C = \frac { B } { A }\)
      Line 50 Let \(D = D + C\)
      Line \(60 \quad\) Let \(E = ( D - 3.14 ) ^ { 2 }\)
      Line 70 If \(E < 0.05\) then go to Line 90
      Line 80 Go to Line 20
      Line 90 Print ' \(\pi\) is approximately', \(D\)
      Line 100 End Trace the algorithm in the case where the input values are $$A = 1 , B = 4 , C = 0 , D = 4 , E = 0$$ (6 marks)
      \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-17_2484_1707_223_155}

8 A simple connected graph has six vertices.

1. One vertex has degree \(x\). State the greatest and least possible values of \(x\).
2. The six vertices have degrees $$x - 2 , x - 2 , x , 2 x - 4,2 x - 4,4 x - 12$$ Find the value of \(x\), justifying your answer.
   
   \includegraphics[max width=\textwidth, alt={}]{fe9c0da0-40e3-4a87-ae9a-13ec0740ffff-19_2484_1707_223_155}