Задача китайского почтальона (Route inspection problem )

В разделе математики теория графов, задачей китайского почтальона (CPP) или задачей маршрута осмотра называется поиск кратчайшего замкнутого пути или контура, который посещает каждое ребро связанного неориентированного графа как минимум один раз. Когда граф имеет эйлеров цикл (замкнутый маршрут, который проходит по каждому ребру единожды) эта схема является оптимальным решением.

Алан Голдман из американского Национального бюро стандартов первый придумал название "задача китайского почтальона" для этой проблемы, так как первоначально ее изучал китайский математик Мэй-Ку Куан в 1962 году [1].

Каковы различия между задачей китайского почтальона и задачей коммивояжера?

Представьте себе остров с дорожной сетью, соединяющей несколько городов. Вы хотите побывать в каждом городе и вернуться в точку старта. Поиск лучшего решения этой задачи и есть задача коммивояжера. (Lmatrix: Точнее сказать поиск кратчайшего пути с возвратом в точку старта из всех возможных путей.)

Теперь представьте, что вы хотите проехать по каждой дороге этой сети самым оптимальным образом. Это и есть задача китайского почтальона. По существу для задачи коммивояжера вы должны посетить все вершины. Для задачи почтальона -  каждое ребро.

Эйлеровы пути и циклы

Для того, чтобы граф имел эйлеров цикл, он, безусловно, должны быть связным.

Пусть мы имеем связный граф G = (V, E), следующие утверждения эквивалентны:
1. Все вершины G должны быть четной степени.
2. G состоит из ребер из непересекающихся объединения некоторых циклов, а вершины из этих циклов 

T-соединения

Решение

Если граф имеет эйлерову-цепь (или эйлеров-путь), то в этом случае, эйлерова-цепь (или путь) проходит по каждому ребру, и таким образом, решением будет являться выбор любой эйлеровой-цепи (или пути).

Варианты

Несколько вариантов Задачи китайского почтальона было изучено и показано, что они являются NP-полными.
 

Min-задача китайского почтальона для смешанных графов: для решения этой задачи, некоторые из ребер могут быть направленными и поэтому, могут быть пройдены только в одном направлении. Когда задачей является минимизация обхода орграфа она известна как "New York Street Sweeper problem". (Задача нью-йоркского подметальщика)
 

Min k-Задача китайского почтальона: найти k-циклы, при условии, что все они начинаются в указанном месте, и таким образом, чтобы каждое ребро было пройдено по крайней мере в одном цикле. Цель состоит в том, чтобы минимизировать стоимость самого дорогого цикла.
 

Задача сельского почтальона: Дано подмножество ребер. Нужно найти самый дешевый гамильтонов-цикл, содержащий каждый из этих ребер (и, возможно, другие). Это частный случай задачи нахождения минимального общего пути, который указывает, какие именно вершины должны содержаться в цикле.  

// English

In graph theory, a branch of mathematics, the Chinese postman problem (CPP), postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution.

Alan Goldman of the U.S. National Bureau of Standards first coined the name 'Chinese Postman Problem' for this problem, as it was originally studied by the Chinese mathematician Mei-Ku Kuan in 1962.[1]

Eulerian paths and circuits

In order for a graph to have an Eulerian circuit, it will certainly have to be connected.

Suppose we have a connected graph G = (V, E), The following statements are equivalent:
All vertices in G have even degree.
G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
G has an Eulerian circuit.
1 → 2 can be shown by induction on the number of cycles.
2 → 3 can also be shown by induction on the number of cycles, and
3 → 1 should be immediate.

An Eulerian path (a walk which is not closed but uses all edges of G just once) exists if and only if G is connected and exactly two vertices have odd valence.

T-joins

Let T be a subset of the vertex set of a graph. An edge set whose odd-degree vertices are the vertices in T is called a T-join. (In a connected graph, a T-join exists if and only if |T| is even.) The T-join problem is to find a smallest T-join. A smallest T-join leads to a solution of the postman problem. A smallest T-join necessarily consists of |T| paths, no two having an edge in common, that join the vertices of T in pairs. The paths will be such that the total length of all of them is as small as possible. A minimum T-join can be obtained by a weighted matching algorithm that uses O(n3) computational steps.[2]
 

Solution

If a graph has an Eulerian circuit (or an Eulerian path), then an Eulerian circuit (or path) visits every edge, and so the solution is to choose any Eulerian circuit (or path).

If the graph is not Eulerian, it must contain vertices of odd degree. By the handshaking lemma, there must be an even number of these vertices. To solve the postman problem we first find a smallest T-join. We make the graph Eulerian by doubling of the T-join. The solution to the postman problem in the original graph is obtained by finding an Eulerian circuit for the new graph.

Variants

A few variants of the Chinese Postman Problem have been studied and shown to be NP-complete.[3]
Min Chinese postman problem for mixed graphs: for this problem, some of the edges may be directed and can therefore only be visited from one direction. When the problem is minimal traversal of a digraph it is known as the "New York Street Sweeper problem."
Min 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.
Rural postman problem: Given is also a subset of the edges. Find the cheapest Hamiltonian cycle containing each of these edges (and possibly others). This is a special case of the minimum general routing problem which specifies precisely which vertices the cycle must contain.

References

^ ""Chinese Postman Problem"".
^ J. Edmonds and E.L. Johnson, Matching Euler tours and the Chinese postman problem, Math. Program. (1973).
^ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. Retrieved 2008-10-22.