Route inspection problem

Route inspection problem

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]

Contents

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 = (VE), The following statements are equivalent:

  1. All vertices in G have even degree.
  2. G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
  3. 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 \tfrac{1}{2}|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.

See also

References

  1. ^ ""Chinese Postman Problem"". http://www.nist.gov/dads/HTML/chinesePostman.html. 
  2. ^ J. Edmonds and E.L. Johnson, Matching Euler tours and the Chinese postman problem, Math. Program. (1973).
  3. ^ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm. http://www.nada.kth.se/~viggo/problemlist/compendium.html. Retrieved 2008-10-22. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… …   Wikipedia

  • U.S. Route 491 — Devil s Highway Map of the Four Corners with US 491 highlighted in …   Wikipedia

  • Deep packet inspection — (DPI) (also called complete packet inspection and Information eXtraction IX ) is a form of computer network packet filtering that examines the data part (and possibly also the header) of a packet as it passes an inspection point, searching for… …   Wikipedia

  • Lethal Inspection — Эпизод «Футурамы» «Смертельный осмотр» «Lethal Inspection» …   Википедия

  • Northwest Staging Route — The Lend Lease Memorial in Fairbanks, Alaska commemorates the shipment of U.S. aircraft to the Soviet Union along the Northwest Staging Route …   Wikipedia

  • The Problem with Popplers — Futurama episode Fry, Bender, and Leela discover the Popplers …   Wikipedia

  • The Problem with Popplers — Эпизод «Футурамы» «Проблема с попплерами» «The Problem with Popplers» Порядковый номер 28 Сезон 2 Код эпизо …   Википедия

  • The Route of All Evil — Эпизод «Футурамы» «Путь Всех Зол» «The Route of All Evil» Порядковый номер 44 Сезон 5 Код эпизода …   Википедия

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”