邮递员问题

邮递员问题（也称邮路问题，Route Inspection Problem，或中国邮路问题,China Route Inspection Problem，或中国邮递员问题Chinese Postman Problem）是一个图论问题。此问题为在一个连通的无向图中找到一最短的封闭路径，且此路径需通过所有边至少一次。
简单来说，邮递员问题就是在一个已知的地区，邮差要设法找到一条最短路径，可以走过此地区所有的街道，且最后要回到出发点，
此问题是图遍历问题的一种。无向图的中国邮路问题是容易解决的，是P问题；而有向图的中国邮路问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出，而美国国家标准和技术研究院（NIST）的 Alan Goldman 首先将此问题命名为中国邮路问题。

无向图上中国邮路问题的解法

若图中有欧拉回路，因为欧拉回路通过所有的边，因此任何一个欧拉回路即为此问题的解。
若图中不存在欧拉回路，其中必存在有奇数个边的端点，且这类的端点一定大于等于2个。因此有些边需要再重复一次，使奇数边的端点变为偶数边的端点。
假设有一个镇有14条路及9个路口（路口分别编号为1,2, …,9），其路和路口对应的图（右边第1 图，边上的数字是各边的cost）中有4个端点（编号 1, 3, 6 及9）有奇数个边通过，因此这个图不存在欧拉回路。后续要作的在图中使几个边重复，使图中所有的端点均有偶数边通过。例如若图中{1,3} 及 {6.9} 边重复，所有的端点均有偶数边通过。不过增加的长度不一定最少。
为了要确定重复哪个边可以使原图的端点都有偶数边通过，且增加长度最少。先画出所有奇数边的端点的完全图  （右边第2 图），边上的数字是从一端点到另一端点（可以经过其他完全图 中省略的点）的最短长度。若选择边{1,6} 及 {3,9}，所有端点都经过一次，而总长度最短。
因此原来的图中，连接端点1 和 6, 端点 3 和 9 的边再重复一次，所有端点均有偶数个边通过（右边第3 图）。因此任一个欧拉路径即为此问题的解答，如以下的端点顺序(1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1) 即为一解。图中红色的部分即为重复的边。