Edexcel International A Level Maths
Minimum spanning trees
Total 27 marks
Name
Class
Date
- 1A network has five vertices , , , and . The arcs and their weights are , , , , , and .(a)How many arcs does a minimum spanning tree of this network contain?[1 mark]
- A
- B
- C
- D
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]- A
- B
- C
- D
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 , , , , with rejected as it forms a cycle
A1: tree , , , with total weight
Do not accept: in the treeTotal for question 1: 4 marks
- 2A network has five vertices , , , and , shown by the following distance matrix. A dash means there is no arc. The rows, in order, are:
: , 12, 9, 15,
: 12, , 8, , 14
: 9, 8, , 11, 10
: 15, , 11, , 6
: , 14, 10, 6,
The columns are in the same order , , , , .(a)How many arcs does the network have?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(b)Prim's algorithm is applied to the matrix starting at . Which arc is chosen first?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(c)Starting at , 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: , , , in this order
Accept: for , for
B1: total weightTotal for question 2: 4 marks
- 3A water company must connect six villages to with pipes. The possible pipes and their costs, in thousands of pounds, are , , , , , , , and . 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, , , , , with rejected
A1: tree , , , ,
A1: minimum cost thousand pounds
Accept:(b)The pipe already exists and must be included in the network. Find the minimum cost of a network containing , and the extra cost compared with the minimum in part (a).[4 marks]Show the mark scheme
Mark scheme
B1: included first, as a given arc
M1: Kruskal continued from , accepting , , , and rejecting any arc that forms a cycle
A1: arcs , , , , with cost
A1: extra cost thousand pounds
Accept: follow-through from their answer to (a) for the extra costTotal for question 3: 7 marks
- 4A company plans a network of fibre-optic cables between five offices to . 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:
: , 13, 9, , 17
: 13, , 11, 15,
: 9, 11, , 8, 12
: , 15, 8, , 10
: 17, , 12, 10,
The columns are in the same order , , , , .(a)(i) State how many arcs are in the network.[6 marks]
(ii) Starting at , 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.Show the mark scheme
Mark scheme
B1: (i) arcs
M1: (ii) Prim's started at , choosing the smallest entry in row ,
M1: next smallest entry in the rows of the selected vertices, in an unselected column,
A1: next
A1: last, giving the order , , ,
Accept: for , for
B1: total cost thousand pounds(b)A sixth office is added. Cable can be laid from to at a cost of and from to at a cost of , and not directly to any other office. Use Kruskal's algorithm to find the new minimum cost. Explain why arc 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 , ,
A1: and accepted, giving 5 arcs for 6 vertices
A1: new tree , , , ,
A1: minimum cost thousand pounds
R1: is not needed because is now connected to the rest of the tree through and
R1: the arcs and together cost , the same as the arc they replaceTotal for question 4: 12 marks
End of questions