# 图论应用：中国邮路问题（CPP）和旅行商问题（TSP）

> IB 数学 AI HL · IB 数学 AI HL
> 来源: https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/

本模块讲解图论的两个核心最优化应用：用于规划覆盖所有边路线的中国邮路问题（CPP），以及用于访问所有顶点的旅行商问题（TSP）。我们会讲解考试要求的求解方法和常见误区。

**先修:** [基础图论术语和性质](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-introduction-to-graph-theory/); [最小生成树算法](https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-minimum-spanning-trees/)

## 学习目标

- 区分中国邮路问题（CPP）和旅行商问题（TSP）
- 求解含0个或2个奇度顶点连通图的CPP问题
- 使用IB标准方法计算TSP的上界和下界
- 在真实世界最优化场景中解读CPP和TSP的解

## 中国邮路问题（CPP）

**中国邮路问题** — 寻找最短闭合路径的问题，要求该路径至少遍历无向连通图的每一条边一次，起点和终点为同一个顶点。

*例:* 规划覆盖街区所有街道的邮政路线，最终回到配送仓库。

CPP的解取决于图中奇度顶点的数量。根据欧拉握手引理，任何图的奇顶点数量都是偶数。IB AI HL仅考察含0个或2个奇顶点的CPP问题。

1. 如果**0个奇顶点**：图是欧拉图，最优路线就是欧拉回路，总权重 = 所有边权重之和。
2. 如果**2个奇顶点**：最优路线需要重复两个奇顶点之间的最短路径。总权重 = 所有边权重之和 + 重复路径的权重。
3. 如果奇顶点数量超过2：配对奇顶点，重复配对之间的最短路径以得到最小额外权重（IB AI HL不考察）。

**例题:** 一个连通图有4个顶点A、B、C、D，度数分别为：A(2，偶)、B(3，奇)、C(2，偶)、D(1，奇)。所有边权重之和为22。B和D之间的最短路径总权重为5。求最优CPP路线的长度。

1. 步骤1：统计奇度顶点的数量。共有2个奇顶点：B和D。
2. 步骤2：对于2个奇顶点的情况，将两个顶点之间最短路径的权重加到所有边的总权重上：
3. $$\text{Total optimal length} = 22 + 5 = 27$$

> **考试提示:** 求解CPP问题前一定要先检查每个顶点的度数；数错奇顶点是最常见的早期错误。

*计算器:* allowed

## 旅行商问题（TSP）简介

**旅行商问题** — 寻找最小总权重哈密顿回路的最优化问题，要求该回路恰好访问图的每个顶点一次，最终回到起点顶点。

*例:* 规划访问每个城市各一次后回到中心仓库的配送路线。

与CPP不同，对于大型图，没有简单高效的算法可以找到TSP的精确最优解。在IB AI HL考试中，大多数问题只要求你计算最优解的上下界，不需要找到精确值。

**概念自测**

检查你对CPP和TSP区别的理解：

1. 哪个问题要求至少遍历每一条边一次？

   - CPP
   - TSP

   *答案:* CPP

   *解析:* 正确！CPP的核心要求是覆盖所有边，而TSP覆盖所有顶点。

2. 哪个问题要求恰好访问每个顶点一次（起点/终点除外）？

   - CPP
   - TSP

   *答案:* TSP

   *解析:* 正确！TSP要求访问每个顶点一次，而CPP可以重复访问顶点。

*计算器:* allowed

## 求解TSP的上界

TSP的上界是一个保证大于或等于真实最优解的总权重。IB AI HL求解上界的标准方法是最近邻算法：

1. 从题目给定的起点顶点出发
2. 移动到当前顶点出发未访问过的、边权重最小的顶点
3. 重复直到所有顶点都被访问
4. 加上最后一个顶点回到起点顶点的边权重，闭合回路

**例题:** 从顶点A出发，使用最近邻算法为该对称TSP求上界：边权重为 $AB=3$，$AC=6$，$AD=3$，$BC=5$，$BD=4$，$CD=2$。

