✳flâneur — a map of the web's best reading

Chinese postman problem - Wikipedia

en.wikipedia.org · 1,524 words · saved by 1 readers

In graph theory, a branch of mathematics and computer science, 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.[1] It can be solved in polynomial time.[2] The problem was originally studied by the Chinese mathematician Kwan Mei-Ko in 1960, whose Chinese paper was translated into English in 1962.[3] 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 U.S. National Bureau

Chinese postman problem - Wikipedia Jump to content From Wikipedia, the free encyclopedia Finding shortest walks through all graph edges A worked example of an undirected Chinese postman problem: 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 ,

Explore this link on the map →

related reading