Spanning trees and network optimisationAQA A-Level Further Maths: Mind map

Exam questions on Spanning trees and network optimisation

1. A network has six nodes $A$ to $F$. The arcs and their weights are $AB$ 6, $AC$ 9, $BC$ 4, $BD$ 8, $CD$ 5, $CE$ 7, $DE$ 3, $DF$ 10 and $EF$ 2.
   Explain why Kruskal's algorithm rejects arc $CE$.2 marks
2. Five villages $P,Q,R,S,T$ are to be linked by cables. The possible links and their costs, in hundreds of pounds, are $PQ$ 12, $PR$ 8, $PS$ 15, $PT$ 9, $QR$ 10, $QS$ 7, $QT$ 14, $RS$ 11, $RT$ 6 and $ST$ 13.
   Explain why Prim's algorithm starting at $P$ does not select arc $QS$, with weight 7, until the last step, even though it is lighter than arc $PR$.2 marks
3. Five towns $A$ to $E$ are to be connected by cable laid along direct links. The distances in km between the towns, with rows and columns in the order $A,B,C,D,E$, are given by $\begin{pmatrix} 0&5&9&4&8 \\ 5&0&6&7&3 \\ 9&6&0&2&10 \\ 4&7&2&0&11 \\ 8&3&10&11&0 \end{pmatrix}$. The cable is to have the least possible total length.
   Use Prim's algorithm, starting at $A$, to find a minimum spanning tree. State the order in which the arcs are added and the total length.3 marks