查看“︁中国邮递员问题”︁的源代码

'''中国邮递员问题'''（也称路线检查问题，Route Inspection Problem）是一个[[图论]]问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑，且此路徑需通過所有邊至少一次。现实意义中，中国邮递员问题就是在一個已知的地區，[[郵差]]要設法找到一條最短路徑，走過此地區所有的街道，且最後要回到出發點。

此問題是[[圖的遍歷|圖遍歷]]問題的一種。无向图的中国邮递员问题是容易解决的，是[[P问题]]；而有向图的中国邮递员问题是[[NP完全问题]]。中国邮递员问题由[[管梅谷]]教授在1960年提出，而[[美國國家標準和技術研究院]]（NIST）的 Alan Goldman 首先將此問題命名为中国邮递员问题。<ref>{{cite web | url=http://www.nist.gov/dads/HTML/chinesePostman.html | title="Chinese Postman Problem" | accessdate=2009-02-19 | archive-date=2008-10-17 | archive-url=https://web.archive.org/web/20081017094141/http://www.nist.gov/dads/HTML/chinesePostman.html | dead-url=no }}</ref>

== 无向图上中国邮递员问题的解法 ==

若圖中有[[歐拉迴路]]，因為歐拉迴路通過所有的邊，因此任何一個歐拉迴路即為此問題的解。

若圖中不存在[[歐拉迴路]]，其中必存在有奇數個邊的端點，且這類的端點一定大於等于2個。因此有些邊需要再重覆一次，使奇數邊的端點變為偶數邊的端點。

[[File:Chinespostman 1.png|thumb|用圖來模擬一個鎮的街道，標示紅色的路口有奇數條路通過。]]

假設有一個鎮有14條路及9個路口（路口分別編號為 1,2, …,9），其路和路口對應的圖（右邊第 1 圖，邊上的數字是各邊的 cost）中有4個端點（編號 1, 3, 6 及9）有奇數個邊通過，因此這個圖不存在歐拉迴路。後續要作的在圖中使幾個邊重覆，使圖中所有的端點均有偶數邊通過。例如若圖中 {1,3} 及 {6.9} 邊重覆，所有的端點均有偶數邊通過。不過增加的長度不一定最少。

[[File:Chinespostman 2.png|thumb|所有奇數邊端點組成的<math>K_4</math>完全圖。]]

為了要確定重覆哪個邊可以使原圖的端點都有偶數邊通過，且增加長度最少。先畫出所有奇數邊的端點的[[完全圖]] <math>K_4</math> （右邊第 2 圖），邊上的數字是從一端點到另一端點（可以經過其他完全圖 <math>K_4</math> 中省略的點）的最短長度。若選擇邊 {1,6} 及 {3,9}，所有端點都經過一次，而總長度 <math>4+2=6</math>最短。

[[File:Chinespostman 3.png|thumb|最後的解，紅色部份是新增的邊及其對應的長度。]]

因此原來的圖中，連接端點 1 和 6, 端點 3 和 9 的邊再重覆一次，所有端點均有偶數個邊通過（右邊第 3 圖）。因此任一個歐拉路徑即為此問題的解答，如以下的端點順序 (1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1) 即為一解。圖中紅色的部份即為重複的邊。

== 参考文献 ==
{{Reflist}}

== 參見 ==
*[[一筆畫問題]]
*[[漢彌爾頓路徑問題]]
*[[旅行推銷員問題]]

== 外部連結 ==
*[http://mathworld.wolfram.com/ChinesePostmanProblem.html Chinese Postman Problem] {{Wayback|url=http://mathworld.wolfram.com/ChinesePostmanProblem.html |date=20090225130434 }}
[[Category:圖論]]
[[Category:NP完全问题]]