Edexcel A-Level Further Maths
Minimum spanning trees
Total 27 marks
Name
Class
Date
- 1A network has six vertices , , , , and . Its edges and weights are , , , , , , , and .(a)How many edges does a minimum spanning tree of this network contain?[1 mark]
- A
- B
- C
- D
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]- A, , , ,
- B, , , ,
- C, , , ,
- D, , , ,
Show the mark scheme
Mark scheme
Answer: A(c)Explain why Kruskal's algorithm rejects the edge .[2 marks]Show the mark scheme
Mark scheme
M1: by the time is considered, and are already connected (via and )
A1: adding would create a cycle
Accept: and are already in the same componentTotal for question 1: 4 marks
- 2Five towns , , , , are linked by roads. The distance matrix (in km) is given row by row, with columns in the order to and a dash meaning no direct road.
Row : , , , ,
Row : , , , ,
Row : , , , ,
Row : , , , ,
Row : , , , ,(a)How many roads (edges) are there in this network?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(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: C(c)The road 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 , , is unchanged and must now be joined by its shortest remaining road
A1: km
Accept: with the arcs , , ,Total for question 2: 4 marks
- 3A company must connect six villages , , , , and with cable. The possible links and their costs, in thousands of pounds, are , , , , , , , and .(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: , , , , , , , ,
A1: accepted , , , ,
A1: rejected , , , because each would form a cycle; total cost 40 (thousand pounds)
Accept: rejected as and are already connected via and(b)Use Prim's algorithm starting at 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 and adds , the cheaper of its two links
A1: then
A1: then
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 uniqueTotal for question 3: 7 marks
- 4Six towns to are linked by roads. The distance matrix (in km) is given row by row, with columns in the order to and a dash meaning no direct road.
Row : , , , , ,
Row : , , , , ,
Row : , , , , ,
Row : , , , , ,
Row : , , , , ,
Row : , , , , ,(a)Use Prim's algorithm in matrix form, starting at , 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 and takes the smallest entry in row :
A1: first two arcs and
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: , , ,
A1: fifth arc , all six vertices connected
A1: total km
Accept: any correct matrix working with the columns numbered in the order , , , , ,(b)A student claims that the route from to along the minimum spanning tree is the shortest route from to . Evaluate this claim.[6 marks]Show the mark scheme
Mark scheme
B1: the tree route from to is
B1: its length is km
M1: the route uses , which is not in the tree
A1: its length is 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. of length 20 kmTotal for question 4: 12 marks
End of questions