Minimum spanning trees

Minimum spanning trees Test

Spec 2.1 · Edexcel International A Level 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 International A Level Maths

Minimum spanning trees

Total 27 marks

Name

Class

Date

  1. 1
    A network has five vertices AA, BB, CC, DD and EE. The arcs and their weights are AB=7AB=7, AC=4AC=4, BC=6BC=6, BD=3BD=3, CD=8CD=8, CE=5CE=5 and DE=9DE=9.
    (a)
    How many arcs does a minimum spanning tree of this network contain?
    [1 mark]
    • A33
    • B44
    • C55
    • D77
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    Kruskal's algorithm is applied to this network. Which arc is the first to be rejected?
    [1 mark]
    • ABCBC
    • BCDCD
    • CDEDE
    • DABAB
    Show the mark scheme

    Mark scheme

    Answer: D
    (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]
    Show the mark scheme

    Mark scheme

    M1: arcs considered in increasing order of weight BD(3)BD(3), AC(4)AC(4), CE(5)CE(5), BC(6)BC(6), with AB(7)AB(7) rejected as it forms a cycle
    A1: tree
    BDBD, ACAC, CECE, BCBC with total weight 1818
    Do not accept:
    ABAB in the tree

    Total for question 1: 4 marks

  2. 2
    A network has five vertices PP, QQ, RR, SS and TT, shown by the following distance matrix. A dash means there is no arc. The rows, in order, are:
    PP: −-, 12, 9, 15, −-
    QQ: 12, −-, 8, −-, 14
    RR: 9, 8, −-, 11, 10
    SS: 15, −-, 11, −-, 6
    TT: −-, 14, 10, 6, −-
    The columns are in the same order
    PP, QQ, RR, SS, TT.
    (a)
    How many arcs does the network have?
    [1 mark]
    • A55
    • B77
    • C88
    • D1616
    Show the mark scheme

    Mark scheme

    Answer: C
    (b)
    Prim's algorithm is applied to the matrix starting at PP. Which arc is chosen first?
    [1 mark]
    • APRPR
    • BPQPQ
    • CQRQR
    • DSTST
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Starting at PP, 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]
    Show the mark scheme

    Mark scheme

    B1: PRPR, RQRQ, RTRT, TSTS in this order
    Accept:
    QRQR for RQRQ, STST for TSTS
    B1: total weight
    3333

    Total for question 2: 4 marks

  3. 3
    A water company must connect six villages AA to FF with pipes. The possible pipes and their costs, in thousands of pounds, are AB=12AB=12, AC=9AC=9, BC=7BC=7, BD=15BD=15, CD=11CD=11, CE=14CE=14, DE=6DE=6, DF=10DF=10 and EF=8EF=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]
    Show the mark scheme

    Mark scheme

    M1: arcs considered in increasing weight order, DE(6)DE(6), BC(7)BC(7), EF(8)EF(8), AC(9)AC(9), with DF(10)DF(10) rejected
    A1: tree
    DEDE, BCBC, EFEF, ACAC, CDCD
    A1: minimum cost
    4141 thousand pounds
    Accept:
    £41 000£41\,000
    (b)
    The pipe BDBD already exists and must be included in the network. Find the minimum cost of a network containing BDBD, and the extra cost compared with the minimum in part (a).
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: BDBD included first, as a given arc
    M1: Kruskal continued from
    BDBD, accepting DE(6)DE(6), BC(7)BC(7), EF(8)EF(8), AC(9)AC(9) and rejecting any arc that forms a cycle
    A1: arcs
    BDBD, DEDE, BCBC, EFEF, ACAC with cost 4545
    A1: extra cost
    44 thousand pounds
    Accept: follow-through from their answer to (a) for the extra cost

    Total for question 3: 7 marks

  4. 4
    A company plans a network of fibre-optic cables between five offices AA to EE. 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:
    AA: −-, 13, 9, −-, 17
    BB: 13, −-, 11, 15, −-
    CC: 9, 11, −-, 8, 12
    DD: −-, 15, 8, −-, 10
    EE: 17, −-, 12, 10, −-
    The columns are in the same order
    AA, BB, CC, DD, EE.
    (a)
    (i) State how many arcs are in the network.
    (ii) Starting at
    AA, 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]
    Show the mark scheme

    Mark scheme

    B1: (i) 88 arcs
    M1: (ii) Prim's started at
    AA, choosing the smallest entry in row AA, AC(9)AC(9)
    M1: next smallest entry in the rows of the selected vertices, in an unselected column,
    CD(8)CD(8)
    A1:
    DE(10)DE(10) next
    A1:
    BC(11)BC(11) last, giving the order ACAC, CDCD, DEDE, BCBC
    Accept:
    DCDC for CDCD, CBCB for BCBC
    B1: total cost
    3838 thousand pounds
    (b)
    A sixth office FF is added. Cable can be laid from FF to BB at a cost of 55 and from FF to EE at a cost of 66, and not directly to any other office. Use Kruskal's algorithm to find the new minimum cost. Explain why arc BCBC is no longer needed, and why the minimum cost is unchanged.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: Kruskal's algorithm applied in increasing weight order, starting BF(5)BF(5), EF(6)EF(6), CD(8)CD(8)
    A1:
    AC(9)AC(9) and DE(10)DE(10) accepted, giving 5 arcs for 6 vertices
    A1: new tree
    BFBF, EFEF, CDCD, ACAC, DEDE
    A1: minimum cost
    3838 thousand pounds
    R1:
    BC(11)BC(11) is not needed because BB is now connected to the rest of the tree through FF and EE
    R1: the arcs
    BFBF and EFEF together cost 5+6=115+6=11, the same as the BCBC arc they replace

    Total for question 4: 12 marks

End of questions

Subtopic tests