OCR Further Discrete (Further Discrete) 2019 June

1 Two graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. 1. Prove that the graphs are isomorphic.
   2. Verify that Euler's formula holds for graph G1.
2. Describe how it is possible to add 4 arcs to graph G1 to make a non-planar graph with 5 vertices.
3. Describe how it is possible to add a vertex U and 4 arcs to graph G 2 to make a connected nonplanar graph with 6 vertices.

2 A project is represented by the activity network and cascade chart below. The table showing the number of workers needed for each activity is incomplete. Each activity needs at least 1 worker.
\includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_202_565_1605_201}
\includegraphics[max width=\textwidth, alt={}, center]{7717b4ca-45ab-4111-9f59-5a3abb04b388-2_328_560_1548_820}

1. Complete the table in the Printed Answer Booklet to show the immediate predecessors for each activity.
2. Calculate the latest start time for each non-critical activity. The minimum number of workers needed is 5 .
3. What type of problem (existence, construction, enumeration or optimisation) is the allocation of a number of workers to the activities? There are 8 workers available who can do activities A and B .
4. 1. Find the number of ways that the workers for activity A can be chosen.
   2. When the workers have been chosen for activity A , find the total number of ways of choosing the workers for activity B for all the different possible values of x , where \(\mathrm { x } \geqslant 1\).

3 A problem is represented as the initial simplex tableau below.

1. Write the problem as a linear programming formulation in the standard algebraic form with no slack variables.
2. Carry out one iteration of the simplex algorithm.
3. Show algebraically how each row of the tableau found in part (b) is calculated.

4 An algorithm must have an input, an output, be deterministic and finite.

1. Why is a counter sometimes used in an algorithm? A computer takes 0.2 seconds to sort a list of 500 numbers.
2. How long would you expect the computer to take to sort a list of 5000 numbers? Simon says that he can sort a list of numbers 'just by looking at them'.
3. Explain to Simon why sorting algorithms are needed.
4. Demonstrate how quick sort works by using it to sort the following list into increasing order. You should indicate the pivots used and which values are already known to be in their correct position.
   \(\begin{array} { l l l l l } 41 & 17 & 8 & 33 & 29 \end{array}\) For an average case the efficiency of quick sort is O (nlogn), where n is the number of items in the list.
5. Explain why quick sort is typically quicker than bubble sort and shuttle sort. When the number of comparisons made is used as a measure of the efficiency, the worst case for quick sort is no more efficient than the worst case for bubble sort. An arrangement of the five numbers from part (d) makes up a new list that is to be sorted using the bubble sort or the quick sort.
6. Without writing out all the passes, determine
   • the worst case list
   • the total number of comparisons for the worst case list
     for each of the algorithms in turn.

5 A network is represented by the distance matrix below. For this network a direct connection between two vertices is always shorter than an indirect connection.

1. How does the distance matrix show that the arcs are undirected? The shortest distance from A to E is 180 .
2. Write down the shortest route from A to E .
3. Use Dijkstra's algorithm on the distance matrix to find the length of the shortest route from \(\mathbf { G }\) to each of the other vertices. The arcs represent roads and the weights represent distances in metres. The total length of all the roads is 1610 metres. Emily and Stephen have set up a company selling ice-creams from a van.
4. Emily wants to deliver leaflets to the houses along each side of each road. Find the length of the shortest continuous route that Emily can use.
5. Stephen wants to drive along each road in the ice-cream van.
   1. Determine the length of the shortest route for Stephen if he starts at B.
   2. Stephen wants to use the shortest possible route.
      • Find the length of the shortest possible route.
6. Write down the start and end vertices of this route.

6 The pay-off matrix for a game between two players, Sumi and Vlad, is shown below. If Sumi plays A and Vlad plays X then Sumi gets X points and Vlad gets 1 point. Sumi You are given that cell ( \(\mathrm { A } , \mathrm { X }\) ) is a Nash Equilibrium solution.

1. Find the range of possible values of X .
2. Explain what the statement 'cell (A, X) is a Nash Equilibrium solution' means for each player.
3. Find a cell where each player gets their maximin pay-off. Suppose, instead, that the game can be converted to a zero-sum game.
4. Determine the optimal strategy for Sumi for the zero-sum game.
   • Record the pay-offs for Sumi when the game is converted to a zero-sum game.
   • Describe how Sumi should play using this strategy.

7 Sam is making pies.
There is exactly enough pastry to make 7 large pies or 20 medium pies or 36 small pies, or some mixture of large, medium and small pies. This is represented as a constraint \(180 x + 63 y + 35 z \leqslant 1260\).

1. Write down what \(\mathrm { X } , \mathrm { Y }\) and Z represent. There is exactly enough filling to make 5 large pies or 12 medium pies or 18 small pies, or some mixture of large, medium and small pies.
2. Express this as a constraint of the form \(a x + b y + c z \leqslant d\), where \(a , b , c\) and \(d\) are integers. The number of small pies must equal the total number of large and medium pies.
3. Show that making exactly 9 small pies is inconsistent with the constraints.
4. Determine the maximum number of large pies that can be made.
   • Your reasoning should be in the form of words, calculations or algebra.
   • You must check that your solution is feasible.