AQA D1 (Decision Mathematics 1) 2012 January

1 Use a Shell sort to rearrange the following numbers into ascending order, showing the new arrangement after each pass.
\(\begin{array} { l l l l l l l l } 37 & 25 & 16 & 12 & 36 & 24 & 13 & 11 \end{array}\)
(5 marks) PART REFERENCE REFERENCE

2

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

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)	\(\mathbf { 6 }\)
   \(\boldsymbol { A }\)	1	1	0	0	1	1
   \(\boldsymbol { B }\)	0	1	0	0	1	1
   \(\boldsymbol { C }\)	1	0	0	0	1	1
   \(\boldsymbol { D }\)	0	1	1	1	0	1
   \(\boldsymbol { E }\)	0	0	0	0	1	1
   \(\boldsymbol { F }\)	0	0	0	0	0	1

2. Given that \(A , B , C , D , E\) and \(F\) represent six people and that 1, 2, 3, 4, 5 and 6 represent six tasks to which they may be assigned, explain why a complete matching is impossible. \begin{verbatim} QUESTION PART REFERENCE \end{verbatim}

3 The following network shows the roads connecting seven villages, \(A , B , C , \ldots , G\). The number on each edge represents the length, in miles, between a pair of villages.
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-06_978_1108_443_466}

1. Use Kruskal's algorithm to find a minimum spanning tree for the network. (5 marks)
2. State the length of your minimum spanning tree.
3. There are two minimum spanning trees for this network. Draw both of these minimum spanning trees.

4 The following network shows the times, in minutes, taken by a policeman to walk along roads connecting 12 places, \(A , B , \ldots , L\), on his beat. Each day, the policeman has to walk along each road at least once, starting and finishing at \(A\).
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-08_1141_1313_461_360} The total of all the times in the network is 224 minutes.

1. Find the length of an optimal Chinese postman route for the policeman.
2. State the number of times that the vertex \(J\) would appear in a route corresponding to the length found in part (a).

5 The feasible region of a linear programming problem is determined by the following: $$\begin{aligned} y & \geqslant 20
x + y & \geqslant 25
5 x + 2 y & \leqslant 100
y & \leqslant 4 x
y & \geqslant 2 x \end{aligned}$$

1. On Figure 1 opposite, draw a suitable diagram to represent the inequalities and indicate the feasible region.
2. Use your diagram to find the minimum value of \(P\), on the feasible region, in the case where:
   1. \(P = x + 2 y\);
   2. \(P = - x + y\). In each case, state the corresponding values of \(x\) and \(y\).

6 The network below shows the lengths of roads, in miles, connecting 10 towns, \(A , B , \ldots , J\).

1. Use Dijkstra's algorithm on the network to find the shortest distance from \(A\) to \(J\). Show all your working at each vertex.
2. Write down the corresponding route.
3. A new road is to be constructed connecting \(B\) to \(G\). Find the length of this new road if the shortest distance from \(A\) to \(J\) is reduced by 10 miles. State the new route.
   (3 marks)
   \includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-12_1846_1719_861_150}

7 The diagram shows the locations of some schools. The number on each edge shows the distance, in miles, between pairs of schools.
\includegraphics[max width=\textwidth, alt={}, center]{5a414265-6273-41c5-ad5f-f6316bd774d0-14_1031_1231_428_392} Sam, an adviser, intends to travel from one school to the next until he has visited all of the schools, before returning to his starting school. The shortest distances for Sam to travel between some of the schools are shown in Table 1 opposite.

1. Complete Table 1.
2. 1. On the completed Table 1, use the nearest neighbour algorithm, starting from \(B\), to find an upper bound for the length of Sam's tour.
   2. Write down Sam's actual route if he were to follow the tour corresponding to the answer in part (b)(i).
   3. Using the nearest neighbour algorithm, starting from each of the other vertices in turn, the following upper bounds for the length of Sam's tour were obtained: 77, 77, 77, 76, 77 and 76. Write down the best upper bound. 7
3. 1. On Table 2 below, showing the order in which you select the edges, use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the schools \(A , B , C\), \(D , F\) and \(G\).
   2. Hence find a lower bound for the length of Sam's minimum tour.
   3. By deleting each of the other vertices in turn, the following lower bounds for the length of a minimum tour were found: \(50,48,52,51,56\) and 64 . Write down the best lower bound.
4. Given that the length of a minimum tour is \(T\) miles, use your answers to parts (b) and (c) to write down the smallest interval within which you know \(T\) must lie.
   (2 marks) \begin{table}[h]
   \captionsetup{labelformat=empty} \caption{Table 2}

   	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	\(\boldsymbol { C }\)	\(\boldsymbol { D }\)	\(\boldsymbol { F }\)	G
   A	-	2	6	4	16	27
   \(\boldsymbol { B }\)	2	-	8	3	15	26
   \(\boldsymbol { C }\)	6	8	-	10	22	32
   \(\boldsymbol { D }\)	4	3	10	-	12	23
   \(\boldsymbol { F }\)	16	15	22	12	-	20
   G	27	26	32	23	20	-

   \end{table}
   \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-17_2486_1714_221_153}

8 Four distinct positive integers are \(( 3 x - 5 ) , ( 2 x + 3 ) , ( x + 1 )\) and \(( 4 x - 13 )\).

1. Explain why \(x \geqslant 4\).
2. The four integers are to be sorted into ascending order using a bubble sort. The original list is
   \(\begin{array} { c c c c } ( 3 x - 5 ) & ( 2 x + 3 ) & ( x + 1 ) & ( 4 x - 13 ) \end{array}\)
   After the first pass, the list is
   \(( 3 x - 5 ) \quad ( x + 1 ) \quad ( 4 x - 13 ) \quad ( 2 x + 3 )\)
   After the second pass, the list is
   \(( x + 1 )\)
   \(( 4 x - 13 )\)
   \(( 3 x - 5 )\)
   \(( 2 x + 3 )\)
   After the third pass, the list is
   \(( 4 x - 13 ) \quad ( x + 1 )\)
   \(( 3 x - 5 )\)
   ( \(2 x + 3\) )
   1. By considering the list after the first pass, write down three inequalities in terms of \(x\).
   2. By considering the list after the second pass, write down two further inequalities in terms of \(x\).
   3. By considering the list after the third pass, write down one further inequality in terms of \(x\).
3. Hence, by considering the results above, find the value of \(x\).
   \includegraphics[max width=\textwidth, alt={}]{5a414265-6273-41c5-ad5f-f6316bd774d0-19_2486_1714_221_153}