Edexcel D1 (Decision Mathematics 1)

1. (a) Draw the complete graph \(K _ { 5 }\).
   (b) Demonstrate that no planar drawing is possible for \(K _ { 5 }\).
   (c) Draw the complete graph \(K _ { 3,3 }\).
   (d) Demonstrate that no planar drawing is possible for \(K _ { 3,3 }\).
2. A project consists of 11 activities, some of which are dependent on others having been completed. The following precedence table summarises the relevant information.

Draw an activity network for the project. You should number the nodes and use as few dummies as possible.
(7 marks)

3. A machinist has to cut the following seven lengths (in centimetres) of steel tubing. $$\begin{array} { l l l l l l l } 150 & 104 & 200 & 60 & 184 & 84 & 120 \end{array}$$

1. Perform a quick sort to put the seven lengths in descending order. The machinist is to cut the lengths from rods that are each 240 cm long. You may assume that no waste is incurred during the cutting process.
2. Explain how to use the first-fit decreasing bin-packing algorithm to find the minimum number of rods required. Show that, using this algorithm, five rods are needed.
   (4 marks)
3. Find if it is possible to cut additional pieces with a total length of 300 cm from the five rods.
   (1 mark)

4. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 1 above shows distances in miles between 10 cities.
Use Dijkstra's algorithm to determine the shortest route, and its length, between Liverpool and Hull. You must indicate clearly:

1. the order in which you labelled the vertices,
2. how you used your labelled diagram to find the shortest route.

5. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} In Figure 2 the weight on each arc represents the cost in pounds of translating a certain document between the two languages at the nodes that it joins. You may assume that the cost is the same for translating in either direction.

1. Use Kruskal's algorithm to find the minimum cost of obtaining a translation of the document from English into each of the other languages on the network. You must show the order in which the arcs were selected.
   (4 marks)
2. It is decided that a Greek translation is not needed. Find the minimum cost if:
   1. translations to and from Greek are not available,
   2. translations to and from Greek are still available.
3. Comment on your findings. Another document is to be translated into 60 languages. It is now also necessary to take into account the fact that the cost of a translation between two languages depends on which language you start from.
4. How would you overcome the problem of having different costs for reverse translations?
5. What algorithm would be suitable to find a computerised solution.
6. State another assumption you have made in answering this question and comment on its validity.
   (2 marks) \section*{6. This question should be answered on the sheet provided.} There are 5 computers in an office, each of which must be dedicated to a single application. The computers have different specifications and the following table shows which applications each computer is capable of running.

   Computer	Applications
   E	Animation
   F	Office, Data
   G	Simulation
   H	Animation, Office
   I	Data, CAD, Simulation

1. Draw a bipartite graph to model this situation. Initially it is decided to run the Office application on computer \(F\), Animation on computer \(H\), and Data on computer \(I\).
2. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied.
3. Computer \(H\) is upgraded to allow it to run CAD. Find an alternative matching to that found in part (b).

7. An engineer makes three components \(X , Y\) and \(Z\). Relevant details are as follows: Component \(X\) requires 6 minutes turning, 3 minutes machining and 1 minute finishing. Component \(Y\) requires 15 minutes turning, 3 minutes machining and 4 minutes finishing. Component \(Z\) requires 12 minutes turning, 1 minute machining and 4 minutes finishing. The engineer gets access to 185 minutes turning, 30 minutes machining and 60 minutes finishing each day. The profits from selling components \(X , Y\) and \(Z\) are \(\pounds 40 , \pounds 90\) and \(\pounds 60\) respectively and the engineer wishes to maximise the profit from her work each day. Let the number of components \(X , Y\) and \(Z\) the engineer makes each day be \(x , y\) and \(z\) respectively.

1. Write down the 3 inequalities that apply in addition to \(x \geq 0 , y \geq 0\) and \(z \geq 0\).
2. Explain why it is not appropriate to use a graphical method to solve the problem. It is decided to use the simplex algorithm to solve the problem.
3. Show that a possible initial tableau is: Workings:
4. Workings:

   \(E\)	\(\bullet\)	\(\bullet\)	\(O\)
   \(F\)	\(\bullet\)	\(\bullet\)	\(D\)
   \(G\)	\(\bullet\)	\(\bullet\)	\(C\)
   \(H\)	\(\bullet\)	\(\bullet\)	\(A\)
   \(I\)	\(\bullet\)	\(\bullet\)	\(S\)

   Alternative matching:

   \(E\)	\(\bullet\)	\(\bullet\)	\(O\)
   \(F\)	\(\bullet\)	\(\bullet\)	\(D\)
   \(G\)	\(\bullet\)	\(\bullet\)	\(C\)
   \(H\)	\(\bullet\)	\(\bullet\)	\(A\)
   \(I\)	\(\bullet\)	\(\bullet\)	\(S\)