Editing Chinese postman problem (section)

{{Short description|Finding shortest walks through all graph edges}}
[[File:Chinese_postman_problem.svg|thumb|upright=1.5|A worked example of an undirected Chinese postman problem:
{{ordered list|Each street must be traversed at least once, starting and ending at the post office at A.|Four vertices with odd degree (orange) are found on its equivalent graph.| The pairing with the lowest total length is found.| After corresponding edges are added (red), the length of the Eulerian circuit is found.}}]]
In [[graph theory]] and [[combinatorial optimization]], '''Guan's route problem''', the '''Chinese postman problem''', '''postman tour'''  or '''route inspection problem''' is to find a shortest closed path or circuit that visits every edge of an (connected) [[undirected graph]] at least once. When the graph has an [[Eulerian circuit]] (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the [[optimization problem]] is to find the smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting [[multigraph]] does have an Eulerian circuit.<ref>{{citation|first1=Fred S.|last1=Roberts|first2=Barry|last2=Tesman|title=Applied Combinatorics|edition=2nd|year=2009|publisher=CRC Press|isbn=9781420099829|pages=640–642}}</ref> It can be solved in [[polynomial time]],<ref name = "EdmondsJohnson" /> unlike the [[Travelling salesman problem|Travelling Salesman Problem]] which is [[NP-hardness|NP-hard]].<ref>{{Cite web |title=The Travelling Salesman Problem |url=http://staff.ustc.edu.cn/~xujm/Graph21.pdf}}</ref> It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes and does not have to visit every edge.

The problem was originally studied by the Chinese mathematician [[Meigu Guan]] in 1960, whose Chinese paper was translated into English in 1962.<ref>{{citation
 | last = Kwan | first = Mei-ko | author-link = Meigu Guan
 | journal = [[Acta Mathematica Sinica]]
 | language = zh
 | mr = 0162630
 | pages = 263–266
 | title = Graphic programming using odd or even points
 | volume = 10
 | year = 1960}}. Translated in ''Chinese Mathematics'' '''1''': 273–277, 1962.</ref> The original name "Chinese postman problem" was coined in his honor; different sources credit the coinage either to [[Alan J. Goldman]] or [[Jack Edmonds]], both of whom were at the [[NIST|U.S. National Bureau of Standards]] at the time.<ref>{{citation|contribution=Chinese postman problem|title=Dictionary of Algorithms and Data Structures|editor1-first=Vreda|editor1-last=Pieterse|editor2-first=Paul E.|editor2-last=Black|date=September 2, 2014|access-date=2016-04-26|contribution-url=https://xlinux.nist.gov/dads/HTML/chinesePostman.html|publisher=[[National Institute of Standards and Technology]]}}</ref><ref>{{citation
 | last1 = Grötschel | first1 = Martin | author1-link = Martin Grötschel
 | last2 = Yuan | first2 = Ya-xiang
 | department = Optimization stories: 21st International Symposium on Mathematical Programming, Berlin, August 19–24, 2012
 | journal = Documenta Mathematica
 | mr = 2991468
 | pages = 43–50
 | title = Euler, Mei-Ko Kwan, Königsberg, and a Chinese postman
 | series = Documenta Mathematica Series | url = http://www.emis.de/journals/DMJDMV/vol-ismp/vol-ismp-all.pdf
 | volume = Extra
 | year = 2012| doi = 10.4171/dms/6/10 | doi-access = free | isbn = 978-3-936609-58-5 }}.</ref>

A generalization takes as input any set ''T'' of evenly many vertices, and must produce as output a minimum-weight edge set in the graph whose odd-degree vertices are precisely those of ''T''. This output is called a ''T''-join.  This problem, the '''''T''-join problem''', is also solvable in polynomial time by the same approach that solves the postman problem.