Question 2 - A-Level Maths

Exam Board	OCR
Module	D1 (Decision Mathematics 1)
Year	2015
Session	June
Topic	Permutations & Arrangements
Type	Assignment/allocation matching problems

A minimum spanning tree is constructed for a network. A vertex and all arcs joined to it are then deleted from the network. Under what circumstances will the remaining arcs of the minimum spanning tree form a minimum spanning tree for the reduced network? Joseph wants to use Kruskal's algorithm to find the minimum spanning tree for a network. He has sorted the arcs in the network by increasing order of weight. $$\begin{array} { l l l l l l l } B D = 5 & F G = 5 & D E = 6 & D F = 7 & E H = 7 & B C = 8 & D G = 8
G H = 8 & A D = 9 & C D = 9 & E G = 9 & A B = 10 & A E = 10 & C F = 10 \end{array}$$
Use Kruskal's algorithm on the list in your answer book, crossing out arcs that are not used. Draw your minimum spanning tree and give its total weight.
By considering the minimum spanning tree for the reduced network formed when vertex $A$ and all arcs joined to $A$ are deleted, find a lower bound for the shortest closed cycle through every vertex on the original network. The table shows the arc weights for the same network.
A $B$ C D E $F$ G $H$
A - 10 - 9 10 - - -
B 10 - 8 5 - - - -
C - 8 - 9 - 10 - -
D 9 5 9 - 6 7 8 -
E 10 - - 6 - 一 9 7
F - - 10 7 - - 5 -
G - - - 8 9 5 - 8
H - - - - 7 - 8 -
Apply the nearest neighbour method, starting at $A$, to find a cycle through every vertex. Hence write down an upper bound for the shortest closed cycle through every vertex on the network.