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.
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]
- a complete graph with more than two vertices is Hamiltonian
- every cycle graph is Hamiltonian
- every tournament has an odd number of Hamiltonian paths
- every platonic solid, considered as a graph, is Hamiltonian
- every prism is Hamiltonian
- The Deltoidal hexecontahedron is the only non-hamiltonian Archimedean dual
- Every antiprism is Hamiltonian
- A maximal planar graph with no separating triangles is Hamiltonian.
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.
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)!.
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.
- 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.
- A simple graph with n vertices (n ≥ 3) is Hamiltonian if each vertex has degree n/2 or greater.
- 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:
- A strongly connected simple directed graph with n vertices is Hamiltonian if some vertex has a full degree smaller than n.
- 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.
- 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 non-Hamiltonian graph in which every vertex-deleted subgraph is Hamiltonian
- LCF notation for Hamiltonian cubic graphs.
- Lovász conjecture that vertex-transitive graphs are Hamiltonian
- Pancyclic graph, graphs with cycles of all lengths including a Hamiltonian cycle
- Snake-in-the-box, 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 3-regular polyhedral graphs are Hamiltonian
- Travelling salesman problem
- Berge, Claude; Ghouila-Houiri, 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/s3-2.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/0095-8956(73)90057-9
- 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 NP-complete," Information Processing Letters, Vol. 52, 1994, pp. 183–189.
Wikimedia Foundation. 2010.
Look at other dictionaries:
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). 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