欢迎来到图论算法 II！

在上一章中，我们学习了如何找出两个特定点之间的最短路径（Dijkstra 算法）。在本章中，我们的角色将从想要从 A 到 B 的“游客”，转变为“送货司机”或“邮差”。

我们要学习的是路径检查算法（Route Inspection Algorithm），它还有一个著名的名称，叫作中国邮差问题（Chinese Postman Problem）。这里的目标不仅仅是到达目的地，而是要走遍网络中每一条边（edge）至少一次，并回到起点，同时确保总行驶距离最短。

先修知识重温：节点基础

在深入研究之前，我们先快速重温课程早前介绍过的两个关键术语：

  • 度数（Degree 或 Valency）：连接到该节点（node）的边的数量。
  • 奇数节点与偶数节点：如果一个节点连接的边数为偶数，它就是偶数节点。如果边数为奇数，它就是奇数节点。

小贴士：在任何图（graph）中，奇数节点的数量永远是偶数（例如：你可以有 0、2 或 4 个奇数节点，但绝对不会有 3 个）。

核心概念：欧拉图（Eulerian Graphs）

对于邮差来说，“完美”的情况是欧拉图。这是一个网络中每一个节点都是偶数节点的情况。

如果所有节点都是偶数，你就可以从任何一个顶点（vertex）出发，刚好走过每一条边一次，并在不重复走过任何一条路的情况下回到起点。这种情况下，你的总距离就是网络中所有边的权重总和。

类比：这就像画一个图形，过程中笔不能离开纸面，也不能重复描绘同一条线。

如果图形不是“完美”的怎么办？

在现实世界中，大多数网络都有奇数节点。如果图中有奇数节点，你就必须重复经过某些边才能回到起点。路径检查算法可以帮助我们决定重复哪些边，以使额外增加的距离降到最低。

情况 1：两个奇数节点

如果有恰好两个奇数节点，该图称为“半欧拉图（Semi-Eulerian）”。要完成路线并回到起点，你必须重复这两个奇数节点之间的最短路径。

2 个奇数节点的操作步骤：
1. 找出两个度数为奇数的节点。
2. 找出它们之间的最短路径（通常可以通过“观察法”得出——直接看图即可）。
3. 将这条最短路径的权重加到网络中所有边的权重总和中。

情况 2：四个奇数节点

这是你在 8FM0 课程中会遇到的最复杂版本。如果有四个奇数节点，你必须将它们两两配对，并重复这些配对之间的最短路径。总共有三种可能的配对方式。

4 个奇数节点的操作步骤：
假设你的奇数节点是 \(A, B, C,\) 和 \(D\)。
1. 列出三种可能的配对方式：
   • 配对 1：\((AB)\) 和 \((CD)\)
   • 配对 2：\((AC)\) 和 \((BD)\)
   • 配对 3：\((AD)\) 和 \((BC)\)
2. 将每种配对的两条路径权重相加，计算出每种配对的总最短距离。
3. 选择总和最小的那一组配对。
4. 将这个“额外”距离加到网络中所有边的权重总和中。

你知道吗？ 这个算法之所以被称为“中国邮差问题”，是因为它是由中国数学家管梅谷（Mei-Ko Kwan）于 1960 年首次研究提出的！

范例详解

想象一个边权重总和为 150km 的小型网络。你发现了四个奇数节点：A, B, C 和 D。

它们之间的最短距离分别为：\(AB = 10, AC = 12, AD = 15, BC = 14, BD = 11, CD = 13\)。

让我们检查一下配对：
1. \((AB + CD) = 10 + 13 = 23\)
2. \((AC + BD) = 12 + 11 = 23\)
3. \((AD + BC) = 15 + 14 = 29\)

配对 1 和配对 2 都给出了最小的额外距离 23。
最终答案： 总路线长度 = \(150 + 23 = 173\text{km}\)。

常见错误提示

  • 忘记加上“权重总和”： 学生经常计算出额外距离（例如 23），却忘记把它加到图中所有原始边的总和上。
  • 遗漏奇数节点： 请务必仔细检查每个节点的度数。如果你漏掉了一个，你的配对就会全错！
  • 没有检查所有 3 种配对： 不要只随手挑选前两个看到的奇数节点。对于 4 个节点，你必须检查所有 3 种组合。

如果刚开始觉得很难，不用担心！ 记住，奇数节点就是“问题区域”。我们只是在试图找出最便宜的方法来“修复”这些问题，方法就是重复走过连接它们的道路。

总结：关键要点

目标：走遍每一条边至少一次并回到起点。

快速检视表：
• 0 个奇数节点： 总距离 = 所有边的总和。
• 2 个奇数节点： 总距离 = 所有边的总和 + 这 2 个奇数节点间的最短路径。
• 4 个奇数节点： 总距离 = 所有边的总和 + 4 个奇数节点的 3 种可能配对中最小的总和。

接下来是什么？

既然你已经能算出路线长度了，接下来请练习列出实际的路线（节点序列）。记住，如果你“重复”了一条边（例如 \(AB\)），你的最终路径必须真的经过 \(A\) 和 \(B\) 两次！