 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.
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 NPcomplete.
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 Hamiltonianconnected 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 "tailtohead").
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
 a complete graph with more than two vertices is Hamiltonian
 every cycle graph is Hamiltonian
 every tournament has an odd number of Hamiltonian paths^{[citation needed]}
 every platonic solid, considered as a graph, is Hamiltonian^{[citation needed]}
 every prism is Hamiltonian^{[citation needed]}
 The Deltoidal hexecontahedron is the only nonhamiltonian Archimedean dual^{[citation needed]}
 Every antiprism is Hamiltonian^{[citation needed]}
 A maximal planar graph with no separating triangles is Hamiltonian.^{[citation needed]}
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 zeroknowledge proof.
Number of different Hamiltonian cycles for a complete graph = (n1)! / 2.
Number of different Hamiltonian cycles for a complete directed graph = (n1)!.
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 nonadjacent vertices, the sum of their degrees is n or greater (see Ore's theorem).
The following theorems can be regarded as directed versions:
GhouilaHouiri (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 nonadjacent 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
 Barnette's conjecture, an open problem on Hamiltonicity of cubic bipartite polyhedral graphs
 Eulerian path, a path through all edges in a graph
 Grinberg's theorem giving a necessary condition for planar graphs to have a Hamiltonian cycle
 Knight's tour, a Hamiltonian cycle in the knight's graph
 Hamiltonian path problem, the computational problem of finding Hamiltonian paths
 Hypohamiltonian graph, a nonHamiltonian graph in which every vertexdeleted subgraph is Hamiltonian
 LCF notation for Hamiltonian cubic graphs.
 Lovász conjecture that vertextransitive graphs are Hamiltonian
 Pancyclic graph, graphs with cycles of all lengths including a Hamiltonian cycle
 Snakeinthebox, the longest induced path in a hypercube
 Steinhaus–Johnson–Trotter algorithm for finding a Hamiltonian path in a permutohedron
 Tait's conjecture (now known false) that 3regular polyhedral graphs are Hamiltonian
 Travelling salesman problem
Notes
References
 Berge, Claude; GhouilaHouiri, A. (1962), Programming, games and transportation networks, New York: John Wiley & Sons, Inc.
 DeLeon, Melissa, "A Study of Sufficient Conditions for Hamiltonian Cycles". Department of Mathematics and Computer Science, Seton Hall University
 Dirac, G. A. (1952), "Some theorems on abstract graphs", Proceedings of the London Mathematical Society, 3rd Ser. 2: 69–81, doi:10.1112/plms/s32.1.69, MR0047308
 Graham, Ronald L., Handbook of Combinatorics, MIT Press, 1995. ISBN 9780262571708.
 Hamilton, William Rowan, "Memorandum respecting a new system of roots of unity". Philosophical Magazine, 12 1856
 Hamilton, William Rowan, "Account of the Icosian Calculus". Proceedings of the Royal Irish Academy, 6 1858
 Meyniel, M. (1973), "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté", Journal of Combinatorial Theory, Ser. B 14 (2): 137–147, doi:10.1016/00958956(73)900579
 Ore, O "A Note on Hamiltonian Circuits." American Mathematical Monthly 67, 55, 1960.
 Peterson, Ivars, "The Mathematical Tourist". 1988. W. H. Freeman and Company, NY
 Pósa, L. A theorem concerning hamilton lines. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 7(1962), 225–226.
 Chuzo Iwamoto and Godfried Toussaint, "Finding Hamiltonian circuits in arrangements of Jordan curves is NPcomplete," Information Processing Letters, Vol. 52, 1994, pp. 183–189.
External links
Categories: Computational problems in graph theory
 NPcomplete problems
 Graph theory objects
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