AQA D1 (Decision Mathematics 1) 2013 January

1

1. Draw a bipartite graph to represent the following adjacency matrix.

   	1	2	3	4	5
   A	0	0	0	0	1
   \(\boldsymbol { B }\)	0	0	0	1	1
   \(\boldsymbol { C }\)	0	1	0	1	1
   \(\boldsymbol { D }\)	0	0	0	1	1
   \(\boldsymbol { E }\)	1	1	1	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)

2

1. Use a Shell sort to arrange the following numbers into ascending order. $$\begin{array} { l l l l l l l l } 7 & 8 & 1 & 6 & 3 & 4 & 5 & 2 \end{array}$$
2. Write down the number of comparisons on the first pass.

3 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A delivery man lives in village \(A\) and is to drive along all the roads at least once before returning to \(A\).
\includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-06_1072_1027_548_502}

1. Find the length of an optimal Chinese postman route around the nine villages, starting and finishing at \(A\).
2. For an optimal Chinese postman route corresponding to your answer in part (a), state:
   1. the number of times village \(E\) would be visited;
   2. the number of times village \(I\) would be visited.

4 The following network shows the lengths, in miles, of roads connecting nine villages, \(A , B , \ldots , I\). A programme of resurfacing some roads is undertaken to ensure that each village can access all other villages along a resurfaced road, while keeping the amount of road to be resurfaced to a minimum.
\includegraphics[max width=\textwidth, alt={}, center]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-08_1008_1043_589_497}

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. Given that Prim's algorithm is used with different start vertices, state the final edge to be added to the minimum spanning tree if:
   1. the start vertex is \(E\);
   2. the start vertex is \(G\).
3. Given that Kruskal's algorithm is used to find the minimum spanning tree, state which edge would be:
   1. the first to be included in the tree;
   2. the last to be included in the tree.

5 The feasible region of a linear programming problem is defined by $$\begin{aligned} x + y & \leqslant 60
2 x + y & \leqslant 80
y & \geqslant 20
x & \geqslant 15
y & \geqslant x \end{aligned}$$

1. On the grid opposite, draw a suitable diagram to represent these inequalities and indicate the feasible region.
2. In each of the following cases, use your diagram to find the maximum value of \(P\) on the feasible region. In each case, state the corresponding values of \(x\) and \(y\).
   1. \(P = x + 4 y\)
   2. \(P = 4 x + y\)

6 The network opposite shows some roads connecting towns. The number on each edge represents the length, in miles, of the road connecting a pair of towns.

1. 1. Use Dijkstra's algorithm on the network to find the minimum distance from \(A\) to \(J\).
   2. Write down the corresponding route.
2. The road \(A J\) is a dual carriageway. Ken drives at 60 miles per hour on this road and drives at 50 miles per hour on all other roads. Find the minimum time to travel from \(A\) to \(J\).
   \includegraphics[max width=\textwidth, alt={}]{d666b2d9-cb14-4d29-a842-8c87f1b25dbd-15_2487_1714_221_152}

7

1. A simple connected graph \(X\) has eight vertices.
   1. State the minimum number of edges of the graph.
   2. Find the maximum number of edges of the graph.
2. A simple connected graph \(Y\) has \(n\) vertices.
   1. State the minimum number of edges of the graph.
   2. Find the maximum number of edges of the graph.
3. A simple graph \(Z\) has six vertices and each of the vertices has the same degree \(d\).
   1. State the possible values of \(d\).
   2. If \(Z\) is connected, state the possible values of \(d\).
   3. If \(Z\) is Eulerian, state the possible values of \(d\).

8 Tony delivers paper to five offices, \(A , B , C , D\) and \(E\). Tony starts his deliveries at office \(E\) and travels to each of the other offices once, before returning to office \(E\). Tony wishes to keep his travelling time to a minimum. The table shows the travelling times, in minutes, between the offices.

9 A factory can make three different kinds of balloon pack: gold, silver and bronze. Each pack contains three different types of balloon: \(A , B\) and \(C\). Each gold pack has 2 type \(A\) balloons, 3 type \(B\) balloons and 6 type \(C\) balloons.
Each silver pack has 3 type \(A\) balloons, 4 type \(B\) balloons and 2 type \(C\) balloons.
Each bronze pack has 5 type \(A\) balloons, 3 type \(B\) balloons and 2 type \(C\) balloons.
Every hour, the maximum number of each type of balloon available is 400 type \(A\), 400 type \(B\) and 400 type \(C\). Every hour, the factory must pack at least 1000 balloons.
Every hour, the factory must pack more type \(A\) balloons than type \(B\) balloons.
Every hour, the factory must ensure that no more than \(40 \%\) of the total balloons packed are type \(C\) balloons. Every hour, the factory makes \(x\) gold, \(y\) silver and \(z\) bronze packs.
Formulate the above situation as 6 inequalities, in addition to \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\), simplifying your answers.
(8 marks)