Edexcel D1 (Decision Mathematics 1)

1. This question should be answered on the sheet provided.

A cable TV company wishes to link 5 villages in the Scottish Highlands. The table below shows the shortest distances, in kilometres, between these 5 villages.

1. Starting at Thurso, use Prim's algorithm to find a minimum spanning tree. You should make your method clear, indicating the order in which you selected the arcs in your final tree.
2. Calculate the minimum total length of cable required.

2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess. Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.

1. Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
2. A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.

3. \begin{figure}[h] \end{figure} Figure 1 shows a graph in which \(y \geq 0\).
Given that the graph is a weighted network,

1. find the range of values for the path of lowest weight from \(S\) to \(T\). Given instead, that the graph is a capacitated network with the numbers representing the capacity along each arc,
2. find the range of values for the maximum flow from \(S\) to \(T\).
3. Give an example of a practical problem which could be solved by using:
   1. the weighted network in part (a),
   2. the capacitated network in part (b).

4. This question should be answered on the sheet provided. The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.

1. Draw a bipartite graph to model this situation. Initially the Prime Minister matches Minister \(P\) to the post of Chancellor, \(Q\) to Foreign Secretary, \(R\) to Defence and \(T\) to Home Secretary.
2. Draw this initial matching.
3. Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used. Minister \(U\), on reflection, now expresses no interest in becoming Foreign Secretary.
4. Explain why no complete matching is now possible.
   (2 marks)

5. \begin{figure}[h] \end{figure} The network in Figure 2 represents the streets near Randolph Square in Newtown, Edinburgh. The weightings represent the average time, in seconds, taken to travel along each road in either direction. The large values for the roads \(C D\) and \(J L\) are due to traffic lights. In the course of his work, a van driver must travel along each road at least once each day. He starts and finishes at his depot, \(F\), and wishes to minimise the total time that this takes.

1. Describe an appropriate algorithm that can be used to find this minimum time.
   (3 marks)
2. Apply this algorithm to find a route that the driver can take and state the total time he can expect to spend on this journey each day.
   (5 marks)
   The section of road \(A B\) is to be turned into a pedestrian precinct.
3. Assuming that the driver must still travel along all the other roads at least once each day, find the modified time he can expect to spend on his daily journey Comment on your answer.
   (3 marks) Turn over

6. The table below shows the maximum flows possible within a system. For example, the maximum flow from \(B\) to \(A\) is 12 units.

1. Draw a digraph to represent this information.
2. Give the capacity of the cut \(\{ S , A , B , C \} \mid \{ D , T \}\).
3. Find the minimum cut, stating its capacity, and expressing it in the form \(\{ \quad \} \mid \{ \quad \}\).
4. Use the labelling procedure to find the maximum flow from \(S\) to \(T\). You should list each flow-augmenting route you find together with its flow.
5. Explain how you know that you have found the maximum possible flow.
6. Give an example of a practical situation that could be modelled by the original table.

7. A fitness centre runs introductory courses aimed at the following groups of customers: Pensioners, who will be charged \(\pounds 4\) for a 2 -hour session.
Other adults, who will be charged \(\pounds 10\) for a 4 -hour session.
Children, who will be charged \(\pounds 2\) for a 1 -hour session.
Let the number of pensioners, other adults, and children be \(x , y\) and \(z\) respectively.
Regulations state that the number of pensioners, \(x\), must be at most 5 more than the number of adults, \(y\). There must also be at least twice as many adults, \(y\), as there are children, \(z\). The centre is able to supervise up to 40 person-hours each day at the centre and wishes to maximise the revenue \(( \pounds R )\) that can be earned each day from these sessions. You may assume that the places on any courses that the centre runs will be filled.

1. Modelling this situation as a linear programming problem, write down the constraints and objective function in terms of \(x , y\) and \(z\). Using the Simplex algorithm, the following initial tableau is obtained.
2. \(\_\_\_\_\)