In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a branch of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
. When the graph has an
Eulerian circuit
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...
(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
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...
does have an Eulerian circuit. It can be solved in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
The problem was originally studied by the Chinese mathematician
Kwan Mei-Ko in 1960, whose Chinese paper was translated into English in 1962. The original name "Chinese postman problem" was coined in his honor; different sources credit the coinage either to
Alan J. Goldman
Alan J. Goldman (1932–2010) was an American expert in operations research...
Career
Goldman was born in 1932 and grew up in Brooklyn, where his parents both worked for the public school system. In 1949, he was a winner of the Westinghouse Scienc ...
or
Jack Edmonds, both of whom were at the
U.S. National Bureau of Standards at the time.
A generalization is to choose any set ''T'' of evenly many vertices that are to be joined by an edge set in the graph whose odd-degree vertices are precisely those of ''T''. Such a set 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.
Undirected solution and ''T''-joins
The undirected route inspection problem can be solved in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
based on the concept of a ''T''-join.
Let ''T'' be a set of vertices in a graph. An edge set ''J'' is called a ''T''-join if the collection of vertices that have an odd number of incident edges in ''J'' is exactly the set ''T''. A ''T''-join exists whenever every connected component of the graph contains an even number of vertices in ''T''. The ''T''-join problem is to find a ''T''-join with the minimum possible number of edges or the minimum possible total weight.
For any ''T'', a smallest ''T''-join (when it exists) necessarily consists of
paths that join the vertices of ''T'' in pairs. The paths will be such that the total length or total weight of all of them is as small as possible. In an optimal solution, no two of these paths will share any edge, but they may have shared vertices. A minimum ''T''-join can be obtained by constructing a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
on the vertices of ''T'', with edges that represent shortest paths in the given input graph, and then finding a
minimum weight perfect matching in this complete graph. The edges of this matching represent paths in the original graph, whose union forms the desired ''T''-join.
Both constructing the complete graph, and then finding a matching in it, can be done in O(''n''
3) computational steps.
For the route inspection problem, ''T'' should be chosen as the set of all odd-degree vertices. By the assumptions of the problem, the whole graph is connected (otherwise no tour exists), and by the
handshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. In more colloquial terms, in a party of people some of whom ...
it has an even number of odd vertices, so a ''T''-join always exists. Doubling the edges of a ''T''-join causes the given graph to become an Eulerian multigraph (a connected graph in which every vertex has even degree), from which it follows that it has an
Euler tour
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...
, a tour that visits each edge of the multigraph exactly once. This tour will be an optimal solution to the route inspection problem.
Directed solution
On a directed graph, the same general ideas apply, but different techniques must be used. If the directed graph is Eulerian, one need only find an Euler cycle. If it is not, one must find ''T''-joins, which in this case entails finding paths from vertices with an in-
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
greater than their out-
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
to those with an out-
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
greater than their in-
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
such that they would make in-degree of every vertex equal to its out-degree. This can be solved as an instance of the
minimum-cost flow problem
The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery rou ...
in which there is one unit of supply for every unit of excess in-degree, and one unit of demand for every unit of excess out-degree. As such it is solvable in O(, ''V'',
2, ''E'', ) time. A solution exists if and only if the given graph is
strongly connected
In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that ...
.
Applications
Various combinatorial problems have been reduced to the Chinese Postman Problem, including finding a maximum cut in a planar graph
and a minimum-mean length circuit in an undirected graph.
Variants
A few variants of the Chinese Postman Problem have been studied and shown to be
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
.
*The windy postman problem is a variant of the route inspection problem in which the input is an undirected graph, but where each edge may have a different cost for traversing it in one direction than for traversing it in the other direction. In contrast to the solutions for directed and undirected graphs, it is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
.
* The
Mixed Chinese postman problem
The mixed Chinese postman problem (MCPP or MCP) is the search for the shortest traversal of a graph with a set of vertices V, a set of undirected edges E with positive rational weights, and a set of directed arcs A with positive rational weights t ...
: for this problem, some of the edges may be directed and can therefore only be visited from one direction. When the problem calls for a minimal traversal of a digraph (or multidigraph) it is known as the "New York Street Sweeper problem."
* The ''k''-Chinese postman problem: find ''k'' cycles all starting at a designated location such that each edge is traversed by at least one cycle. The goal is to minimize the cost of the most expensive cycle.
* The "Rural Postman Problem": solve the problem with some edges not required.
See also
*
Travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
*
Arc routing
Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing p ...
*
Mixed Chinese postman problem
The mixed Chinese postman problem (MCPP or MCP) is the search for the shortest traversal of a graph with a set of vertices V, a set of undirected edges E with positive rational weights, and a set of directed arcs A with positive rational weights t ...
References
External links
*
*{{commons category-inline
NP-complete problems
Computational problems in graph theory