📚 Using a Minimum Spanning Tree Method to Find an Upper Bound | 用最小生成树方法求上界
In the Edexcel A-Level Further Mathematics Decision Mathematics 1 module, the travelling salesman problem requires you to find a short route visiting every vertex exactly once and returning to the start. Since exact methods are often too slow, exam questions ask for upper and lower bounds for the optimal tour length. This article explains how to use a minimum spanning tree method to construct a valid tour and hence obtain an upper bound.
在 Edexcel A-Level 进阶数学 D1 模块中，旅行商问题要求找到一条访问每个顶点恰好一次并返回起点的最短路线。由于精确方法通常太慢，考试题会要求求出最优路线长度的上界和下界。本文讲解如何使用最小生成树方法构造一条有效路线，从而得到一个上界。
1. What the Method Is For | 方法用途
A minimum spanning tree method for an upper bound is used on a complete weighted network, where every pair of vertices is joined by an edge. The goal is to build a Hamiltonian cycle, which is a cycle visiting every vertex exactly once before returning to the start. The total weight of that cycle is an upper bound for the travelling salesman problem because the optimal tour cannot be longer than any feasible tour you find.
求上界的最小生成树方法用于完全加权网络，即每对顶点之间都有一条边相连。目标是构建一个哈密顿回路，也就是访问每个顶点恰好一次并返回起点的回路。该回路的总权重就是旅行商问题的一个上界，因为最优路线不可能比你找到的任何可行路线更长。
2. Key Idea: From MST to Hamiltonian Cycle | 核心思想：从最小生成树到哈密顿回路
First find a minimum spanning tree of the network using Prim's algorithm or Kruskal's algorithm. Then traverse this tree in a depth-first search, recording each vertex the first time you visit it. Finally, return directly from the last recorded vertex to the starting vertex. This produces a Hamiltonian cycle using original graph edges, and its length is an upper bound.
首先使用 Prim 算法或 Kruskal 算法找到网络的最小生成树。然后对这个树进行深度优先搜索，记录每个顶点第一次被访问的顺序。最后从最后一个记录的顶点直接返回起点。这样就得到一条使用原图边权的哈密顿回路，其长度即为一个上界。
The method works because a minimum spanning tree connects all vertices cheaply. The depth-first traversal converts that cheap connection structure into an ordered vertex list, and the final direct return closes the cycle. It does not always give the optimal tour, but it always gives a feasible tour.
该方法之所以有效，是因为最小生成树以较低成本连接了所有顶点。深度优先遍历将这个低成本的连接结构转化为一个有序顶点列表，最后的直接返回闭合了回路。它不一定给出最优路线，但总能给出可行路线。
3. Step 1: Find the Minimum Spanning Tree | 第一步：求最小生成树
Use Kruskal's algorithm by sorting all edges in ascending order of weight. Add the shortest edge that does not create a cycle. Continue until all vertices are connected and exactly n − 1 edges have been added, where n is the number of vertices. Alternatively, use Prim's algorithm from a chosen starting vertex.
使用 Kruskal 算法时，将所有边按权值从小到大排序。依次加入不形成回路的最短边。继续这一过程，直到所有顶点都被连接并且恰好加入了 n − 1 条边，其中 n 是顶点数。也可以从选定的起点使用 Prim 算法。
elow, the vertices are A, B, C, D, E, and the edge weights are shown in the table. Kruskal's algorithm gives the MST edges BC, AC, CE, CD with total weight 2 + 3 + 3 + 4 = 12.
在下面的示例中，顶点为 A、B、C、D、E，边权如下表所示。Kruskal 算法得到最小生成树的边为 BC、AC、CE、CD，总权重为 2 + 3 + 3 + 4 = 12。
4. Step 2: Depth-First Search of the MST | 第二步：对最小生成树进行深度优先搜索
A depth-first search starts at a chosen vertex and follows one branch of the tree as far as possible before backtracking. When a vertex has unvisited neighbours, go to the next unvisited neighbour. When a dead end is reached, backtrack to the most recent vertex that still has an unvisited neighbour.
深度优先搜索从选定的顶点开始，沿着树的一个分支尽可能深入，然后再回溯。当一个顶点还有未访问的邻居时，就前往下一个未访问的邻居。当到达死胡同时，回溯到最近一个仍有未访问邻居的顶点。
At each vertex, the order of neighbour choice may be alphabetical, by increasing edge weight, or as specified in the question. Different choices can produce different tours, so always state the order you are using.
在每个顶点处，邻居的选择顺序可以是字母顺序、按边权从小到大，或者题目指定的顺序。不同的选择会产生不同的路线，因此务必说明你使用的顺序。
5. Step 3: List Vertices in First-Visit Order | 第三步：按首次访问顺序列出顶点
During the depth-first search, write down a vertex only when it is visited for the first time. Do not write it again when backtracking through it. The final list is the order of first visits. This list determines your candidate Hamiltonian cycle.
在深度优先搜索过程中，仅在顶点第一次被访问时写下它。回溯经过该顶点时不要再次记录。最终列表就是首次访问顺序。该列表决定了候选的哈密顿回路。
For example, starting at A and using alphabetical order at C, the depth-first search of the MST with edges A–C, C–B, C–D, C–E gives the first-visit order A, C, B, D, E.
例如，从 A 出发，在 C 处按字母顺序选择，对边为 A–C、C–B、C–D、C–E 的最小生成树进行深度优先搜索，得到首次访问顺序 A、C、B、D、E。
6. Step 4: Close the Cycle and Calculate Length | 第四步：闭合回路并计算长度
After listing all vertices, return directly from the last vertex to the first vertex. This direct edge must exist because the network is complete. Then calculate the tour length by adding the weights of the consecutive edges in the cycle.
列出所有顶点后，从最后一个顶点直接返回到第一个顶点。由于网络是完全的，这条直接边一定存在。然后将回路中相邻边的权值相加，计算路线长度。
al travelling salesman tour. Write the answer as: optimal tour length ≤ tour length found.
该路线长度是最优旅行商路线的一个上界。答案写作：最优路线长度 ≤ 所求路线长度。
7. Worked Example: Distance Table | 示例：距离表
The following complete network has five vertices A, B, C, D, E. Use the minimum spanning tree method to find an upper bound for the optimal tour length.
以下完全网络有五个顶点 A、B、C、D、E。使用最小生成树方法求最优路线长度的上界。
| Vertex | A | B | C | D | E |
|---|---|---|---|---|---|
| A | — | 4 | 3 | 5 | 6 |
| B | 4 | — | 2 | 7 | 5 |
| C | 3 | 2 | — | 4 | 3 |
| D | 5 | 7 | 4 | — | 4 |
| E | 6 | 5 | 3 | 4 | — |
, DE = 4, AD = 5, BE = 5, AE = 6, BD = 7. Add BC, AC, CE, CD. The MST has total weight 12.
为 Kruskal 算法排序边：BC = 2、AC = 3、CE = 3、AB = 4、CD = 4、DE = 4、AD = 5、BE = 5、AE = 6、BD = 7。加入 BC、AC、CE、CD。最小生成树总权重为 12。
8. Worked Example: Depth-First Traversal and Upper Bound | 示例：深度优先遍历与上界
Start the depth-first search at A. The MST is A–C, C–B, C–D, C–E. At C, use alphabetical order, so visit B first, then D, then E. The first-visit order is A, C, B, D, E.
从 A 开始深度优先搜索。最小生成树为 A–C、C–B、C–D、C–E。在 C 处按字母顺序，先访问 B，然后 D，再 E。首次访问顺序为 A、C、B、D、E。
Return from E directly to A to close the cycle. The candidate tour is A–C–B–D–E–A. Its length is calculated as follows.
从 E 直接返回 A 以闭合回路。候选路线为 A–C–B–D–E–A。其长度计算如下。
Tour length = d(A,C) + d(C,B) + d(B,D) + d(D,E) + d(E,A) = 3 + 2 + 7 + 4 + 6 = 22
Therefore the optimal tour length is at most 22, so an upper bound is 22. If the question asks for the best possible upper bound from different depth-first search orderings, you can try all valid orderings and select the smallest tour length found.
因此最优路线长度最多为 22，所以上界为 22。如果题目要求从不同深度优先搜索顺序中找出最佳上界，你可以尝试所有有效顺序并选择找到的最小路线长度。
9. Why It Gives an Upper Bound | 为什么它给出上界
The depth-first search of a minimum spanning tree gives a sequence that visits every vertex at least once, and recording first visits removes repeated vertices. Since the original network is complete, you can join consecutive vertices in the first-visit list directly. The result is a Hamiltonian cycle, so it is a feasible tour.
最小生成树的深度优先搜索给出一个至少访问每个顶点一次的序列，记录首次访问可以去掉重复顶点。由于原网络是完全的，你可以直接连接首次访问列表中相邻的顶点。得到的结果是一个哈密顿回路，因此是一条可行路线。
The optimal tour is the shortest of all Hamiltonian cycles. Any feasible tour length must be greater than or equal to the optimal length, so the calculated tour length is an upper bound. A smaller upper bound is better, but any valid upper bound is accepted unless the question demands the best one.
最优路线是所有哈密顿回路中最短的。任何可行路线长度都一定大于或等于最优长度，因此计算出的路线长度是一个上界。较小的上界更好，但除非题目要求最佳上界，任何有效上界都可以接受。
10. Common Mistakes and Exam Tips | 常见错误与应试技巧
One common mistake is writing down a vertex every time it is passed during backtracking. This creates repeated vertices in the tour, which is not a Hamiltonian cycle. Only record the first visit to each vertex.
一个常见错误是在回溯时每次经过顶点都写下来。这会在路线中产生重复顶点，这不是哈密顿回路。只记录每个顶点的首次访问。
Another mistake is using an edge that is not in the original graph to close the cycle. The network must be complete, so the direct return edge exists, but always check the distance table. Also do not use the MST weight as the upper bound; you must calculate the original edge weights along the tour.
另一个错误是使用原图中不存在的边来闭合回路。网络必须是完全的，所以直接返回边确实存在，但务必检查距离表。此外不要用最小生成树的权重作为上界；你必须计算路线沿线原图边的权重。
In the exam, show the sorted edges for Kruskal or the Prim table, draw the MST, draw or list the depth-first search order, then show the final tour and its length. Clear working helps secure method marks even if a small arithmetic error occurs.
考试中，展示 Kruskal 的排序边或 Prim 表格，画出最小生成树，画出或列出深度优先搜索顺序，然后展示最终路线及其长度。清晰的步骤有助于即使出现小的计算错误也能拿到方法分。
11. Quick Comparison with Nearest Neighbour | 与最近邻法快速比较
The nearest neighbour algorithm chooses the cheapest unvisited vertex from the current vertex. It is faster, but it often produces a tour that can be locally trapped. The minimum spanning tree method uses global cheap connections first and then converts the tree into a cycle, so it is less likely to miss very cheap edges.
最近邻算法从当前顶点选择最便宜的未访问顶点。它速度更快，但常常会陷入局部最优。最小生成树方法先利用全局的廉价连接，然后将树转化为回路，因此不太可能漏掉非常便宜的边。
Both methods produce upper bounds. In Edexcel D1, you may be asked to compare two upper bounds or to explain why the minimum spanning tree method is suitable. A smaller upper bound is closer to the true optimal tour, so it is more useful.
两种方法都产生上界。在 Edexcel D1 中，你可能会被要求比较两个上界，或解释为什么最小生成树方法适用。较小的上界更接近真实最优路线，因此更有用。
12. Summary | 小结
To find an upper bound using a minimum spanning tree method: find the MST, perform a depth-first search from a chosen start vertex, list vertices in first-visit order, return directly to the start, and calculate the tour length. This gives a valid Hamiltonian cycle, so its length is an upper bound for the optimal travelling salesman tour.
使用最小生成树方法求上界的步骤为：找到最小生成树，从选定的起点进行深度优先搜索，按首次访问顺序列出顶点，直接返回起点，并计算路线长度。这给出一个有效的哈密顿回路，因此其长度是旅行商最优路线的一个上界。
Practice with different complete networks and check your depth-first search order carefully. In the exam, always state your ordering rule and show your working for full marks.
用不同的完全网络多加练习，并仔细检查深度优先搜索顺序。考试中务必说明你的排序规则并展示步骤，以获得满分。
Published by TutorHao | Further Maths (D1) Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图