OXFORD CAMBRIDGE AND RSA EXAMINATIONS
Advanced Subsidiary General Certificate of Education
Advanced General Certificate of Education
MATHEMATICS
4736
Decision Mathematics 1
Wednesday
12 JANUARY 2005
Afternoon
1 hour 30 minutes
Additional materials:
Answer booklet
Graph paper
List of Formulae (MF1)
TIME
1 hour 30 minutes
INSTRUCTIONS TO CANDIDATES
•
Write your name, centre number and candidate number in the spaces provided on the answer
booklet.
•
Answer all the questions.
•
There is an insert for use in Questions 4 and 7.
•
Give non-exact numerical answers correct to 3 significant figures unless a different degree of
accuracy is specified in the question or is clearly appropriate.
•
You are permitted to use a graphical calculator in this paper.
INFORMATION FOR CANDIDATES
•
The number of marks is given in brackets [ ] at the end of each question or part question.
•
The total number of marks for this paper is 72.
•
Questions carrying smaller numbers of marks are printed earlier in the paper, and questions carrying
larger numbers of marks later in the paper.
•
You are reminded of the need for clear presentation in your answers.
This question paper consists of 6 printed pages, 2 blank pages and an insert.
© OCR 2005 [M/102/2697]
Registered Charity Number: 1066969
[Turn over
2
1
Use the shuttle sort algorithm to sort the list
6
5
9
4
5
2
into increasing order. Write down the list that results from each pass through the algorithm.
[5]
2
(i) 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]
(ii) Is the graph Eulerian, semi-Eulerian or neither? Give a reason to support your answer.
[1]
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.
(iii) Explain why a simple graph with six vertices, two of order 3 and the rest of order 4, must also be
a connected graph.
[2]
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.
(i) 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.
[3]
(ii) 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]
4736/Jan05
3
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.
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
−
(i) 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?
[5]
(ii) On the insert, draw a network to represent the information given in the table above.
[2]
A team decides to visit each peak exactly once on the hike from peak A to peak H.
(iii) Explain why the team cannot use the arc AC.
[1]
(iv) Explain why the team must use the arc EF.
[1]
(v) There are only two possible routes that the team can use. Find both routes and determine which
is the quicker route.
[3]
4736/Jan05
[Turn over
4
5
The constraints of a linear programming problem are represented by the graph below. The feasible
region is the unshaded region, including its boundaries.
(i) Write down four inequalities that define the feasible region.
[3]
The objective is to maximise P = 5x + 3y.
(ii) 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.
[6]
The objective is changed to maximise Q = ax + 3y.
(iii) For what set of values of a is the maximum value of Q equal to 3?
[4]
4736/Jan05
5
6
Consider the linear programming problem:
maximise
P = 2x −5y −,
subject to
5x + 3y −5 ≤15,
2x + 6y + 8 ≤24,
and
x ≥0, y ≥0, ≥0.
(i) Using slack variables, s and t, express the non-trivial constraints as two equations.
[1]
(ii) Represent the problem as an initial Simplex tableau.
Perform one iteration of the Simplex
algorithm.
[6]
(iii) Use the Simplex algorithm to find the values of x, y and for which P is maximised, subject to
the constraints above.
[4]
(iv) 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.
[2]
4736/Jan05
[Turn over
