Minimum spanning treesEdexcel A-Level Further Maths: Mind map

Exam questions on Minimum spanning trees

1. A network has six vertices $A$, $B$, $C$, $D$, $E$ and $F$. Its edges and weights are $AB=7$, $AC=4$, $BC=6$, $BD=9$, $CD=5$, $CE=8$, $DE=3$, $DF=12$ and $EF=10$.
   Explain why Kruskal's algorithm rejects the edge $AB$.2 marks
2. Five towns $A$, $B$, $C$, $D$, $E$ are linked by roads. The distance matrix (in km) is given row by row, with columns in the order $A$ to $E$ and a dash meaning no direct road. Row $A$: $-$, $6$, $9$, $-$, $-$ Row $B$: $6$, $-$, $4$, $8$, $-$ Row $C$: $9$, $4$, $-$, $7$, $5$ Row $D$: $-$, $8$, $7$, $-$, $3$ Row $E$: $-$, $-$, $5$, $3$, $-$
   The road $DE$ is closed for repairs. Find the total length of the minimum spanning tree of the remaining roads.2 marks
3. A company must connect six villages $P$, $Q$, $R$, $S$, $T$ and $U$ with cable. The possible links and their costs, in thousands of pounds, are $PQ=14$, $PR=9$, $QR=11$, $QS=8$, $RS=12$, $RT=10$, $ST=6$, $SU=13$ and $TU=7$.
   Use Kruskal's algorithm to find a minimum spanning tree, listing the edges in the order they are considered and stating which are accepted and which rejected.3 marks