Postman problem
The postman problem is a model from graph theory in which one uses the transmitted image of a postman delivering letters on the shortest route: A postman is supposed to deliver the letters (on both sides of the street at the same time) in a street network (city).
The postman problem got its English name ( Chinese postman problem ) by Alan Goldman after the Chinese mathematician Mei Ko Kwan , who first investigated the problem in 1962 . A solution was given in 1973 by Jack Edmonds and Ellis L. Johnson .
Modeling the problem with graphs
The problem is modeled using graphs . Streets are modeled as edges and intersections as nodes . The length of the corresponding street is assigned to the edges. What is now required is a shortest cycle that runs through all streets at least once.
the solution of the problem
The solution to the problem depends on the resulting graph. In Eulerian graphs (connected graph with even nodal degrees ) the shortest route corresponds to an Euler tour that runs through each edge exactly once . In general, the problem can be solved by making the graph Eulerian by inserting further edges at a minimum cost and thereby reducing the problem to finding an Euler tour. If a connected graph is not Eulerian, it has nodes with an odd degree. Since there are only an even number of nodes with odd degrees in every graph, is even. If you connect two nodes of odd node degrees by an additional path, the odd node degrees become even, while the even node degrees remain straight. In order to make the graph Eulerian, additional paths have to be inserted into the graph.
A complete graph is created for the nodes with an odd degree in order to expand the graph at minimal cost . The distance of the shortest path (for example determined with the matrix multiplication or the triple algorithm ) between the two corresponding nodes in the original graph is selected as the edge weight . A cost-minimal perfect pairing with matching edges is then sought in this complete graph . For each matching edge, the edges of the corresponding shortest path between the two nodes are then duplicated in the original graph. The postman has to walk exactly twice along these edges of the original graph. Each Euler tour in the graph expanded in this way is then an optimal solution to the postman problem.
example
Let there be a city with fourteen streets and nine intersections 1, ..., 9. The corresponding graph (see first figure) has four nodes (1, 3, 6 and 9) with an odd node degree and is therefore not Eulerian. We are now looking for a cost-minimal Eulerian extension of the graph in order to be able to specify an Euler tour. For example, if the two edges {1,3} and {6,9} were doubled, the resulting graph would be Eulerian, since then all nodes would have even degrees. The corresponding Euler tour would not necessarily be the shortest tour for the postman. To determine the shortest extension, the complete graph is created from the nodes with an uneven node degree (second figure). The edge weight is the length of the shortest path between two nodes. The minimum matching in this case consists of the edges {1,6} and {3,9} with total length . The corresponding edges of the shortest paths from 1 to 6 and from 3 to 9 are then also entered in the original graph (third figure). An Euler tour and thus a minimal postman tour would be, for example, the node sequence (1, 2, 3, 4, 9, 3, 1, 8, 7, 3, 9, 7, 6, 9, 5, 6, 7, 8, 1). The streets that correspond to the additionally inserted red edges are driven twice by the postman.
