📚 Route Inspection: Chinese Postman Problem | 路径检查：中国邮递员问题
In many real-world situations, such as postal delivery, street sweeping or meter reading, a person or vehicle must traverse every street in a network at least once, starting and ending at the same point, while covering the shortest possible total distance. This classic optimisation challenge is known as the Chinese Postman Problem, or Route Inspection Problem. This article explains the key concepts required for the Edexcel A-Level Decision Mathematics module, including Eulerian and semi-Eulerian graphs, identification of odd vertices, and the pairing method used to find an optimal solution.
在许多实际场景中，例如邮递派送、街道清扫或抄表，工作人员须从某点出发并最终返回，途经每条街道至少一次，且要求总路程最短。这个经典的优化问题被称为中国邮递员问题，亦称路径检查问题。本文讲解Edexcel A-Level决策数学模块所需的关键概念，包括欧拉图与半欧拉图、奇顶点的识别，以及通过配对法求出最优解的步骤。
1. Graph Theory Foundations | 图论基础
A network is modelled as a graph consisting of vertices (nodes) and edges (arcs). Edges may be assigned weights, typically representing distances, times or costs. In route inspection, we assume the graph is connected and we must travel along every edge, possibly repeating some edges to minimise total weight.
网络被模拟为一个由顶点（节点）和边（弧）构成的图。边可能被赋予权重，通常表示距离、时间或成本。在路径检查中，我们假定图是连通的，并且必须经过每一条边，可重复某些边以最小化总权重。
The degree of a vertex is the number of edges incident to it. A vertex is odd if its degree is an odd number, and even if its degree is even. The sum of all vertex degrees in any graph is twice the number of edges, hence it is always even; therefore the number of odd vertices is always even.
顶点的度是指与该点相连的边的数目。若度为奇数则称奇顶点，度为偶数则称偶顶点。任何图中所有顶点度之和为边数的两倍，因而总是偶数；所以奇顶点的个数必定为偶数。
2. Eulerian Graphs: No Repeated Edges Needed | 欧拉图：无需重复边
A graph is Eulerian if it contains a closed trail that uses every edge exactly once. This is known as an Eulerian circuit. A necessary and sufficient condition for a connected graph to be Eulerian is that every vertex has even degree. In such a network, the shortest route is simply an Eulerian circuit, with total weight equal to the sum of all edge weights, and no edge needs to be traversed more than once.
如果一个连通图存在一条包含每条边恰好一次的闭合路径，则该图是欧拉图。该闭合路径称为欧拉回路。一个连通图是欧拉图的充要条件是所有顶点度数均为偶数。在这样的网络中，最短路径就是一个欧拉回路，总权重等于所有边权之和，且不需要重复走任何一条边。
3. Semi-Eulerian Graphs: Start and End Differ | 半欧拉图：起点终点不同
A connected graph is semi-Eulerian if it admits a trail that uses every edge exactly once but starts and ends at different vertices. This occurs precisely when the graph has exactly two odd vertices; all others are even. The trail must begin at one odd vertex and end at the other. In route inspection, if we must start and finish at the same point, a semi-Eulerian graph still requires extra traversal to return to the start, making it a special case of the Chinese Postman Problem.
若一个连通图存在一条恰好经过每条边一次但起点与终点不同的路径，则该图是半欧拉图。这恰好发生在图中仅有两个奇顶点，其余均为偶顶点的情形。该路径必须从一个奇顶点出发，在另一个奇顶点结束。在路径检查中，如果要求出发并返回同一点，半欧拉图仍需额外行走以回到起点，这便成为中邮问题的一种特殊情况。
4. The Chinese Postman Problem Defined | 中国邮递员问题定义
The Chinese Postman Problem asks for a closed walk of minimum total weight that traverses every edge at least once, starting and ending at the same vertex. When the graph is Eulerian, the answer is trivial. If not, some edges must be duplicated. The objective is to determine which edges to repeat so that all vertices become even, and the total weight of the duplicated edges is minimised. The route will then be an Eulerian circuit on the augmented graph (the original graph plus the duplicated edges).
中国邮递员问题要求找出一个总权重最小的闭合行走，该行走从某点出发并回到该点，且每条边至少被经过一次。当图为欧拉图时，答案显然。若否，必须重复某些边。目标在于确定应重复哪些边，使得所有顶点度数变为偶数，且重复边的总权重最小。随后，增广图（原图加上重复边）上的欧拉回路即是所求路径。
5. Identifying Odd Vertices | 找出奇顶点
Begin by listing all vertices and their degrees. Circle or highlight those with odd degree. Because the number of odd vertices is even, we can have 2, 4, 6, … odd vertices. In Edexcel examinations, networks rarely have more than four odd vertices; the method extends to larger sets but requires systematic pairing.
首先列出所有顶点及其度数，圈出或标出度数为奇的点。因为奇顶点个数为偶数，可能为2、4、6……。在Edexcel考试中，网络通常不超过四个奇顶点；方法可推广到更多，但需系统配对。
For example, consider a graph with vertices A, B, C, D, E, with degrees: A(3), B(3), C(4), D(2), E(2). Here A and B are the only odd vertices (two odd vertices). If instead A(3), B(3), C(3), D(3), E(2) then we have four odd vertices.
例如，某图有顶点A、B、C、D、E，度数分别为 A 3, B 3, C 4, D 2, E 2。则仅A和B为奇顶点（两个奇顶点）。若度数为 A 3, B 3, C 3, D 3, E 2，则存在四个奇顶点。
6. Adding Repeated Edges for Two Odd Vertices | 两个奇顶点的重复边添加
If the graph has exactly two odd vertices, the Chinese Postman route is found by finding the shortest path between those two odd vertices and traversing that path twice (once as part of the original walk and once as the return leg). In effect, the edges along that shortest path are duplicated. The total weight becomes (sum of all original edge weights) + (length of the shortest path between the two odds). The start/end vertex can be any even vertex or one of the odd vertices after duplication.
若图恰好有两个奇顶点，中国邮递员路径可以通过找到这两个奇顶点之间的最短路径，并将该路径走两遍（一次作为原有行走的一部分，一次作为返回行程）得到。实际上，该最短路径上的边被复制。总权重变为（原图所有边权和） + （两奇顶点间最短路径长度）。起点/终点可选任一个偶顶点或复制后的奇顶点之一。
7. When There Are Four Odd Vertices: Pairing Approach | 四个奇顶点：配对方法
When the network has four odd vertices, we need to make the graph Eulerian by adding extra edges connecting these odd vertices in pairs. There are three possible ways to pair them: (odd1,odd2) together with (odd3,odd4), (odd1,odd3) with (odd2,odd4), or (odd1,odd4) with (odd2,odd3). For each pairing, we find the shortest distance between each pair and sum these two distances. The chosen pairing is the one that gives the smallest total extra distance. We then duplicate the edges along both shortest paths, turning all odd vertices into even ones.
当网络有四个奇顶点时，需要通过添加额外边，将这些奇顶点两两配对连接，使图成为欧拉图。共有三种可能的配对方式：(奇₁,奇₂)与(奇₃,奇₄)；(奇₁,奇₃)与(奇₂,奇₄)；(奇₁,奇₄)与(奇₂,奇₃)。对每种配对，找出每对之间的最短距离并求和。选择总额外距离最小的配对。接着将这两条最短路径上的边进行复制，所有奇顶点即变为偶顶点。
8. Finding Shortest Distances Between Odd Vertices | 找奇顶点之间的最短距离
To apply the pairing method, we first construct a complete distance table for the odd vertices. Use Dijkstra’s algorithm or Floyd’s algorithm (or simply inspect small networks) to determine the length of the shortest path between each pair of odd vertices. Record these values in a matrix. For a network with four odd vertices, say P, Q, R, S, we find d(P,Q), d(P,R), d(P,S), d(Q,R), d(Q,S), d(R,S).
要运用配对法，首先为奇顶点构建完整的距离表格。使用Dijkstra算法或Floyd算法（小型网络可直接观察）确定每对奇顶点之间最短路径的长度。将这些数值记录在矩阵中。对于有P、Q、R、S四个奇顶点的网络，我们需要求出d(P,Q)、d(P,R)、d(P,S)、d(Q,R)、d(Q,S)、d(R,S)。
These shortest paths may pass through even vertices. It is the total length that matters, not the intermediate nodes. When duplicating, we add the edges that lie on that shortest path.
这些最短路径可能经过偶顶点。重要的是总长度，而非中间节点。复制时，我们添加的是位于该最短路径上的边。
9. Choosing the Minimum Pairing | 选择最小配对
List the three possible pairings and compute the total extra distance for each:
| Pairing | Total extra weight |
|---|---|
| (P,Q) & (R,S) | d(P,Q) + d(R,S) |
| (P,R) & (Q,S) | d(P,R) + d(Q,S) |
| (P,S) & (Q,R) | d(P,S) + d(Q,R) |
Select the pairing that yields the smallest total. This is effectively a minimum weight perfect matching on the complete graph formed by odd vertices.
列出三种配对并计算每种的总额外距离：
| 配对 | 总额外权重 |
|---|---|
| (P,Q) 与 (R,S) | d(P,Q) + d(R,S) |
| (P,R) 与 (Q,S) | d(P,R) + d(Q,S) |
| (P,S) 与 (Q,R) | d(P,S) + d(Q,R) |
选择总和最小的配对。这本质上是奇顶点形成的完全图上的最小权重完美匹配。
10. Constructing the Eulerian Circuit on the Augmented Graph | 在增广图上构造欧拉回路
Once the extra edges are added (duplicating the edges along the chosen shortest paths), all vertices in the augmented graph have even degree. The graph is now Eulerian. We can find an Eulerian circuit using a standard method such as Hierholzer’s algorithm or by listing edges systematically. The total weight of the Chinese Postman tour is the sum of original edge weights plus the total extra weight from the chosen pairing.
一旦添加了额外边（即重复所选定最短路径上的边），增广图中所有顶点度数均为偶数。该图现为欧拉图。我们可以使用标准方法，如Hierholzer算法或系统地列出边，找出欧拉回路。中国邮递员回路的总权重等于原边权和加上所选配对的总额外权重。
Total tour length = Σ(original edges) + minimum extra distance
总路径长度 = 原图边权和 + 最小额外距离
11. Worked Example with Four Odd Vertices | 四奇顶点例题演示
Consider a network with vertices A, B, C, D, E and edges: AB(5), AC(7), AD(4), BC(3), BD(6), BE(8), CD(2), CE(9), DE(4). Vertex degrees: A(3) odd, B(3) odd, C(3) odd, D(3) odd, E(3) odd? Wait, that gives five odd vertices – impossible. Let’s design a proper example with four odds. Use A(2) even, B(3) odd, C(3) odd, D(3) odd, E(3) odd. Connect as: AB(4), AC(5), AD(6), BC(7), BD(8), BE(3), CD(2), CE(9), DE(1). But let us create a simpler, exam-style network with clear shortest paths.
设想一个更清晰的考试型网络，顶点P、Q、R、S、T。边及权：PQ(5), PS(7), QT(4), QR(6), RS(3), RT(8), ST(2)。度数：P：2 (PQ,PS) = 偶？P连Q和S，度2偶；Q连P,T,R度3奇；R连Q,S,T度3奇；S连P,R,T度3奇；T连Q,R,S度3奇。这样有四个奇顶点 Q,R,S,T。完美。
原边权和 =5+7+4+6+3+8+2=35。奇顶点：Q,R,S,T。求出它们之间的最短距离（可通过检查或应用Dijkstra）：
- Q到R直接：6；也可Q-T-R:4+8=12，直接路径更短，d(Q,R)=6
- Q到S: Q-R-S:6+3=9, Q-T-S:4+2=6, 所以d(Q,S)=6
- Q到T: 4 直接，d(Q,T)=4
- R到S: 3直接，d(R,S)=3
- R到T: R-T 8直接，R-S-T 3+2=5, 所以d(R,T)=5
- S到T: 2直接，d(S,T)=2
三种配对：
(Q,R)与(S,T): 6 + 2 = 8
(Q,S)与(R,T): 6 + 5 = 11
(Q,T)与(R,S): 4 + 3 = 7 ← 最小
因此选择配对(Q,T)与(R,S)，重复边为Q-T和R-S。增广图总权重 = 35 + 7 = 42。然后可找出欧拉回路：例如 P – Q – T – S – P – S – R – Q – R – T – P… 适当排列使所有边被遍历。最终回路总长42。
12. More Than Four Odd Vertices and Exam Tips | 多于四个奇顶点及考试提示
In principle, the same method extends to 6, 8, … odd vertices. You create a complete graph of odd vertices with edge weights equal to shortest path distances, then find a minimum weight perfect matching. This can be solved by systematic listing when the number is small, or by using a systematic algorithm. Edexcel D1 typically restricts to up to four odd vertices where simple enumeration suffices.
原则上，同一方法可推广至6、8……个奇顶点。构建奇顶点的完全图，边权为最短路径距离，然后求最小权重完美匹配。当数量少时可通过系统列举求解，或使用系统化算法。Edexcel D1通常限定在不超过四个奇顶点，简单的枚举即可胜任。
In the exam, always show the degree calculation, list odds, find shortest paths between them (show working for Dijkstra if required), list all pairings with total extra weights, and state clearly which pairing is optimal. Write the total tour length, and sketch or describe one possible Eulerian circuit on the augmented graph. Pay attention to precision with weights and the final route.
考试时，务必展示度数计算、列出奇顶点、求出它们之间的最短路径（若需要则展示Dijkstra算法的步骤）、列出所有配对及其总额外权重，并明确指出哪个配对最优。写下总路径长度，并在增广图上画或描述一条可能的欧拉回路。注意权重的准确性和最终路径的描述。
Published by TutorHao | Route Inspection Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图