Hamiltonian path

Hamiltonian path
A Hamiltonian cycle in a dodecahedron. Like all platonic solids, the dodecahedron is Hamiltonian.
The Herschel graph is the smallest possible polyhedral graph that does not have a Hamiltonian cycle.

In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the Icosian game, now also known as Hamilton's puzzle, which involves finding 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 solution does not generalize to arbitrary graphs. However, despite being named after Hamilton, Hamiltonian cycles in polyhedra had also been studied a year earlier by Thomas Kirkman.[1]

Contents

Definitions

A Hamiltonian path or traceable path is a path that visits each vertex exactly once. A graph that contains a Hamiltonian path is called a traceable graph. A graph is Hamiltonian-connected if for every pair of vertices there is a Hamiltonian path between the two vertices.

A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once (except the vertex that is both the start and end, and so is visited twice). A graph that contains a Hamiltonian cycle is called a Hamiltonian graph.

Similar notions may be defined for directed graphs, where each edge (arc) of a path or cycle can only be traced in a single direction (i.e., the vertices are connected with arrows and the edges traced "tail-to-head").

A Hamiltonian decomposition is an edge decomposition of a graph into Hamiltonian circuits. This is one of the known but unsolved problems.[clarification needed]

Examples

Properties

Any Hamiltonian cycle can be converted to a Hamiltonian path by removing one of its edges, but a Hamiltonian path can be extended to Hamiltonian cycle only if its endpoints are adjacent.

The line graph of a Hamiltonian graph is Hamiltonian. The line graph of an Eulerian graph is Hamiltonian[clarification needed].

A tournament (with more than 2 vertices) is Hamiltonian if and only if it is strongly connected.

A Hamiltonian cycle may be used as the basis of a zero-knowledge proof.

Number of different Hamiltonian cycles for a complete graph = (n-1)! / 2.

Number of different Hamiltonian cycles for a complete directed graph = (n-1)!.

Bondy–Chvátal theorem

The best vertex degree characterization of Hamiltonian graphs was provided in 1972 by the Bondy–Chvátal theorem, which generalizes earlier results by G. A. Dirac (1952) and Øystein Ore. In fact, both Dirac's and Ore's theorems are less powerful than what can be derived from Pósa's theorem (1962). Dirac and Ore's theorems basically state that a graph is Hamiltonian if it has enough edges. First we have to define the closure of a graph.

Given a graph G with n vertices, the closure cl(G) is uniquely constructed from G by successively adding for all nonadjacent pairs of vertices u and v with degree(v) + degree(u) ≥ n[clarification needed] the new edge uv.

Bondy–Chvátal theorem

A graph is Hamiltonian if and only if its closure is Hamiltonian.

As complete graphs are Hamiltonian, all graphs whose closure is complete are Hamiltonian, which is the content of the following earlier theorems by Dirac and Ore.

Dirac (1952)

A simple graph with n vertices (n ≥ 3) is Hamiltonian if each vertex has degree n/2 or greater.[2]

Ore (1960)

A graph with n vertices (n ≥ 3) is Hamiltonian if, for each pair of non-adjacent vertices, the sum of their degrees is n or greater (see Ore's theorem).

The following theorems can be regarded as directed versions:

Ghouila-Houiri (1960)

A strongly connected simple directed graph with n vertices is Hamiltonian if some vertex has a full degree smaller than n.

Meyniel (1973)

A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of some two distinct non-adjacent vertices is smaller than 2n − 1.

The number of vertices must be doubled because each undirected edge corresponds to two directed arcs and thus the degree of a vertex in the directed graph is twice the degree in the undirected graph.

See also

Notes

  1. ^ Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR608093 .
  2. ^ Graham, p. 20.

References

External links


Wikimedia Foundation. 2010.

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

  • Hamiltonian path — noun A path through an undirected graph which visits each vertex exactly once …   Wiktionary

  • Hamiltonian path problem — This article is about the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph. For the general graph theory concepts, see Hamiltonian path. In the mathematical field of graph theory the Hamiltonian path… …   Wikipedia

  • Hamiltonian — may refer toIn mathematics : * Hamiltonian system * Hamiltonian path, in graph theory * Hamiltonian group, in group theory * Hamiltonian (control theory) * Hamiltonian matrix * Hamiltonian flow * Hamiltonian vector field * Hamiltonian numbers (or …   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

  • Hamiltonian — 1. adjective Applied to various mathematical constructs developed or inspired by Hamilton, as in Hamiltonian path, Hamiltonian cycle. 2. noun a) In quantum mechanics, the observable, denoted by H, that corresponds to the total energy of the… …   Wiktionary

  • Hamiltonian cycle — noun A Hamiltonian path with an additional connection between the first and last vertices visited, forming a cycle …   Wiktionary

  • 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

  • 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

  • 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


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

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