OCR MEI D1 (Decision Mathematics 1) 2013 June

1 The adjacency graph for a map has a vertex for each country. Two vertices are connected by an arc if the corresponding countries share a border.

1. Draw the adjacency graph for the following map of four countries. The graph is planar and you should draw it with no arcs crossing.
   \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_531_1486_561_292}
2. Number the regions of your planar graph, including the outside region. Regarding the graph as a map, draw its adjacency graph.
3. Repeat parts (i) and (ii) for the following map.
   \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-2_533_1484_1361_294}

2 The instructions labelled 1 to 7 describe the steps of a sorting algorithm applied to a list of six numbers.
1 Let \(i\) equal 1.
2 Repeat lines 3 to 7, stopping when \(i\) becomes 6 .

3 Let \(j\) equal 1.

4 Repeat lines 5 and 6 , until \(j\) becomes \(7 - i\).

5 If the \(j\) th number in the list is bigger than the \(( j + 1 )\) th, then swap them.

6 Let the new value of \(j\) be \(j + 1\).

7 Let the new value of \(i\) be \(i + 1\).

1. Apply the sorting algorithm to the list of numbers shown below. Record in the table provided the state of the list after each pass. Record the number of comparisons and the number of swaps that you make in each pass. (The result of the first pass has already been recorded.) List: \(\begin{array} { l l l l l l } 9 & 11 & 7 & 3 & 13 & 5 \end{array}\)
2. Suppose now that the list is split into two sublists, \(\{ 9,11,7 \}\) and \(\{ 3,13,5 \}\). The sorting algorithm is adapted to apply to three numbers, and is applied to each sublist separately. This gives \(\{ 7,9,11 \}\) and \(\{ 3,5,13 \}\). How many comparisons and swaps does this need?
3. How many further swaps would the original algorithm need to sort the revised list \(\{ 7,9,11,3,5,13 \}\) into increasing order? 3 The network below represents a number of villages together with connecting roads. The numbers on the arcs represent distances (in miles).
   \includegraphics[max width=\textwidth, alt={}, center]{e528b905-7419-44b6-b700-4c04ad96c816-3_684_785_1612_625}
4. Use Dijkstra's algorithm to find the shortest routes from A to each of the other villages. Give these shortest routes and the corresponding distances. Traffic in the area travels at 30 mph . An accident delays all traffic passing through C by 20 minutes.
5. Describe how the network can be adapted and used to find the fastest journey time from A to F .