Minimum spanning treesEdexcel International A Level Maths: Mind map

Exam questions on Minimum spanning trees

1. A network has five vertices $A$, $B$, $C$, $D$ and $E$. The arcs and their weights are $AB=7$, $AC=4$, $BC=6$, $BD=3$, $CD=8$, $CE=5$ and $DE=9$.
   Use Kruskal's algorithm to find a minimum spanning tree for the network. List the arcs in the order in which you consider them, stating whether each is accepted or rejected, and find the total weight of the tree.2 marks
2. A network has five vertices $P$, $Q$, $R$, $S$ and $T$, shown by the following distance matrix. A dash means there is no arc. The rows, in order, are: $P$: $-$, 12, 9, 15, $-$ $Q$: 12, $-$, 8, $-$, 14 $R$: 9, 8, $-$, 11, 10 $S$: 15, $-$, 11, $-$, 6 $T$: $-$, 14, 10, 6, $-$ The columns are in the same order $P$, $Q$, $R$, $S$, $T$.
   Starting at $P$, use Prim's algorithm to find a minimum spanning tree. State the order in which the arcs are added and the total weight of the tree.2 marks
3. A water company must connect six villages $A$ to $F$ with pipes. The possible pipes and their costs, in thousands of pounds, are $AB=12$, $AC=9$, $BC=7$, $BD=15$, $CD=11$, $CE=14$, $DE=6$, $DF=10$ and $EF=8$. Every village must be connected to every other village, directly or through other villages, at minimum total cost.
   Use Kruskal's algorithm to find a minimum spanning tree, showing the order in which you consider the arcs, and state the minimum cost.3 marks