OCR D1 (Decision Mathematics 1) 2016 June

1 The arc weights for a network on a complete graph with six vertices are given in the following table. Apply Prim's algorithm to the table in the Printed Answer Book. Start by crossing out the row for \(A\) and choosing an entry from the column for \(A\). Write down the arcs used in the order that they are chosen. Draw the resulting minimum spanning tree and give its total weight.

2 Shaun measured the mass, in kg, of each of 9 filled bags. He then used an algorithm to sort the masses into increasing order. Shaun's list after the first pass through the sorting algorithm is given below. $$\begin{array} { l l l l l l l l l } 32 & 41 & 22 & 37 & 53 & 43 & 29 & 15 & 26 \end{array}$$

1. Explain how you know that Shaun did not use bubble sort. In fact, Shaun used shuttle sort, starting at the left-hand end of the list.
2. Write down the two possibilities for the original list.
3. Write down the list after the second pass through the shuttle sort algorithm.
4. How many passes through shuttle sort were needed to sort the entire list? Shaun's sorted list is given below. $$\begin{array} { l l l l l l l l l } 15 & 22 & 26 & 29 & 32 & 37 & 41 & 43 & 53 \end{array}$$ Shaun wants to pack the bags into bins, each of which can hold a maximum of 100 kg .
5. Write the list in decreasing order of mass and then apply the first-fit decreasing method to decide how to pack the bags into bins. Write the weights of the bags in each bin in the order that they are put into the bin.
6. Find a way to pack all the bags using only 3 bins, each of which can hold a maximum of 100 kg .

3 A problem to maximise \(P\) as a function of \(x , y\) and \(z\) is represented by the initial Simplex tableau below.

1. Write down \(P\) as a function of \(x , y\) and \(z\).
2. Write down the constraints as inequalities involving \(x , y\) and \(z\).
3. Carry out one iteration of the Simplex algorithm. After a second iteration of the Simplex algorithm the tableau is as given below.

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
   1	0	7.25	0	0.6	1.75	211
   0	1	0.75	0	0	0.25	25
   0	0	0.75	1	- 0.2	0.25	13

4. Explain how you know that the optimal solution has been achieved.
5. Write down the values of \(x , y\) and \(z\) that maximise \(P\). Write down the optimal value of \(P\).

4 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 joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected. Molly says that she has drawn a graph with exactly five vertices, having vertex orders 1, 2, 3, 4 and 5.

1. State how you know that Molly is wrong. Holly has drawn a connected graph with exactly six vertices, having vertex orders 2, 2, 2, 2, 4 and 6.
2. (a) Explain how you know that Holly’s graph is not simply connected.
   (b) Determine whether Holly's graph is Eulerian, semi-Eulerian or neither, explaining how you know which of these it is. Olly has drawn a simply connected graph with exactly six vertices.
3. (a) State the minimum possible value of the sum of the vertex orders in Olly's graph.
   (b) If Olly's graph is also Eulerian, what numerical values can the vertex orders take? Polly has drawn a simply connected Eulerian graph with exactly six vertices and exactly ten arcs.
4. (a) What can you deduce about the vertex orders in Polly's graph?
   (b) Draw a graph that fits the description of Polly's graph.

5 The network below represents a single-track railway system. The vertices represent stations, the arcs represent railway tracks and the weights show distances in km. The total length of the arcs shown is 60 km .
\includegraphics[max width=\textwidth, alt={}, center]{d783915d-5950-4a97-b6a0-70959214e218-5_442_1152_429_459}

1. Apply Dijkstra's algorithm to the network, starting at \(G\), to find the shortest distance (in km ) from \(G\) to \(N\) and write down the route of this shortest path. Greg wants to travel from the station represented by vertex \(G\) to the station represented by vertex \(N\). He especially wants to include the track \(K L\) (in either direction) in his journey.
2. Show how to use your working from part (i) to find the shortest journey that Greg can make that fulfils his requirements. Write down his route. Percy Li needs to check each track to see if any maintenance is required. He wants to start and end at the station represented by vertex \(G\) and travel in one continuous route that passes along each track at least once. The direction of travel along the tracks does not matter.
3. Apply the route inspection algorithm, showing your working, to find the minimum distance that Percy will need to travel. Write down those arcs that Percy will need to repeat. If he travels this minimum distance, how many times will Percy travel through the station represented by vertex \(L\) ?

6 William is making the bridesmaid dresses and pageboy outfits for his sister's wedding. He expects it to take 20 hours to make each bridesmaid dress and 15 hours to make each pageboy outfit. Each bridesmaid dress uses 8 metres of fabric. Each pageboy outfit uses 3 metres of fabric. The fabric costs \(\pounds 8\) per metre. Additional items cost \(\pounds 35\) for each bridesmaid dress and \(\pounds 80\) for each pageboy outfit. William's sister wants to have at least one bridesmaid and at least one pageboy. William has 100 hours available and must not spend more than \(\pounds 600\) in total on materials. Let \(x\) denote the number of bridesmaids and \(y\) denote the number of pageboys.

1. Show why the constraint \(4 x + 3 y \leqslant 20\) is needed and write down three more constraints on the values of \(x\) and \(y\), other than that they must be integers.
2. Plot the feasible region where all four constraints are satisfied. William's sister wants to maximise the total number of attendants (bridesmaids and pageboys) at her wedding.
3. Use your graph to find the maximum number of attendants.
4. William costs his time at \(\pounds 15\) an hour. Find, and simplify, an expression, in terms of \(x\) and \(y\), for the total cost (for all materials and William’s time). Hence find, and interpret, the minimum cost solution to part (iii).

7 A tour guide wants to find a route around eight places of interest: Queen Elizabeth Olympic Park ( \(Q\) ), Royal Albert Hall ( \(R\) ), Statue of Eros ( \(S\) ), Tower Bridge ( \(T\) ), Westminster Abbey ( \(W\) ), St Paul's Cathedral ( \(X\) ), York House ( \(Y\) ) and Museum of Zoology ( \(Z\) ). The table below shows the travel times, in minutes, from each of the eight places to each of the other places.

1. Use the nearest neighbour method to find an upper bound for the minimum time to travel to each of the eight places, starting and finishing at \(Y\). Write down the route and give the time in minutes.
2. The Answer Book lists the arcs by increasing order of weight (reading across the rows). Apply Kruskal's algorithm to this list to find the minimum spanning tree for all eight places. Draw your tree and give its total weight.
3. (a) Vertex \(Q\) and all arcs joined to \(Q\) are temporarily removed. Use your answer to part (ii) to write down the weight of the minimum spanning tree for the seven vertices \(R , S , T , W , X , Y\) and \(Z\).
   (b) Use your answer to part (iii)(a) to find a lower bound for the minimum time to travel to each of the eight places of interest, starting and finishing at \(Y\). The tour guide allows for a 5 -minute stop at each of \(S\) and \(Y\), a 10 -minute stop at \(T\) and a 30 -minute stop at each of \(Q , R , W , X\) and \(Z\). The tour guide wants to find a route, starting and ending at \(Y\), in which the tour (including the stops) can be completed in five hours (300 minutes).
4. Use the nearest neighbour method, starting at \(Q\), to find a closed route through each vertex. Hence find a route for the tour, showing that it can be completed in time.