Minimum spanning trees

Minimum spanning trees Test

Spec 2.1 · Edexcel 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

Edexcel A-Level Further Maths

Minimum spanning trees

Total 27 marks

Name

Class

Date

  1. 1
    A network has six vertices AA, BB, CC, DD, EE and FF. Its edges and weights are AB=7AB=7, AC=4AC=4, BC=6BC=6, BD=9BD=9, CD=5CD=5, CE=8CE=8, DE=3DE=3, DF=12DF=12 and EF=10EF=10.
    (a)
    How many edges does a minimum spanning tree of this network contain?
    [1 mark]
    • A44
    • B66
    • C99
    • D55
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    In which order does Kruskal's algorithm accept edges for the minimum spanning tree?
    [1 mark]
    • ADEDE, ACAC, CDCD, BCBC, EFEF
    • BDEDE, ACAC, CDCD, BCBC, ABAB
    • CDEDE, ACAC, CDCD, EFEF, BCBC
    • DACAC, DEDE, CDCD, BCBC, EFEF
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Explain why Kruskal's algorithm rejects the edge ABAB.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: by the time AB(7)AB(7) is considered, AA and BB are already connected (via ACAC and BCBC)
    A1: adding
    ABAB would create a cycle A−B−C−AA-B-C-A
    Accept:
    AA and BB are already in the same component

    Total for question 1: 4 marks

  2. 2
    Five towns AA, BB, CC, DD, EE are linked by roads. The distance matrix (in km) is given row by row, with columns in the order AA to EE and a dash meaning no direct road.
    Row
    AA: −-, 66, 99, −-, −-
    Row
    BB: 66, −-, 44, 88, −-
    Row
    CC: 99, 44, −-, 77, 55
    Row
    DD: −-, 88, 77, −-, 33
    Row
    EE: −-, −-, 55, 33, −-
    (a)
    How many roads (edges) are there in this network?
    [1 mark]
    • A1414
    • B77
    • C55
    • D1010
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    Prim's algorithm is applied starting at AA. In which order are the arcs added?
    [1 mark]
    • AABAB, ACAC, CECE, EDED
    • BABAB, BCBC, CDCD, DEDE
    • CABAB, BCBC, CECE, EDED
    • DABAB, BCBC, BDBD, DEDE
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    The road DEDE is closed for repairs. Find the total length of the minimum spanning tree of the remaining roads.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: the tree ABAB, BCBC, CECE is unchanged and DD must now be joined by its shortest remaining road CD=7CD=7
    A1:
    6+4+5+7=226+4+5+7=22 km
    Accept:
    2222 with the arcs ABAB, BCBC, CECE, CDCD

    Total for question 2: 4 marks

  3. 3
    A company must connect six villages PP, QQ, RR, SS, TT and UU with cable. The possible links and their costs, in thousands of pounds, are PQ=14PQ=14, PR=9PR=9, QR=11QR=11, QS=8QS=8, RS=12RS=12, RT=10RT=10, ST=6ST=6, SU=13SU=13 and TU=7TU=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]
    Show the mark scheme

    Mark scheme

    M1: edges considered in increasing order of cost: STST, TUTU, QSQS, PRPR, RTRT, QRQR, RSRS, SUSU, PQPQ
    A1: accepted
    ST(6)ST(6), TU(7)TU(7), QS(8)QS(8), PR(9)PR(9), RT(10)RT(10)
    A1: rejected
    QRQR, RSRS, SUSU, PQPQ because each would form a cycle; total cost 40 (thousand pounds)
    Accept:
    QRQR rejected as QQ and RR are already connected via SS and TT
    (b)
    Use Prim's algorithm starting at PP 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]
    Show the mark scheme

    Mark scheme

    M1: starts at PP and adds PR(9)PR(9), the cheaper of its two links
    A1:
    RT(10)RT(10) then ST(6)ST(6)
    A1:
    TU(7)TU(7) then QS(8)QS(8)
    B1: total 40, the same tree and cost as Kruskal's (both give a minimum spanning tree)

    Accept: the tree is the same because all the costs are different, so the minimum spanning tree is unique

    Total for question 3: 7 marks

  4. 4
    Six towns AA to FF are linked by roads. The distance matrix (in km) is given row by row, with columns in the order AA to FF and a dash meaning no direct road.
    Row
    AA: −-, 1111, 1515, 1313, 99, −-
    Row
    BB: 1111, −-, −-, 33, 88, −-
    Row
    CC: 1515, −-, −-, 77, −-, −-
    Row
    DD: 1313, 33, 77, −-, −-, 66
    Row
    EE: 99, 88, −-, −-, −-, 1111
    Row
    FF: −-, −-, −-, 66, 1111, −-
    (a)
    Use Prim's algorithm in matrix form, starting at AA, to find a minimum spanning tree. Give the arcs in the order they are added and the total length.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: starts at AA and takes the smallest entry in row AA: AE(9)AE(9)
    A1: first two arcs
    AE(9)AE(9) and EB(8)EB(8)
    M1: at each stage takes the smallest entry joining a vertex in the tree to a vertex not yet in the tree

    A1: first four arcs correct:
    AEAE, EBEB, BD(3)BD(3), DF(6)DF(6)
    A1: fifth arc
    DC(7)DC(7), all six vertices connected
    A1: total
    9+8+3+6+7=339+8+3+6+7=33 km
    Accept: any correct matrix working with the columns numbered in the order
    AA, EE, BB, DD, FF, CC
    (b)
    A student claims that the route from AA to FF along the minimum spanning tree is the shortest route from AA to FF. Evaluate this claim.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: the tree route from AA to FF is A−E−B−D−FA-E-B-D-F
    B1: its length is
    9+8+3+6=269+8+3+6=26 km
    M1: the route
    A−D−FA-D-F uses ADAD, which is not in the tree
    A1: its length is
    13+6=1913+6=19 km, which is shorter than 26 km
    R1: a minimum spanning tree minimises the total length needed to connect all the towns, not the distance between one particular pair

    R1: the claim is false, and a shortest-path method must be used to find the shortest route

    Accept: any other route shorter than 26 km, e.g.
    A−B−D−FA-B-D-F of length 20 km

    Total for question 4: 12 marks

End of questions

Subtopic tests