Using a Minimum Spanning Tree Method to Find a Lower Bound | 用最小生成树方法求下界

📚 Using a Minimum Spanning Tree Method to Find a Lower Bound | 用最小生成树方法求下界

In Edexcel Decision Mathematics 1, the travelling salesperson problem (TSP) asks for the shortest possible tour that visits every vertex exactly once and returns to the start. Finding the exact optimal tour can be time-consuming, so we use upper and lower bounds to narrow down the possible tour length. A lower bound is a value that no valid tour can have a weight below. This article explains how a minimum spanning tree (MST) can be used to construct a reliable lower bound for the TSP.

在 Edexcel 决策数学 1 中，旅行商问题 (TSP) 要求找到一条访问每个顶点恰好一次并返回起点的最短巡回路线。找到确切的最优巡回路线可能非常耗时，因此我们使用上界和下界来缩小可能的巡回路线长度范围。下界是任何有效巡回路线的权重都不能低于的值。本文解释如何使用最小生成树 (MST) 为 TSP 构造一个可靠的下界。

1. The Travelling Salesperson Problem and Bounds | 旅行商问题与界限

The TSP is a classic optimisation problem. A tour must include every vertex once and return to the starting point, so it forms a Hamiltonian cycle. In a complete graph with n vertices, there are (n − 1)! / 2 possible tours, which makes complete enumeration impractical for large n.

TSP 是一个经典的优化问题。一条巡回路线必须包含每个顶点一次并返回起点，因此它形成一个哈密顿环。在具有 n 个顶点的完全图中，共有 (n − 1)! / 2 条可能的巡回路线，这使得对于较大的 n，完全枚举是不切实际的。

To solve TSP problems in exam conditions, we usually find an upper bound using a heuristic method such as the nearest neighbour algorithm, and a lower bound using the minimum spanning tree method. If the upper bound and lower bound are equal, then the tour used to find the upper bound is provably optimal.

在考试条件下解决 TSP 问题时，我们通常使用启发式方法（如最近邻算法）求上界，使用最小生成树方法求下界。如果上界和下界相等，那么用于求上界的巡回路线就是可证明的最优解。

2. Why a Minimum Spanning Tree Gives a Lower Bound | 为什么最小生成树给出下界

Consider any optimal TSP tour. If we delete one vertex from the tour, we also delete the two edges that connect that vertex to its two neighbours in the tour. The remaining edges still connect all the other vertices, and because the original tour was a cycle, removing two edges and one vertex leaves behind a path, which is a special type of tree.

考虑任意最优 TSP 巡回路线。如果我们从巡回路线中删除一个顶点，同时也会删除该顶点与其巡回路线中两个相邻顶点连接的两条边。剩下的边仍然连接所有其他顶点，并且因为原始巡回路线是一个环，删除两条边和一个顶点后会留下一条路径，而路径是一种特殊类型的树。

This remaining structure is a spanning tree on the vertices that were not deleted. Its total weight must be at least the weight of the minimum spanning tree (MST) on those vertices. The two deleted edges must have total weight at least the sum of the two shortest possible edges that could connect the deleted vertex back to the graph. Adding these two minimum contributions gives a valid lower bound for the whole tour.

剩余的结构是在未删除顶点上的一棵生成树。它的总权重必须至少是这些顶点上最小生成树 (MST) 的权重。被删除的两条边的总权重必须至少是能够将被删除顶点连接回图的两条最短可能边的权重之和。将这两个最小贡献相加，就得到了整个巡回路线的一个有效下界。

3. The Vertex-Deletion Technique | 删除顶点技巧

The standard Edexcel D1 method is to choose one vertex, delete it from the graph, and find the MST of the remaining vertices. Then we add the weights of the two smallest edges that were incident to the deleted vertex. The result is a lower bound for the TSP.

标准的 Edexcel D1 方法是选择一个顶点，将其从图中删除，然后求剩余顶点的 MST。接着，我们加上与被删除顶点关联的两条最小边的权重。结果就是 TSP 的一个下界。

