OCR D1 (Decision Mathematics 1) Specimen

1 The graph \(\mathrm { K } _ { 5 }\) has five nodes, \(A , B , C , D\) and \(E\), and there is an arc joining every node to every other node.

1. Draw the graph \(\mathrm { K } _ { 5 }\) and state how you know that it is Eulerian.
2. By listing the arcs involved, give an example of a path in \(\mathrm { K } _ { 5 }\). (Your path must include more than one arc.)
3. By listing the arcs involved, give an example of a cycle in \(\mathrm { K } _ { 5 }\).

2 This question is about a simply connected network with at least three arcs joining 4 nodes. The weights on the arcs are all different and any direct paths always have a smaller weight than the total weight of any indirect paths between two vertices.

1. Kruskal's algorithm is used to construct a minimum connector. Explain why the arcs with the smallest and second smallest weights will always be included in this minimum connector.
2. Draw a diagram to show that the arc with the third smallest weight need not always be included in a minimum connector.

3

1. Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l } 6 & 3 & 8 & 3 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.
2. Shuttle sort is a quadratic order algorithm. Explain briefly what this statement means.

4 [Answer this question on the insert provided.]
An algorithm involves the following steps.
Step 1: Input two positive integers, \(A\) and \(B\).
Let \(C = 0\)
Step 2: If \(B\) is odd, replace \(C\) by \(C + A\).
Step 3: If \(B = 1\), go to step 6.
Step 4: Replace \(A\) by \(2 A\).
If \(B\) is even, replace \(B\) by \(B \div 2\), otherwise replace \(B\) by ( \(B - 1\) ) ÷ 2 .
Step 5: Go back to step 2.
Step 6: Output the value of \(C\).

1. Demonstrate the use of the algorithm for the inputs \(A = 6\) and \(B = 13\).
2. When \(B = 8\), what is the output in terms of \(A\) ? What is the relationship between the output and the original inputs?

5 [Answer this question on the insert provided.]
\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-3_659_1002_324_609} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the shortest distances in kilometres.

1. The diagram on the insert shows the result of deleting vertex \(F\) and all the arcs joined to \(F\). Show that a lower bound for the length of the travelling salesperson problem on the original network is 38 km . The corresponding lower bounds by deleting each of the other vertices are: $$A : 40 \mathrm {~km} , \quad B : 39 \mathrm {~km} , \quad C : 35 \mathrm {~km} , \quad D : 37 \mathrm {~km} , \quad E : 35 \mathrm {~km} \text {. }$$ The route \(A - B - C - D - E - F - A\) has length 47 km .
2. Using only this information, what are the best upper and lower bounds for the length of the solution to the travelling salesperson problem on the network?
3. By considering the orders in which vertices \(C , D\) and \(E\) can be visited, find the best upper bound given by a route of the form \(A - B - \ldots - F - A\).

6 [Answer part (i) of this question on the insert provided.]
The diagram shows a simplified version of an orienteering course. The vertices represent checkpoints and the weights on the arcs show the travel times between checkpoints, in minutes.
\includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-4_483_931_461_630}

1. Use Dijkstra's algorithm, starting from checkpoint \(\boldsymbol { A }\), to find the least travel time from \(A\) to \(D\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels were assigned. Give the route that takes the least time from \(A\) to \(D\).
2. By using an appropriate algorithm, find the least time needed to travel every arc in the diagram starting and ending at \(A\). You should show your method clearly.
3. Starting from \(A\), apply the nearest neighbour algorithm to the diagram to find a cycle that visits every checkpoint. Use your solution to find a path that visits every checkpoint, starting from \(A\) and finishing at \(D\).

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

1. Represent the constraints graphically, shading out the regions where the inequalities are not satisfied. Calculate the value of \(x\) and the value of \(y\) at each of the vertices of the feasible region. Hence find the maximum value of \(P\), clearly indicating where it occurs.
2. By introducing slack variables, represent the problem as an initial Simplex tableau and use the Simplex algorithm to solve the problem.
3. Indicate on your diagram for part (i) the points that correspond to each stage of the Simplex algorithm carried out in part (ii). \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
   4736
   Decision Mathematics 1
   INSERT for Questions 4, 5 and 6
   Specimen Paper
   • This insert should be used to answer Questions 4, 5 and 6
   • .
   • Write your Name, Centre Number and Candidate Number in the spaces provided at the top of this page.
   • Write your answers to Questions 4, 5 and 6
   • in the spaces provided in this insert, and attach it to your answer booklet.
   4

4. STEP	A	\(B\)	C
   1
   2

5. STEP	A	\(B\)	C
   1
   2

   5
6. 
   \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-7_661_1004_285_557}
7. Upper bound = \(\_\_\_\_\) km Lower bound = \(\_\_\_\_\) km
8. \(\_\_\_\_\)
   Best upper bound = \(\_\_\_\_\) km 6
9. 
   \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_668_1406_292_406}
   \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_307_1342_1014_424}
   Least travel time = \(\_\_\_\_\) minutes Route: A- \(\_\_\_\_\) \(- D\)