Spanning trees and network optimisation

Spanning trees and network optimisation Test

Spec DB1–DB2 · AQA A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

AQA A-Level Further Maths

Spanning trees and network optimisation

Total 27 marks

Name

Class

Date

  1. 1
    A network has six nodes AA to FF. The arcs and their weights are ABAB 6, ACAC 9, BCBC 4, BDBD 8, CDCD 5, CECE 7, DEDE 3, DFDF 10 and EFEF 2.
    (a)
    How many arcs does a spanning tree of this network contain?
    [1 mark]
    • A66
    • B99
    • C44
    • D55
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    What is the total weight of a minimum spanning tree?
    [1 mark]
    • A2121
    • B2020
    • C2323
    • D2727
    Show the mark scheme

    Mark scheme

    Answer: B
    (c)
    Explain why Kruskal's algorithm rejects arc CECE.
    [2 marks]
    Show the mark scheme

    Mark scheme

    R1: when CECE (weight 7) is considered, CC and EE are already connected through CC–DD–EE (CDCD 5 and DEDE 3 are already chosen)
    R1: adding
    CECE would form a cycle, and a tree has no cycles

    Total for question 1: 4 marks

  2. 2
    Five villages P,Q,R,S,TP,Q,R,S,T are to be linked by cables. The possible links and their costs, in hundreds of pounds, are PQPQ 12, PRPR 8, PSPS 15, PTPT 9, QRQR 10, QSQS 7, QTQT 14, RSRS 11, RTRT 6 and STST 13.
    (a)
    Which arc does Kruskal's algorithm select first?
    [1 mark]
    • AQSQS
    • BPRPR
    • CRTRT
    • DPTPT
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    Prim's algorithm is applied starting at PP. In which order are the arcs added?
    [1 mark]
    • APRPR, RTRT, QRQR, QSQS
    • BPRPR, PTPT, QRQR, QSQS
    • CRTRT, QSQS, PRPR, QRQR
    • DPRPR, RTRT, RSRS, QSQS
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Explain why Prim's algorithm starting at PP does not select arc QSQS, with weight 7, until the last step, even though it is lighter than arc PRPR.
    [2 marks]
    Show the mark scheme

    Mark scheme

    R1: Prim's algorithm only considers arcs that join a node already in the tree to a node not yet in it
    R1: neither
    QQ nor SS is in the tree until QRQR is added, so QSQS cannot be considered before then

    Total for question 2: 4 marks

  3. 3
    Five towns AA to EE 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,EA,B,C,D,E, are given by (05948506739602104720118310110)\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 AA, to find a minimum spanning tree. State the order in which the arcs are added and the total length.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: start at AA and choose the shortest arc from AA: ADAD (4)
    A1: then
    CDCD (2), ABAB (5), BEBE (3) in that order
    B1: total length 14 km
    (b)
    The direct link ADAD becomes unavailable. Find the new minimum spanning tree and its total length, and state the increase in length.
    [4 marks]
    Show the mark scheme

    Mark scheme

    M1: apply Kruskal's or Prim's algorithm with ADAD removed
    A1: arcs
    CDCD (2), BEBE (3), ABAB (5), BCBC (6)
    B1: total length 16 km

    B1: an increase of 2 km on the original 14 km

    Total for question 3: 7 marks

  4. 4
    A network has seven nodes AA to GG. The arcs and their weights are ABAB 7, ADAD 5, BCBC 8, BDBD 9, BEBE 7, CECE 5, DEDE 15, DFDF 6, EFEF 8, EGEG 9 and FGFG 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]
    Show the mark scheme

    Mark scheme

    M1: arcs considered in ascending order of weight
    B1: accept
    ADAD 5, CECE 5, DFDF 6
    B1: accept
    ABAB 7, BEBE 7
    R1: reject
    BCBC 8 and EFEF 8, each of which would form a cycle (B,E,CB,E,C and E,B,A,D,FE,B,A,D,F respectively)
    B1: accept
    EGEG 9 (after rejecting BDBD 9, which would form a cycle)
    A1: total weight 39

    Accept: ties in either order
    (b)
    Use Prim's algorithm starting at GG to find a minimum spanning tree. A van must travel from GG to FF along the tree arcs; compare this route with the direct arc FGFG and comment on what this shows about minimum spanning trees.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: start at GG and choose EGEG 9, the lighter of EGEG 9 and FGFG 11
    A1: arcs added in the order
    EGEG, CECE, BEBE, ABAB, ADAD, DFDF
    B1: total weight 39, the same as in (a)

    M1: tree route from
    GG to FF is G,E,B,A,D,FG,E,B,A,D,F with weight 9+7+7+5+69+7+7+5+6
    B1: this is 34, compared with 11 for the direct arc
    FGFG
    R1: a minimum spanning tree minimises the total weight of the whole tree, not the distance between a particular pair of nodes, so it does not give shortest routes

    Total for question 4: 12 marks

End of questions

Subtopic tests