OCR D1 (Decision Mathematics 1) 2007 June

1 Two graphs A and B are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Write down an example of a cycle on graph A .
2. W hy is \(\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }\) not a path on graph B ?
3. How many arcs would there be in a spanning tree for graph A ?
4. For each graph state whether it is Eulerian, semi-Eulerian or neither.
5. The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph? An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.
6. Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?

2 A landscape gardener is designing a garden. Part of the garden will be decking, part will be flowers and the rest will be grass. Let d be the area of decking, f be the area of flowers and g be the area of grass, all measured in \(\mathrm { m } ^ { 2 }\). The total area of the garden is \(120 \mathrm {~m} ^ { 2 }\) of which at least \(40 \mathrm {~m} ^ { 2 }\) must be grass. The area of decking must not be greater than the area of flowers. Also, the area of grass must not be more than four times the area of decking. Each square metre of grass will cost \(\pounds 5\), each square metre of decking will cost \(\pounds 10\) and each square metre of flowers will cost \(\pounds 20\). These costs include labour. The landscape gardener has been instructed to come up with the design that will cost the least.

1. Write down a constraint in d , f and g from the total area of the garden.
2. Explain why the constraint \(\mathrm { g } \leqslant 4 \mathrm {~d}\) is required.
3. Write down a constraint from the requirement that the area of decking must not be greater than the area of flowers.
4. Write down a constraint from the requirement that at least \(40 \mathrm {~m} ^ { 2 }\) of the garden must be grass and write down the minimum feasible values for each of \(d\) and \(f\).
5. Write down the objective function to be minimised.
6. Write down the resulting LP problem, using slack variables to express the constraints from parts (ii) and (iii) as equations.
   (You are not required to solve the resulting LP problem.)

3

1. Use shuttle sort to sort the five numbers 8, 6, 9, 7, 5 into increasing order. Write down the list that results at the end of each pass. Calculate and record the number of comparisons and the number of swaps that are made in each pass.
2. The algorithm below is part of another method for sorting a list into increasing order. A pply it to the list 8, 6, 9, 7, 5. Show the result of each step. Step 1: Input the original list and call it list A.
   Step 2: Remove the first item in list \(A\) and call this item \(X\).
   Step 3: If the first item remaining in list A is less than X move it to list B , otherwise move it to list C.
   Step 4: If the next item remaining in list A is less than X move it to become the next item in list B, otherwise move it to become the next item in list C.
   Step 5: If there are still items in list A, repeat Step 4.
   Step 6: Count the number of items in list \(\mathbf { B }\) and call this \(\mathbf { N }\).
   Step 7: Put the items in list B at positions 1 to N of list A, item X at position \(\mathrm { N } + 1\) of list A and the items in list C at positions \(\mathrm { N } + 2\) onwards of list A.
   Step 8: Display list A.

4 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 3 x - 5 y ,
\text { subject to } & x + 5 y \leqslant 12 ,
& x - 5 y \leqslant 10 ,
& 3 x + 10 y \leqslant 45 ,
\text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$

1. Represent the problem as an initial Simplex tableau.
2. Identify the entry on which to pivot for the first iteration of the Simplex algorithm. Explain how you made your choice of column and row.
3. Perform oneiteration of the Simplex algorithm. Write down the values of \(\mathrm { x } , \mathrm { y }\) and P after this iteration.
4. Show that \(\mathrm { x } = 11 , \mathrm { y } = 0.2\) is a feasible solution and that it gives a bigger value of P than that in part (iii).

5 Answer this question on the insert provided. The network below represents a simplified map of a building. The arcs represent corridors and the weights on the arcs represent the lengths of the corridors, in metres. The sum of the weights on the arcs is 765 metres.
\includegraphics[max width=\textwidth, alt={}, center]{dbf782dd-879c-4f0f-b532-246a0db9f130-5_1271_1539_584_303}

1. Janice is the cleaning supervisor in the building. She is at the position marked as J when she is called to attend a cleaning emergency at B. On the network in the insert, use Dijkstra's algorithm, starting from vertex J and continuing until B is given a permanent label, to find the shortest path from J to B and the length of this path.
2. In her job J anice has to walk along each of the corridors represented on the network. This requires finding a route that covers every arc at least once, starting and ending at J. Showing all your working, find the shortest distance that J anice must walk to check all the corridors. The labelled vertices represent 'cleaning stations'. J anice wants to visit every cleaning station using the shortest possible route. She produces a simplified network with no repeated arcs and no arc that joins a vertex to itself.
3. On the insert, complete Janice's simplified network. Which standard network problem does Janice need to solve to find the shortest distance that she must travel?

6 Answer this question on the insert provided. The table shows the distances, in miles, along the direct roads between six villages, \(A\) to \(F\). A dash ( - ) indicates that there is no direct road linking the villages.

1. On the table in the insert, use Prim's algorithm to find a minimum spanning tree. Start by crossing out row A. Show which entries in the table are chosen and indicate the order in which the rows are deleted. Draw your minimum spanning tree and state its total weight.
2. By deleting vertex B and the arcs joined to vertex B, calculate a lower bound for the length of the shortest cycle through all the vertices.
3. A pply the nearest neighbour method to the table above, starting from \(F\), to find a cycle that passes through every vertex and use this to write down an upper bound for the length of the shortest cycle through all the vertices.
   \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}