Hamiltonian path problem

Hamiltonian path problem

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. The problem of finding a Hamiltonian cycle or path is in FNP.

There is a simple relation between the two problems. The Hamiltonian path problem for graph G is equivalent to the Hamiltonian cycle problem in a graph H obtained from G by adding a new vertex and connecting it to all vertices of G.

The Hamiltonian cycle problem is a special case of the travelling salesman problem, obtained by setting the distance between two cities to a finite constant if they are adjacent and infinity otherwise.

The directed and undirected Hamiltonian cycle problems were two of Karp's 21 NP-complete problems. Garey and Johnson showed shortly afterwards in 1974 that the directed Hamiltonian cycle problem remains NP-complete for planar graphs and the undirected Hamiltonian cycle problem remains NP-complete for cubic planar graphs.

Contents

Algorithms

A trivial heuristic algorithm for locating Hamiltonian paths is to construct a path abc... and extend it until no longer possible; when the path abc...xyz cannot be extended any longer because all neighbours of z already lie in the path, one goes back one step, removing the edge yz and extending the path with a different neighbour of y; if no choice produces a Hamiltonian path, then one takes a further step back, removing the edge xy and extending the path with a different neighbour of x, and so on. This algorithm will certainly find an Hamiltonian path (if any) but it runs in exponential time.

Some algorithms use a rotation argument as a fast way to get unstuck when a path that cannot be extended, transforming the path in a different path of the same length: given a path "abc...xyz" that cannot be extended because all neighbours of z lie on the path, one chooses some neighbour n of z and transforms the path "abc...n-op...xyz" into the path "abc...n-zyx...po"; the edge no is removed and replaced by the edge nz, while the subpath op...xyz is rotated.
This argument alone does not guarantee that a Hamiltonian path will eventually be found.

Solving the problem

Due to the complexity of the problem computers have to be used to solve what may seem to be minor tasks.

In November 1994, Leonard Adleman published his work on solving a 7-vertex instance of the Hamiltonian Path Problem using a DNA computer. Exploiting the parallelism inherent in chemical reactions, the problem is solvable with the number of required procedures growing linear in proportion to the number of vertices in the graph.[1]

In July 2009, research published in the Journal of Biological Engineering showed that a bacterial computer can be used to solve a simple Hamiltonian path problem (using three locations).[2]

Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the Icosian game, now also known as Hamilton's puzzle, to find a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the Icosian Calculus, an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hamilton). This the Icosian Calculus solution is absent generalization to arbitrary graphs.

See also

External links

References

  1. ^ Adleman, Leonard (November). Science (American Association for the Advancement of Science) 266 (5187): 1021–1024. doi:10.1126/science.7973651. JSTOR 2885489. PMID 7973651. 
  2. ^ [1]

Wikimedia Foundation. 2010.

См. также в других словарях:

  • Hamiltonian path — This article is about the overall graph theory concept of a Hamiltonian path. For the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph, see Hamiltonian path problem. A Hamiltonian cycle in a dodecahedron …   Wikipedia

  • Path cover — Given a directed graph G = (V, E), a path cover is a set of directed paths such that every vertex v ∈ V belongs to at least one path. Note that a path cover may include paths of length 0 (a single vertex).[1] A path cover …   Wikipedia

  • Hamiltonian completion — The Hamiltonian completion problem is to find the minimal number of edges to add to a graph to make it Hamiltonian.The problem is clearly NP hard in general case (since its solution gives an answer to the NP complete problem of determining… …   Wikipedia

  • Path (graph theory) — In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. The first vertex is called the start vertex and the last vertex is called the end vertex . Both… …   Wikipedia

  • Path integral formulation — This article is about a formulation of quantum mechanics. For integrals along a path, also known as line or contour integrals, see line integral. The path integral formulation of quantum mechanics is a description of quantum theory which… …   Wikipedia

  • 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

  • Eulerian path — In graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the …   Wikipedia

  • Function problem — In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO.Notable examples include the travelling salesman problem, which asks for the …   Wikipedia

  • Classical central-force problem — In classical mechanics, the central force problem is to determine the motion of a particle under the influence of a single central force. A central force is a force that points from the particle directly towards (or directly away from) a fixed… …   Wikipedia

  • 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… …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»