Spanning trees and network optimisationAQA A-Level Further Maths: Subtopic test

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

   (a)

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

   [1 mark]

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

   (b)

   What is the total weight of a minimum spanning tree?

   [1 mark]

   • A$21$
   • B$20$
   • C$23$
   • D$27$

   (c)

   Explain why Kruskal's algorithm rejects arc $CE$.

   [2 marks]

   Total for question 1: 4 marks

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

   (a)

   Which arc does Kruskal's algorithm select first?

   [1 mark]

   • A$QS$
   • B$PR$
   • C$RT$
   • D$PT$

   (b)

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

   [1 mark]

   • A$PR$, $RT$, $QR$, $QS$
   • B$PR$, $PT$, $QR$, $QS$
   • C$RT$, $QS$, $PR$, $QR$
   • D$PR$, $RT$, $RS$, $QS$

   (c)

   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]

   Total for question 2: 4 marks

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

   (a)

   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]

   (b)

   The direct link $AD$ becomes unavailable. Find the new minimum spanning tree and its total length, and state the increase in length.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A network has seven nodes $A$ to $G$. The arcs and their weights are $AB$ 7, $AD$ 5, $BC$ 8, $BD$ 9, $BE$ 7, $CE$ 5, $DE$ 15, $DF$ 6, $EF$ 8, $EG$ 9 and $FG$ 11.

   (a)

   Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order you consider them, say which you reject and why, and state the total weight.

   [6 marks]

   (b)

   Use Prim's algorithm starting at $G$ to find a minimum spanning tree. A van must travel from $G$ to $F$ along the tree arcs; compare this route with the direct arc $FG$ and comment on what this shows about minimum spanning trees.

   [6 marks]

   Total for question 4: 12 marks

End of questions