This technique works because any TSP tour must enter and leave the deleted vertex exactly once, using two incident edges. The rest of the tour forms a spanning tree on the remaining vertices. Therefore, the tour weight is always greater than or equal to the sum of the MST weight and the two shortest incident edges.

这种技巧之所以有效，是因为任何 TSP 巡回路线必须恰好进入和离开被删除顶点一次，使用两条关联边。巡回路线的其余部分在剩余顶点上形成一棵生成树。因此，巡回路线权重总是大于或等于 MST 权重与两条最短关联边之和。

4. Step 1: Choose a Vertex to Delete | 步骤1：选择要删除的顶点

You can choose any vertex to delete, and the method will still produce a lower bound. However, some vertices give better bounds than others. In an exam question, you may be told which vertex to delete, or you may be asked to try several vertices and select the largest lower bound.

你可以选择任意顶点删除，该方法仍会产生一个下界。但是，有些顶点比其他顶点给出更好的下界。在考试题中，题目可能会指定要删除哪个顶点，或者可能要求你尝试多个顶点并选择最大的下界。

Choosing a vertex with relatively large edges to the rest of the graph is often useful because the two shortest edges from it will still be included in the bound. If a vertex has one very small edge, deleting it may produce a weak bound, so repeating the process for other vertices is important.

选择与图中其他顶点之间边权相对较大的顶点通常很有用，因为从它出发的两条最短边仍会被包含在下界中。如果某个顶点有一条非常小的边，删除它可能会产生较弱的下界，因此对其他顶点重复此过程非常重要。

5. Step 2: Find the MST of the Remaining Vertices | 步骤2：求剩余顶点的最小生成树

After deleting the chosen vertex, apply Kruskal’s algorithm or Prim’s algorithm to the remaining vertices. With Kruskal’s algorithm, list all remaining edges in increasing order of weight, then repeatedly add the smallest edge that does not form a cycle until all remaining vertices are connected.

删除所选顶点后，对剩余顶点应用 Kruskal 算法或 Prim 算法。使用 Kruskal 算法时，按权重递增的顺序列出所有剩余边，然后反复添加不会形成环的最小边，直到所有剩余顶点都连通。

It is essential to use only the edges that do not involve the deleted vertex. The MST weight is the sum of the selected edge weights. A tree on n vertices needs exactly n − 1 edges, so if five vertices remain after deletion, the MST must contain four edges.

必须只使用不涉及被删除顶点的边。MST 权重是所选边权重的总和。n 个顶点上的树恰好需要 n − 1 条边，因此如果删除后剩余五个顶点，则 MST 必须包含四条边。

6. Step 3: Add the Two Shortest Edges to the Deleted Vertex | 步骤3：加上连接到被删除顶点的两条最短边

From the original graph, identify all edges incident to the deleted vertex. Choose the two with the smallest weights. It does not matter whether these two edges share the same endpoint or not, because they simply represent the cheapest possible way to enter and leave the deleted vertex.

从原图中找出与被删除顶点关联的所有边。选择权重最小的两条边。这两条边是否共享同一个端点并不重要，因为它们只是代表进入和离开被删除顶点的最便宜方式。

The lower bound is then calculated as: Lower bound = MST weight of remaining vertices + weight of shortest incident edge + weight of second shortest incident edge.

Lower bound = MST weight + w₁ + w₂

其中 w₁ 和 w₂ 是与被删除顶点关联的两条最短边的权重。不要在 MST 中重复计算这些边，因为 MST 只包含剩余顶点之间的边。

7. Worked Example: Finding a Lower Bound | 例题：求一个下界

Consider a complete graph on six vertices A, B, C, D, E, F. The edge weights are shown in the table below. We will delete vertex A and find a lower bound for the TSP.

考虑一个六个顶点 A、B、C、D、E、F 的完全图。边权重如下表所示。我们将删除顶点 A 并求 TSP 的一个下界。

Edge	Weight	Edge	Weight
AB	5	BD	6
AC	7	BE	7
AD	9	BF	5
AE	4	CD	4
AF	6	CE	3
BC	8	CF	9
		DE	5
		DF	7
		EF	6

