史记

中国邮递员问题

简介

中国邮递员问题是一个著名的数学难题，它询问一个邮递员能否沿着一条连续的路径递送信件，该路径会经过所有街道一次且仅一次，并返回出发点。

多级标题

历史

该问题最初由欧拉在 1736 年提出，他研究了哥尼斯堡的七座桥是否可以沿着一条连续的路径穿过。

欧拉证明，对于欧拉路径（可以通过单条路径连接所有顶点的路径）的存在，图中所有顶点的度（与之相连的边的数量）必须偶数。

中国邮递员问题的正式表述

给定一个图，其中每个顶点代表一个路口，每条边代表连接两个路口的街道。邮递员问题询问是否存在一条欧拉路径，称为中国邮递员路径，可以沿着该路径覆盖图中的所有边。

必要条件

与欧拉路径类似，中国邮递员路径的存在也受以下必要条件约束：

图中所有顶点的度之和必须为偶数。

图中最多只能有两个奇数度顶点（奇数度顶点是与奇数条边相连的顶点）。

算法

如果图满足中国邮递员路径存在的必要条件，则可以使用以下算法找到路径：1. 找到两个奇数度顶点（如果有的话）。 2. 将这两个顶点连接一条新边，形成一个新的图。 3. 在新图中找到欧拉回路。 4. 从欧拉回路中删除新边，得到中国邮递员路径。

应用

中国邮递员问题在现实生活中有很多应用，包括：

路线规划

垃圾收集

公共交通规划

其他相关问题

中国邮递员问题是图论中一个更广泛问题的特例，称为邮递员问题。邮递员问题询问是否存在一条最短路径，可以穿过给定图中的所有边一次且仅一次。