📚 Using a Minimum Spanning Tree Method to Find an Upper Bound | 用最小生成树方法求上界
In the Travelling Salesman Problem (TSP), an upper bound is any tour length that is guaranteed to be at least as long as the optimal tour. One elegant, graph‑theoretic way to construct such an upper bound is to start from a minimum spanning tree, perform a systematic traversal, and apply triangle‑inequality shortcuts to obtain a valid Hamiltonian cycle. This article explains the rationale, step‑by‑step procedure, and a worked example following the Edexcel Decision Mathematics approach.
在旅行商问题（TSP）中，上界是指任何一个保证不低于最优巡回长度的回路长度。一种简洁的图论方法是：从最小生成树出发，进行系统遍历，再利用三角不等式走捷径，从而得到一个合法的哈密顿回路。本文将按照 Edexcel 决策数学的思路，解释其原理、逐步步骤，并给出一个详细算例。
1. Upper Bounds and the Role of Spanning Trees | 上界与生成树的作用
For a complete graph with non‑ y once and returns to the start is a feasible solution. Its total length is an upper bound— one edge from a tour yields a spanning tree, so MST ≤ optimal tour), but by traversing the MST cleverly we can also generate an upper bound.
对于一个边权非负的完全图，任意一条访问所有顶点各一次并返回起点的回路都是一个可行解。其总长度就是一个上界——最优回路不会比我们找到的最佳可行回路更长。最小生成树给出了 TSP 的下界（从回路上删去一条边就得到一棵生成树，故 MST ≤ 最优回路），但通过巧妙地遍历 MST，我们也能生成一个上界。
2. Key Idea: Walk Around the Tree | 核心思想：绕树行走
Imagine drawing the MST and walking along its edges so that every branch is traced twice – ength of this walk is exactly 2 × weight of MST. If the graph satisfies the triangle inequality, we can ‘short‑ut’ repeated vertices to turn the walk into a Hamiltonian cycle whose length is ≤ 2 × MST.
想象画出 MST 并沿着它的边行走，使得每条树枝都被走两次——一次去程、一次回程。这就产生了一个访问所有顶点并返回起点的闭行走。由于每条边走两次，此行走的长度恰好为 2 × MST 的总权。如果图满足三角不等式，就可以对重复顶点“走捷径”，从而将行走转化为长度 ≤ 2 × MST 的哈密顿回路。
3. Step 1: Build the Minimum Spanning Tree | 步骤一：构造最小生成树
Apply Prim’s or Kruskal’s algorithm to the complete graph (or a reduced distance matrix). The result is a connected, acyclic subgraph linking all vertices with minimum total weight. For a TSP on n cities, this tree has n – 1 edges.
对完全图（或简化后的距离矩阵）使用普里姆算法或克鲁斯卡尔算法。结果是一个连接所有顶点的连通无环子图，且总权最小。对于 n 座城市的 TSP，这棵树具有 n – 1 条边。
- Example: In a 5‑ network we obtain an MST with edges AB (20), BD (15), DC (10), CE (25); total weight = 70.
- 例子：在 5 城网络中，我们得到一棵 MST，边为 AB (20)、BD (15)、DC (10)、CE (25)；总权 = 70。
4. Step 2: Double the Edges or Record a Walk | 步骤二：将边加倍或记录遍历顺序
Convert the tree into an Eulerian multigraph by duplicating every tree edge. This ensures every vertex has even degree, so an Eulerian circuit exists. Alternatively, we plan a depth‑first traversal of the tree that visits vertices and notes the order in which they are first encountered, then returns to the start along the tree.
将树中的每条边复制一份，得到一个每个顶点度数均为偶数的欧拉多重图，从而存在欧拉回路。或者，我们设计对树的深度优先遍历，记录第一次访问顶点的顺序，然后沿树返回起点。
- Using the same MST, a doubled walk could be A‑B‑D‑C‑E‑C‑D‑B‑A.
- 沿用上述 MST，加倍边的行走可以是 A‑B‑D‑C‑E‑C‑D‑B‑A。
5. Step 3: Short‑Cut to Avoid Repeats | 步骤三：通过捷径避免重复顶点
In the walk obtained, some vertices appear more than once. Because the graph satisfies the triangle inequality (the direct path between two vertices is no longer than any indirect path), we can skip a vertex already visited by jumping directly to the next unvisited vertex. This ‘short‑cutting’ never increases the total length.
在得到的行走中，某些顶点会出现多次。由于图满足三角不等式（两点间直接路径不长于任何间接路径），我们可以通过直接跳至下一个未访问顶点来跳过已访问过的顶点。这种“走捷径”操作不会增加总长度。
- From A‑B‑D‑C‑E‑C‑D‑B‑A, short‑cut to A‑B‑D‑C‑E‑A, assuming edge EA is available in the original graph.
- 从 A‑B‑D‑C‑E‑C‑D‑B‑A 走捷径得到 A‑B‑D‑C‑E‑A，假设原始图中 EA 边存在。
6. Step 4: Form the Hamiltonian Cycle and Calculate Its Length | 步骤四：形成哈密顿回路并计算长度
The short‑cut sequence A‑B‑D‑C‑E‑ t distances from the original distance matrix, not the tree edges. This length is your MST‑based upper bound. By construction, Length(tour) ≤ 2 × (MST weight).
捷径序列 A‑B‑D‑C‑E‑A 是一条合法巡回。其长度从原始距离矩阵中的直接距离相加得到，而不是用树边长度。这个长度就是基于 MST 的上界。根据构造过程，巡回长度 ≤ 2 × (MST 权)。
Upper Bound = d(A,B) + d(B,D) + d(D,C) + d(C,E) + d(E,A)
上界 = d(A,B) + d(B,D) + d(D,C) + d(C,E) + d(E,A)
7. Worked Example with a Distance Table | 带距离表的完整算例
Consider five cities A–E with the following distance matrix (symmetric).
考虑五个城市 A–E，其距离矩阵如下（对称）。
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | – | 20 | 30 | 25 | 40 |
| B | 20 | – | 35 | 15 | 45 |
| C | 30 | 35 | – | 10 | 25 |
| D | 25 | 15 | 10 | – | 30 |
| E | 40 | 45 | 25 | 30 | – |
MST (Prim from A): A–B (20), B–D (15), D–C (10), C–E (25). Total = 70.
MST（从 A 开始 Prim 算法）：A–B (20)、B–D (15)、D–C (10)、C–E (25)。总和 = 70。
Double‑the‑tree walk: A–B–D–C–E–C–D–B–A. After short‑cutting repeated vertices we obtain the tour A–B–D–C–E– s: AB (20) + BD (15) + DC (10) + CE (25) + EA (40) = 110. Thus 110 is a valid upper bound.
加倍树的行走：A–B–D–C–E–C–D–B–A。对重复顶点走捷径后得到巡回 A–B–D–C–E–A。用原始直接距离计算长度：AB (20) + BD (15) + DC (10) + CE (25) + EA (40) = 110。因此 110 是一个有效的上界。
8. Why This Upper Bound Works | 为何该上界有效
ever worse than twice the optimal, and often much better. Because MST ≤ Optimal, we have 2 × MST ≤ 2 × Optimal, but the upper bound itself is the tour length, which sits between Optimal and 2 × MST.
我们构造的巡回是一个可行解，因此真正最优的巡回 ≤ 110。不等式 巡回长度 ≤ 2 × MST 保证了该界不会比最优解的两倍更差，并且通常要好得多。因为 MST ≤ 最优解，所以 2 × MST ≤ 2 × 最优解，但上界本身是巡回长度，它介于最优解与 2 × MST 之间。
9. Comparison with the Nearest Neighbour Upper Bound | 与最近邻上界的对比
arest neighbour algorithm also yields an upper bound, often tighter (smaller) than the MST‑ riangle inequality holds, making it theoretically robust. In Edexcel exams you may be asked to find both lower bounds (via MST) and upper bounds (via NN); knowing this alternative enriches your understanding.
最近邻算法也给出一个上界，通常比基于 MST 的方法更紧（更小）。然而，MST 方法是确定的，并且在三角不等式成立时能提供 ≤ 2 × 最优解的保证，使其在理论上具有稳健性。在 Edexcel 考试中，你可能既要找下界（通过 MST）也要找上界（通过最近邻）；了解这一替代方法会加深你的理解。
10. Practical Steps Summary | 实际操作步骤总结
- Find the MST of the complete graph using Prim or Kruskal. | 求 MST：用 Prim 或 Kruskal 算法求出完全图的最小生成树。
- Double every edge of the MST mentally to create a closed walk. | 将树边加倍：在思维中将 MST 的每条边复制一份，形成一个闭行走。
- Trace a walk that starts at a chosen vertex, follows the doubled edges, and returns to start. | 记录行走：选择一个起点，沿加倍后的边行走并返回起点。
- Short‑cut any vertex that appears more than once by going directly to the next unvisited vertex. | 走捷径：对出现两次的顶点，直接跳至下一个未访问顶点。
- List the resulting Hamiltonian cycle and compute its total length from original distances. | 列出哈密顿回路：用原始距离计算回路的总长度。
- This length is your upper bound. | 该长度即为上界。
11. Limitations and Key Exam Tips | 局限性与考试要点
The MST‑based upper bound depends on the starting vertex and the short‑cut decisions; different choices may give different (still valid) bounds. It requires the original graph to satisfy the triangle inequality; otherwise short‑cutting could increase the length. In Edexcel Decision Maths, always state clearly that a tour obtained by any constructive method is an upper bound, and justify why the length is valid.
基于 MST 的上界依赖于起始顶点和走捷径的选择；不同的选择会给出不同（但仍然有效）的上界。它要求原图满足三角不等式，否则走捷径可能会增加长度。在 Edexcel 决策数学中，要明确说明任何构造方法得到的巡回都是一个上界，并论证为何其长度有效。
12. Conclusion | 结论
Using a minimum spanning tree to obtain an upper bound is a clever blend of graph theory and TSP heuristics. While not always the tightest bound, it demonstrates the power of MSTs beyond simple network design and provides a safety net when other methods fail. Practice with small distance tables and compare your result with the nearest neighbour tour to build confidence.
用最小生成树来获取上界是图论与 TSP 启发式方法的巧妙融合。尽管它并不总是最紧的界，但它展示了 MST 在简单网络设计之外的威力，并在其他方法失效时提供一个安全网。用小距离表格进行练习，并将结果与最近邻巡回相比较，以建立信心。
Published by TutorHao | Decision Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图