Question
The vertices and weights of the graph \(G\) are given in the following table.
(a) (i) Use Kruskal’s algorithm to find the minimum spanning tree for \(G\), indicating clearly the order in which the edges are included.
(ii) Draw the minimum spanning tree for \(G\).
(b) Consider the travelling salesman problem for \(G\).
(i) An upper bound for the problem can be found by doubling the weight of the minimum spanning tree. Use this method to find an upper bound.
(ii) Starting at \({\text{A}}\), use the nearest neighbour algorithm to find another upper bound.
(iii) By first removing \({\text{A}}\), use the deleted vertex algorithm to find a lower bound for the problem.
(c) The travelling salesman problem is now modified so that starting at \({\text{A}}\), the vertices \({\text{B}}\) and \({\text{C}}\) have to be visited first in that order, then \({\text{D}}\), \({\text{E}}\), \({\text{F}}\) in any order before returning to \({\text{A}}\).
(i) Solve this modified problem.
(ii) Comment whether or not your answer has any effect on the upper bound to the problem considered in (b).
Answer/Explanation
Markscheme
(a) (i) using Kruskal’s algorithm, the minimum spanning tree is built up as follows
\({\text{BF}}\) A1
\({\text{BE, BC}}\) A1
\({\text{DE, AD}}\) A1
(ii) 
A1
[4 marks]
(b) (i) weight of minimum spanning tree \(= 69\) A1
Note: This mark may be earned earlier.
upper bound \(= 138\) A1
(ii) starting at \({\text{A}}\), the cycle is \({\text{A}} \to {\text{D}} \to {\text{E}} \to {\text{B}} \to {\text{F}} \to {\text{C}} \to {\text{A}}\) M1A1
an upper bound is the total weight of this cycle (M1)
\(17 + 16 + 12 + 10 + 20 + 19 = 94\) A1
(iii) the minimum spanning tree of the reduced graph is as above with AD removed (R1)
its total weight is \(10 + 12 + 14 + 16 = 52\) A1
adding the weights of the two deleted edges of the minimum spanning tree gives (M1)
lower bound \( = 52 + 17 + 18 = 87\) A1
[10 marks]
(c) (i) the possible cycles, and their weights, are
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{E}} \to {\text{F}} \to {\text{A Weight 102 (or 70 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{D}} \to {\text{F}} \to {\text{E}} \to {\text{A Weight 107 (or 75 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{E}} \to {\text{D}} \to {\text{F}} \to {\text{A Weight 106 (or 74 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{E}} \to {\text{F}} \to {\text{D}} \to {\text{A Weight 99 (or 67 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{D}} \to {\text{E}} \to {\text{A Weight 110 (or 78 exc A}} \to {\text{B}} \to {\text{C)}}\)
\({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{E}} \to {\text{D}} \to {\text{A Weight 98 (or 66 exc A}} \to {\text{B}} \to {\text{C)}}\) A3
Note: Award A(3 – n) for \(n\) errors up to \(n = 2\), A0 thereafter.
the solution is therefore the cycle \({\text{A}} \to {\text{B}} \to {\text{C}} \to {\text{F}} \to {\text{E}} \to {\text{D}} \to {\text{A}}\)
(with weight \(98\)) A1
(ii) no, it has no effect A1
[5 marks]