📚 Route Inspection | 路线检查问题（中国邮递员问题）
Route inspection is a graph theory problem that asks for the shortest closed walk which traverses every edge of a connected graph at least once and returns to the starting vertex. It is often called the Chinese postman problem because a postman needs to deliver letters along every street and return to the depot while minimising total walking distance.
路线检查是图论中的一个问题：求一条最短的闭合行走路线，使其至少经过连通图中的每条边一次并回到出发点。它常被称为中国邮递员问题，因为邮递员需要沿每条街道投递信件并返回邮局，同时使总行走距离最小。
1. What is Route Inspection? | 什么是路线检查问题？
Route inspection deals with connected graphs in which each edge represents a road or path that must be covered. The task is to find a route that covers every edge at least once, with the smallest possible total weight. In the standard version, the route must start and finish at the same vertex.
路线检查问题研究的是连通图，其中每条边代表一条必须经过的道路或路径。任务是找到一条覆盖每条边至少一次且总权重尽可能小的路线。在标准版本中，路线必须从同一个顶点出发并返回该顶点。
This problem is different from the travelling salesman problem, which visits every vertex exactly once. Route inspection focuses on edges, not vertices. For this reason, the degrees of vertices and the concept of Eulerian trails are essential.
这个问题与旅行商问题不同，后者要求恰好访问每个顶点一次。路线检查问题关注的是边而不是顶点。因此，顶点的度数以及欧拉路径的概念至关重要。
2. Graph Terminology: Vertices, Edges and Degree | 图论术语：顶点、边与度
A graph consists of vertices (also called nodes) connected by edges (also called arcs). The degree or valency of a vertex is the number of edges incident to it. A loop contributes 2 to the degree of a vertex because it touches the vertex twice.
图由顶点（也称为节点）和连接顶点的边（也称为弧）组成。顶点的度或价是指与该顶点相连的边数。一个环对该顶点的度贡献为 2，因为它两次接触该顶点。
For example, if vertex A is connected to B, C and D by three separate edges, then A has degree 3. In a network representing roads, each street is an edge and each junction is a vertex. The degree of a junction is the number of roads meeting there.
例如，如果顶点 A 通过三条独立的边与 B、C、D 相连，则 A 的度为 3。在表示道路的网络中，每条街道是一条边，每个路口是一个顶点。路口的度就是在此交汇的道路数量。
Knowing the degree of every vertex is the first step in any route inspection problem. Write it next to each vertex before deciding whether the graph is Eulerian, semi-Eulerian, or neither.
在任何路线检查问题中，第一步都是写出每个顶点的度数。在判断图是欧拉图、半欧拉图还是两者都不是之前，先在每个顶点旁标出度数。
3. Odd and Even Vertices | 奇度顶点与偶度顶点
Vertices are classified according to their degree. An odd vertex has an odd degree such as 1, 3 or 5. An even vertex has an even degree such as 0, 2, 4 or 6. This classification is important because Eulerian properties depend on the number of odd vertices.
顶点根据其度数分为奇度顶点和偶度顶点。奇度顶点的度数为奇数，如 1、3、5；偶度顶点的度数为偶数，如 0、2、4、6。这种分类非常重要，因为欧拉性质取决于奇度顶点的数量。
A fundamental theorem states that every graph has an even number of odd vertices. This follows from the handshaking lemma: the sum of all vertex degrees equals twice the number of edges, so the sum must be even. Therefore the number of odd degrees must be even.
一个基本定理指出，任何图中奇度顶点的总数总是偶数。这源于握手引理：所有顶点的度数之和等于边数的两倍，因此度数之和必为偶数。所以奇数度的个数必须为偶数。
In an exam, if you count an odd number of odd vertices, you have made a mistake. Always re-check the degree of each vertex before moving on.
在考试中，如果你数出奇数个奇度顶点，就说明计算出错了。在继续之前，一定要重新检查每个顶点的度数。
4. Eulerian Graphs | 欧拉图
A connected graph is Eulerian if every vertex has even degree. In an Eulerian graph, there exists a closed trail that starts and ends at the same vertex and uses every edge exactly once. This trail is called an Eulerian circuit.
如果连通图中每个顶点都是偶度，则该图为欧拉图。在欧拉图中，存在一条闭合路径，它从某个顶点出发并回到该顶点，且恰好经过每条边一次。这条路径称为欧拉回路。
If a graph is Eulerian, the route inspection problem is solved immediately: no edges need to be repeated. The shortest inspection route length is simply the sum of all original edge weights.
如果图是欧拉图，路线检查问题就立即解决：无需重复任何边。最短检查路线长度就是所有原始边权之和。
This is the ideal case. In practice, many road networks are not Eulerian, because some junctions have an odd number of streets meeting them.
这是最理想的情况。实际上，许多道路网络并不是欧拉图，因为有些路口有奇数条街道交汇。
5. Semi-Eulerian Graphs | 半欧拉图
A connected graph is semi-Eulerian if it has exactly two odd vertices. In this case, an Eulerian trail exists that starts at one odd vertex, ends at the other odd vertex, and uses every edge exactly once.
如果连通图中恰好有两个奇度顶点，则该图为半欧拉图。此时存在一条欧拉路径，它从一个奇度顶点出发，到达另一个奇度顶点，并恰好经过每条边一次。
This is useful when the inspection route can start and end at different places. However, if the postman must return to the starting point, then the route must be closed. To close the trail in a semi-Eulerian graph, the postman needs to repeat the shortest path between the two odd vertices.
当检查路线可以在不同地点开始和结束时，这一点很有用。但如果邮递员必须回到出发点，路线就必须闭合。为了在半欧拉图中闭合路径，邮递员需要重复两个奇度顶点之间的最短路径。
The extra distance added is exactly the length of that shortest path. The total closed route length is the total edge weight plus this shortest path length.
所增加的额外路程正是这条最短路径的长度。闭合路线总长度等于总边权加上这条最短路径的长度。
6. Why Edges Must Sometimes Be Repeated | 为什么有时必须重复边
If a connected graph has more than two odd vertices, neither an Eulerian circuit nor an Eulerian trail exists. For example, a graph with four odd vertices cannot be traversed by a route using every edge exactly once.
如果连通图有两个以上的奇度顶点，则既不存在欧拉回路也不存在欧拉路径。例如，具有四个奇度顶点的图不可能用一条恰好经过每条边一次的路线走完。
However, the postman can still complete the delivery by repeating certain edges. Repeating an edge means walking along it twice, so its weight is counted again in the total distance. The challenge is to choose which edges to repeat so that every vertex becomes even.
然而，邮递员仍然可以通过重复某些边来完成投递。重复一条边意味着沿它走两次，因此它的权重会再次计入总距离。难点在于选择要重复哪些边，使每个顶点都变成偶度。
Mathematically, repeating an edge along a path connecting two odd vertices changes the parity of both endpoints: odd vertices become even, and even vertices remain even if the path passes through them in pairs. The aim is to pair up all odd vertices using the cheapest possible connecting paths.
从数学上讲，重复连接两个奇度顶点的路径会改变这两个端点的奇偶性：奇度顶点变成偶度，而如果路径成对经过偶度顶点，它们仍保持偶度。目标是用尽可能便宜的连接路径将所有奇度顶点配对。
7. Route Inspection Algorithm | 路线检查算法
The standard route inspection algorithm for an undirected graph is systematic. It guarantees the minimum extra distance needed to make the graph Eulerian.
无向图的标准路线检查算法是系统性的。它能保证找到使图变为欧拉图所需的最小额外路程。
- Step 1: Identify all odd vertices in the graph. 第 1 步：找出图中所有奇度顶点。
- Step 2: List all possible complete pairings of these odd vertices. 第 2 步：列出这些奇度顶点的所有可能的完整配对方案。
- Step 3: For each pair, find the shortest path distance between the two vertices, not just the direct edge weight. 第 3 步：对每对顶点，找出它们之间的最短路径长度，而不仅仅是直接边权。
- Step 4: For each complete pairing scheme, add the distances of all pairs together. 第 4 步
Published by TutorHao | A-Level Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply