Minimum spanning treesEdexcel A-Level Further Maths: Subtopic test

1. 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$.

   (a)

   How many edges does a minimum spanning tree of this network contain?

   [1 mark]

   • A$4$
   • B$6$
   • C$9$
   • D$5$

   (b)

   In which order does Kruskal's algorithm accept edges for the minimum spanning tree?

   [1 mark]

   • A$DE$, $AC$, $CD$, $BC$, $EF$
   • B$DE$, $AC$, $CD$, $BC$, $AB$
   • C$DE$, $AC$, $CD$, $EF$, $BC$
   • D$AC$, $DE$, $CD$, $BC$, $EF$

   (c)

   Explain why Kruskal's algorithm rejects the edge $AB$.

   [2 marks]

   Total for question 1: 4 marks

2. 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$, $-$

   (a)

   How many roads (edges) are there in this network?

   [1 mark]

   • A$14$
   • B$7$
   • C$5$
   • D$10$

   (b)

   Prim's algorithm is applied starting at $A$. In which order are the arcs added?

   [1 mark]

   • A$AB$, $AC$, $CE$, $ED$
   • B$AB$, $BC$, $CD$, $DE$
   • C$AB$, $BC$, $CE$, $ED$
   • D$AB$, $BC$, $BD$, $DE$

   (c)

   The road $DE$ is closed for repairs. Find the total length of the minimum spanning tree of the remaining roads.

   [2 marks]

   Total for question 2: 4 marks

3. 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$.

   (a)

   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]

   (b)

   Use Prim's algorithm starting at $P$ to find a minimum spanning tree, giving the arcs in the order they are added. State the total cost and compare with part (a).

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Six towns $A$ to $F$ are linked by roads. The distance matrix (in km) is given row by row, with columns in the order $A$ to $F$ and a dash meaning no direct road.
   Row $A$: $-$, $11$, $15$, $13$, $9$, $-$
   Row $B$: $11$, $-$, $-$, $3$, $8$, $-$
   Row $C$: $15$, $-$, $-$, $7$, $-$, $-$
   Row $D$: $13$, $3$, $7$, $-$, $-$, $6$
   Row $E$: $9$, $8$, $-$, $-$, $-$, $11$
   Row $F$: $-$, $-$, $-$, $6$, $11$, $-$

   (a)

   Use Prim's algorithm in matrix form, starting at $A$, to find a minimum spanning tree. Give the arcs in the order they are added and the total length.

   [6 marks]

   (b)

   A student claims that the route from $A$ to $F$ along the minimum spanning tree is the shortest route from $A$ to $F$. Evaluate this claim.

   [6 marks]

   Total for question 4: 12 marks

End of questions