OCR D1 (Decision Mathematics 1) 2005 January

1 Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l l } 6 & 5 & 9 & 4 & 5 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.

2

1. A graph has six vertices; two are of order 3 and the rest are of order 4. Calculate the number of arcs in the graph, showing your working.
2. Is the graph Eulerian, semi-Eulerian or neither? Give a reason to support your answer. 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 connected, directly or indirectly, to every other vertex.
3. Explain why a simple graph with six vertices, two of order 3 and the rest of order 4, must also be a connected graph.

3 The diagram shows a network. The weights on the arcs represent distances in miles. The direct path between any two adjacent vertices is never longer than any indirect path.
\includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-02_490_748_1372_699}

1. By deleting vertex \(U\) and all arcs connected to \(U\), find a lower bound for the length of the shortest cycle that visits every vertex of this network.
2. Find a vertex that can be used as the start vertex for the nearest neighbour method to give a cycle that passes through every vertex of this network. Give your cycle and its length.

4 [Answer this question on the insert provided.]
A competition challenges teams to hike across a moor, visiting each of eight peaks, in the quickest possible time. The teams all start at peak \(A\) and finish at peak \(H\), but other than this the peaks may be visited in any order. The estimated journey times, in hours, between peaks are shown in the table. A dash in the table means that there is no direct route between two peaks.

1. Use Prim's algorithm on the table in the insert 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. What can you deduce from this answer about the quickest possible time needed to complete the challenge?
2. On the insert, draw a network to represent the information given in the table above. A team decides to visit each peak exactly once on the hike from peak \(A\) to peak \(H\).
3. Explain why the team cannot use the arc \(A C\).
4. Explain why the team must use the arc \(E F\).
5. There are only two possible routes that the team can use. Find both routes and determine which is the quicker route.

5 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries.
\includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-04_1118_816_404_662}

1. Write down four inequalities that define the feasible region. The objective is to maximise \(P = 5 x + 3 y\).
2. Using the graph or otherwise, obtain the coordinates of the vertices of the feasible region and hence find the values of \(x\) and \(y\) that maximise \(P\), and the corresponding maximum value of \(P\). The objective is changed to maximise \(Q = a x + 3 y\).
3. For what set of values of \(a\) is the maximum value of \(Q\) equal to 3?

6 Consider the linear programming problem:

1. Using slack variables, \(s\) and \(t\), express the non-trivial constraints as two equations.
2. Represent the problem as an initial Simplex tableau. Perform one iteration of the Simplex algorithm.
3. Use the Simplex algorithm to find the values of \(x , y\) and \(z\) for which \(P\) is maximised, subject to the constraints above.
4. The value 15 in the first constraint is increased to a new value \(k\). As a result the pivot for the first iteration changes. Show what effect this has on the final value of \(y\).

7 [Answer this question on the insert provided.]
The network below represents a simplified map of the centre of a small town. The arcs represent roads and the weights on the arcs represent distances, in units of 100 metres.
\includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-06_725_1259_495_443}

1. 1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest route from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. State the shortest route from \(A\) to \(E\) and the shortest route from \(A\) to \(J\), and give their lengths. [7]
   2. The shortest route from \(E\) to \(J\) that passes through every vertex can be treated as being made up of two parts, one from \(E\) to \(A\) and the other from \(A\) to \(J\). Use your answers to part (i) to write down the length of the shortest such route. List the vertices in the order that they are visited in travelling from \(E\) to \(J\) using this route.
   3. Explain why a similar approach to that used in parts (a)(i) and (a)(ii) would not give the shortest route between \(G\) and \(H\) that passes through every vertex.
2. By considering pairings of odd nodes, find the length of the shortest route that starts at \(A\) and ends at \(E\) and uses every arc at least once. \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 and 7
   Wednesday

12 JANUARY 2005
Afternoon
1 hour 30 minutes

• This insert should be used to answer Questions 4 and 7.
• Write your name, centre number and candidate number in the spaces provided at the top of this page.
• Write your answers to Questions 4 and 7 in the spaces provided in this insert, and attach it to your answer booklet.

4

1. 	\(A\)	\(B\)	C	D	\(E\)	\(F\)	G	\(H\)
   A	-	4	2	3	-	-	-	-
   \(B\)	4	-	1	-	3	-	-	-
   C	2	1	-	2	-	6	5	-
   \(D\)	3	-	2	-	-	-	4	-
   E	-	3	-	-	-	8	-	7
   \(F\)	-	-	6	-	8	-	-	8
   \(G\)	-	-	5	4	-	-	-	9
   \(H\)	-	-	-	-	7	8	9	-

2. B
   \(E\)
   \(C\)
   F
   • \(H\)
     \(A\)
     •
   • \({ } ^ { \text {F } }\)
   H D
   G
3. \(\_\_\_\_\)
4. \(\_\_\_\_\)
5. \(\_\_\_\_\)
   7 (a) (i)
   \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_191_1179_269_482} Do not cross out your working values (temporary labels)
   \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_871_1557_612_335} Shortest route from \(A\) to \(E =\) \(\_\_\_\_\) Length = \(\_\_\_\_\)
   Shortest route from \(A\) to \(J =\) \(\_\_\_\_\) Length = \(\_\_\_\_\)
6. Length of route \(=\) \(\_\_\_\_\)
   Vertices visited in order \(\_\_\_\_\)
7. Explanation \(\_\_\_\_\)
   (b) \(\_\_\_\_\)
   Length = \(\_\_\_\_\)