1. 步骤1：从A出发。未访问顶点是B、C、D。A出发最小边是AB=3和AD=3；先选AD。目前总权重：3。
2. 步骤2：当前顶点D。未访问顶点是B、C。D出发最小边是CD=2。移动到C。目前总权重：$3 + 2 = 5$。
3. 步骤3：当前顶点C。仅剩下未访问顶点B。边CB=5。移动到B。目前总权重：$5 + 5 = 10$。
4. 步骤4：所有顶点都已访问。从B返回A。边BA=3。计算上界总权重：
5. $$\text{Upper bound} = 10 + 3 = 13$$

> **tip**
>
> 若要得到最优（最小）上界，从每个顶点出发分别运行最近邻算法，然后选择得到的最小总权重。如果题目要求最优上界，一定要这么做。

*计算器:* allowed

## 求解TSP的下界

TSP的下界是一个保证小于或等于真实最优解的值。IB AI HL的标准方法使用最小生成树（MST）：

1. 从原图中删除任意一个顶点
2. 找到剩余图的最小生成树（MST）
3. 将连接被删除顶点的两个最小不同边的权重加到MST权重上
4. 得到的总和就是下界

**例题:** 对前一个例子中的TSP（边权重：$AB=3$，$AC=6$，$AD=3$，$BC=5$，$BD=4$，$CD=2$），删除顶点A后求下界。

1. 步骤1：删除顶点A。剩余顶点是B、C、D。
2. 步骤2：找到剩余图的MST。MST使用边CD=2和BD=4，因此MST总权重为 $2 + 4 = 6$。
3. 步骤3：得到连接被删除顶点A的两个最小边。A的边为AB=3、AD=3、AC=6，因此两个最小边是3和3。
4. 步骤4：计算下界总权重：
5. $$\text{Lower bound} = 6 + 3 + 3 = 12$$

*计算器:* allowed

## 常见错误

- **错误做法:** 混淆CPP和TSP的要求，把CPP问题当成需要访问所有顶点而非所有边来求解。
  - 原因: 两个问题的核心目标完全不同，混淆会导致错误解。
  - 正确做法: 一定要先确认问题类型：CPP = 覆盖所有边，TSP = 访问所有顶点。
- **错误做法:** 对于含2个奇顶点的CPP问题，忘记将重复路径的权重加到所有边的总权重上。
  - 原因: 很多学生只报告重复路径的权重，而不是完整路线的权重。
  - 正确做法: 求解CPP时，一定要将重复路径的权重加到所有原边权重的总和上。
- **错误做法:** 在TSP的最近邻算法中，访问完所有顶点就停止，忘记加上回到起点的返回边。
  - 原因: TSP要求闭合回路回到起点，这一步是得满分必须的。
  - 正确做法: 一定要加上最后一个顶点回到起点的边权重，才能得到总上界。
- **错误做法:** 计算TSP下界时，只加了一条连接被删除顶点的边，而非两条。
  - 原因: TSP回路必须进出被删除顶点，因此需要两条不同的边。
  - 正确做法: 计算下界时，一定要加上连接被删除顶点的两个最小不同边的权重。

## 速查表

| 问题类型 | 核心要求 | 关键求解规则 |
| --- | --- | --- |
| CPP（0个奇顶点） | 遍历所有边，回到起点 | 最优值 = 所有边权重之和 |
| CPP（2个奇顶点） | 遍历所有边，回到起点 | 最优值 = 所有边权重之和 + 奇顶点之间最短路径权重 |
| TSP 上界 | 访问所有顶点，回到起点 | 最近邻法：从给定顶点出发，选最近未访问顶点，加返回边 |
| TSP 下界 | 访问所有顶点，回到起点 | 删除1个顶点，求剩余图MST，加连接删除顶点的两个最小边 |

## 下一步

CPP和TSP是核心最优化主题，经常作为扩展回答题出现在IB AI HL试卷2中，广泛应用于真实世界物流、配送路线规划和网络设计。掌握这些方法建立在你对图基础和最小生成树的理解上，也为你学习更高级的网络问题（如项目管理的关键路径分析）做准备。这些主题也为大学学习运筹学、计算机科学和数据分析打下坚实基础。

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/