Minimum spanning treesEdexcel International A Level Maths: Subtopic test

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

   (a)

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

   [1 mark]

   • A$3$
   • B$4$
   • C$5$
   • D$7$

   (b)

   Kruskal's algorithm is applied to this network. Which arc is the first to be rejected?

   [1 mark]

   • A$BC$
   • B$CD$
   • C$DE$
   • D$AB$

   (c)

   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]

   Total for question 1: 4 marks

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

   (a)

   How many arcs does the network have?

   [1 mark]

   • A$5$
   • B$7$
   • C$8$
   • D$16$

   (b)

   Prim's algorithm is applied to the matrix starting at $P$. Which arc is chosen first?

   [1 mark]

   • A$PR$
   • B$PQ$
   • C$QR$
   • D$ST$

   (c)

   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]

   Total for question 2: 4 marks

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

   (a)

   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]

   (b)

   The pipe $BD$ already exists and must be included in the network. Find the minimum cost of a network containing $BD$, and the extra cost compared with the minimum in part (a).

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A company plans a network of fibre-optic cables between five offices $A$ to $E$. The cost in thousands of pounds of laying cable directly between two offices is given by the matrix below, where a dash means a direct link is not possible. The rows, in order, are:
   $A$: $-$, 13, 9, $-$, 17
   $B$: 13, $-$, 11, 15, $-$
   $C$: 9, 11, $-$, 8, 12
   $D$: $-$, 15, 8, $-$, 10
   $E$: 17, $-$, 12, 10, $-$
   The columns are in the same order $A$, $B$, $C$, $D$, $E$.

   (a)

   (i) State how many arcs are in the network.
   (ii) Starting at $A$, use Prim's algorithm on the matrix to find a minimum spanning tree. State the order in which the arcs are selected and the total cost.

   [6 marks]

   (b)

   A sixth office $F$ is added. Cable can be laid from $F$ to $B$ at a cost of $5$ and from $F$ to $E$ at a cost of $6$, and not directly to any other office. Use Kruskal's algorithm to find the new minimum cost. Explain why arc $BC$ is no longer needed, and why the minimum cost is unchanged.

   [6 marks]

   Total for question 4: 12 marks

End of questions