OCR D1 (Decision Mathematics 1) 2013 June

1 The list below is to be sorted into increasing order using bubble sort, starting at the left-hand end of the list. $$\begin{array} { l l l l l l } 24 & 57 & 9 & 31 & 16 & 4 \end{array}$$

1. Show which values are compared and which are swapped in the first pass. Write down the list that results at the end of the first pass.
2. Without showing the individual comparisons and swaps, write down the lists that result after the second pass and after the third pass.
3. In total there will be five passes made in carrying out bubble sort on the list. Write down how many swaps are made in each pass.

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. (a) Draw a connected Eulerian graph that has exactly four vertices and five arcs but is not simple.
   (b) Explain why it is not possible to have a simply connected Eulerian graph with exactly four vertices and five arcs. A simply connected Eulerian graph is drawn that has exactly eight vertices and ten arcs.
2. (a) Explain how you know that the sum of the vertex orders must be 20 .
   (b) Write down the minimum and maximum possible vertex order and draw a diagram that includes both the minimum and the maximum cases.
   (c) Draw a diagram to show a simply connected Eulerian graph with exactly eight vertices and ten arcs in which the number of vertices of order 4 is as large as possible.

3 Holly has written an algorithm.

1. Work through Holly's algorithm using the input values \(A = 30\) and \(B = 18\). Set out your working using the table in the answer book. Use one row for each step where any values change and only write down values when they change. Write down the values that are printed.
2. Describe what happens when \(A = 18\) and \(B = 30\). You need only record enough rows of the table to be able to show what happens.
3. Without doing further working, state the output values of \(F\) and \(M\) when \(A = 12\) and \(B = 8\).

4 A simplified map of an area of moorland is shown below. The vertices represent farmhouses and the arcs represent the paths between the farmhouses. The weights on the arcs show distances in km.
\includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-4_618_1420_356_319} Ted wants to visit each farmhouse and then return to his starting point.

1. In your answer book the arcs have been sorted into increasing order of weight. Use Kruskal’s algorithm to find a minimum spanning tree for the network, and give its total weight. Hence find a route visiting each farmhouse, and returning to the starting point, which has length 82 km .
2. Give the weight of the minimum spanning tree for the six vertices \(A , B , C , E , F , G\). Hence find a route visiting each of the seven farmhouses once, and returning to the starting point, which has length 81 km .
3. Show that the nearest neighbour method fails to produce a cycle through every vertex when started from \(A\) but that it succeeds when started from \(B\). Adapt this cycle to find a complete cycle of total weight less than 70 , and find the total length of the shorter cycle.

5 This question uses the same network as question 4. The total weight of the arcs in the network is 224.
\includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-5_618_1415_310_319}

1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(G\).
2. Dijkstra's algorithm has quadratic order (order \(n ^ { 2 }\) ). It takes 2.25 seconds for a certain computer to apply Dijkstra's algorithm to a network with 7 vertices. Calculate approximately how many hours it will take to apply Dijkstra's algorithm to a network with 1400 vertices.
3. How much shorter would the path \(C E\) need to be for it to become part of a shortest path from \(A\) to \(G\) ? Following a landslip, the paths \(A C\) and \(C E\) become blocked and cannot be used. A warden needs to travel along all the remaining paths to check that there are no more landslips.
4. Find the shortest distance that the warden must travel, assuming that she starts and ends at vertex \(C\). Show your working.

6 Consider the following linear programming problem.

1. Represent the constraints graphically. Shade the regions where the inequalities are not satisfied and hence identify the feasible region.
2. Calculate the coordinates of the vertices of the feasible region, apart from the origin, and calculate the value of \(P\) at each vertex. Hence find the optimal values of \(x\) and \(y\), and state the maximum value of the objective.
3. Suppose that, additionally, \(x\) and \(y\) must both be integers. Find the maximum feasible value of \(y\) for every feasible integer value of \(x\). Calculate the value of \(P\) at each of these points and hence find the optimal values of \(x\) and \(y\) with this additional restriction. Tom wants to use the Simplex algorithm to solve the original (non-integer) problem. He reformulates it as follows.

   Maximise	\(\quad P = 5 x + 8 y\),
   subject to	\(3 x - 2 y \leqslant 12\),
   	\(3 x + 4 y \leqslant 30\),
   	\(- 3 x + 8 y \leqslant 24\),
   	\(x \geqslant 0 , y \geqslant 0\).

4. Explain why Tom needed to change the third constraint.
5. Represent the problem by an initial Simplex tableau.
6. Perform one iteration of the Simplex algorithm, choosing your pivot from the \(\boldsymbol { y }\) column. Show how the pivot row was used to calculate the other rows. Write down the values of \(x , y\) and \(P\) that result from this iteration. Perform a second iteration of the Simplex algorithm to achieve the optimum point.