After deleting vertex A, the remaining vertices are B, C, D, E, F. The edges among these vertices in ascending order of weight are: CE = 3, CD = 4, DE = 5, BF = 5, BD = 6, EF = 6, BE = 7, DF = 7, BC = 8, CF = 9.

删除顶点 A 后，剩余顶点为 B、C、D、E、F。这些顶点之间的边按权重升序排列为：CE = 3、CD = 4、DE = 5、BF = 5、BD = 6、EF = 6、BE = 7、DF = 7、BC = 8、CF = 9。

Using Kruskal’s algorithm, we select CE = 3 and CD = 4. The next smallest is DE = 5, but adding DE would form the cycle C-D-E, so it is rejected. We then select BF = 5 and BD = 6. At this point we have four edges for five vertices, so the MST is complete. The total MST weight is 3 + 4 + 5 + 6 = 18.

使用 Kruskal 算法，我们选择 CE = 3 和 CD = 4。下一个最小边是 DE = 5，但添加 DE 会形成环 C-D-E，因此被拒绝。接着我们选择 BF = 5 和 BD = 6。此时五个顶点已有四条边，因此 MST 完成。MST 总权重为 3 + 4 + 5 + 6 = 18。

The edges incident to deleted vertex A have weights AB = 5, AC = 7, AD = 9, AE = 4, AF = 6. The two shortest are AE = 4 and AB = 5, with total weight 9.

与被删除顶点 A 关联的边权重为 AB = 5、AC = 7、AD = 9、AE = 4、AF = 6。两条最短边是 AE = 4 和 AB = 5，总权重为 9。

Therefore, the lower bound for this TSP is MST weight 18 + two shortest incident edge weights 9 = 27.

Lower bound = 18 + 4 + 5 = 27

因此，该 TSP 的下界为 MST 权重 18 + 两条最短关联边权重 9 = 27。

8. Improving the Bound by Trying Different Vertices | 尝试不同顶点改进下界

Because the lower bound depends on which vertex is deleted, deleting a different vertex may produce a larger lower bound. A larger lower bound is better because it is closer to the true optimal tour length. You should repeat the MST method for several vertices and record each bound.

由于下界取决于删除哪个顶点，删除不同的顶点可能会产生更大的下界。更大的下界更好，因为它更接近真正的最优巡回路线长度。你应该对多个顶点重复 MST 方法并记录每个下界。

For example, deleting vertex B would require finding the MST of A, C, D, E, F and adding the two shortest edges incident to B. The procedure is identical, but the resulting value may be higher or lower than 27. The best lower bound is the maximum of all the bounds found.

例如，删除顶点 B 需要求 A、C、D、E、F 的 MST，并加上与 B 关联的两条最短边。过程完全相同，但得到的值可能高于或低于 27。最佳下界是找到的所有下界中的最大值。

9. Using the Maximum Lower Bound | 使用最大下界

If you have also found an upper bound for the same TSP using a heuristic such as the nearest neighbour algorithm, compare the two values. The maximum lower bound and the minimum upper bound give an interval that must contain the optimal tour length.

如果你还使用最近邻等启发式方法找到了同一 TSP 的上界，请比较这两个值。最大下界和最小上界给出了一个必定包含最优巡回路线长度的区间。

If the maximum lower bound equals the minimum upper bound, then that common value is the exact optimal tour weight. In exam problems, this equality often confirms that the tour used for the upper bound is optimal.

如果最大下界等于最小上界，那么这个共同值就是确切的最优巡回路线权重。在考试题中，这种相等通常可以确认用于求上界的巡回路线是最优的。

10. Common Mistakes and Exam Tips | 常见错误与考试提示

One common mistake is to include the deleted vertex in the MST calculation. Remember that the MST is found only on the remaining vertices after deletion. Another error is to add only one edge back to the deleted vertex, but a TSP tour must

Published by TutorHao | A-Level Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Using a Minimum Spanning Tree Method to Find a Lower Bound | 用最小生成树方法求下界