AQA A-Level Further Maths
Spanning trees and network optimisation
Total 27 marks
Name
Class
Date
- 1A network has six nodes to . The arcs and their weights are 6, 9, 4, 8, 5, 7, 3, 10 and 2.(a)How many arcs does a spanning tree of this network contain?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(b)What is the total weight of a minimum spanning tree?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(c)Explain why Kruskal's algorithm rejects arc .[2 marks]Show the mark scheme
Mark scheme
R1: when (weight 7) is considered, and are already connected through –– ( 5 and 3 are already chosen)
R1: adding would form a cycle, and a tree has no cyclesTotal for question 1: 4 marks
- 2Five villages are to be linked by cables. The possible links and their costs, in hundreds of pounds, are 12, 8, 15, 9, 10, 7, 14, 11, 6 and 13.(a)Which arc does Kruskal's algorithm select first?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(b)Prim's algorithm is applied starting at . In which order are the arcs added?[1 mark]- A, , ,
- B, , ,
- C, , ,
- D, , ,
Show the mark scheme
Mark scheme
Answer: A(c)Explain why Prim's algorithm starting at does not select arc , with weight 7, until the last step, even though it is lighter than arc .[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 nor is in the tree until is added, so cannot be considered before thenTotal for question 2: 4 marks
- 3Five towns to are to be connected by cable laid along direct links. The distances in km between the towns, with rows and columns in the order , are given by . The cable is to have the least possible total length.(a)Use Prim's algorithm, starting at , 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 and choose the shortest arc from : (4)
A1: then (2), (5), (3) in that order
B1: total length 14 km(b)The direct link 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 removed
A1: arcs (2), (3), (5), (6)
B1: total length 16 km
B1: an increase of 2 km on the original 14 kmTotal for question 3: 7 marks
- 4A network has seven nodes to . The arcs and their weights are 7, 5, 8, 9, 7, 5, 15, 6, 8, 9 and 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 5, 5, 6
B1: accept 7, 7
R1: reject 8 and 8, each of which would form a cycle ( and respectively)
B1: accept 9 (after rejecting 9, which would form a cycle)
A1: total weight 39
Accept: ties in either order(b)Use Prim's algorithm starting at to find a minimum spanning tree. A van must travel from to along the tree arcs; compare this route with the direct arc and comment on what this shows about minimum spanning trees.[6 marks]Show the mark scheme
Mark scheme
M1: start at and choose 9, the lighter of 9 and 11
A1: arcs added in the order , , , , ,
B1: total weight 39, the same as in (a)
M1: tree route from to is with weight
B1: this is 34, compared with 11 for the direct arc
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 routesTotal for question 4: 12 marks
End of questions