Hamiltonian CycleEdit
In mathematics and computer science, a Hamiltonian cycle is a closed loop that visits every vertex of a graph exactly once and then returns to the starting point. The concept is named after Sir William Rowan Hamilton, who explored ideas about traversing a network of points in a way that would visit each point once before completing the circuit. In the language of graph theory, which is part of the broader study of discrete structures, such a cycle is the quintessential example of a traversal that covers all nodes without repetition. For a broader sense of the objects involved, see Graph theory and Cycle (graph theory).
A related notion is the Hamiltonian path, which visits every vertex exactly once but does not necessarily form a cycle. The Hamiltonian cycle problem asks whether a given graph contains such a cycle. This problem sits at a central place in the theory of computational complexity, illustrating how some natural questions can be easy to state but hard to solve in general. See Hamiltonian cycle problem for a focused treatment of the decision version, and note that the weighted version is closely connected to the Travelling salesman problem in optimization.
Because Hamiltonian cycles touch on fundamental questions about coverage and routing, they have long attracted both theoretical interest and practical application. Although not every graph admits a Hamiltonian cycle, many important graph classes do, and a number of classical results give sufficient conditions for existence. See Dirac's theorem and Ore's theorem for well-known criteria, and explore the boundary between graphs that always carry a Hamiltonian cycle and those that do not.
Definition and basic concepts
A graph G = (V, E) has a Hamiltonian cycle if there exists a sequence of vertices v1, v2, ..., vn with n = |V| such that: - each consecutive pair (vi, vi+1) is an edge in E (for i = 1, ..., n−1), - (vn, v1) is also an edge, and - all vertices in V appear exactly once in the sequence.
In a simple graph, no vertex is repeated along the cycle except for the return to the starting point. The cycle that results is sometimes denoted as a Hamiltonian cycle of G. The term is distinct from a cycle that visits only a subset of vertices, which would not be Hamiltonian unless that subset happens to be all of V.
A number of standard results help classify when Hamiltonian cycles exist: - In a complete graph K_n with n ≥ 3, a Hamiltonian cycle exists for every such n, because every pair of distinct vertices is adjacent. - The concept interacts with other graph properties, such as planarity and degree constraints, which can influence whether a Hamiltonian cycle is guaranteed or obstructed.
Graph theory provides a broad framework for understanding these cycles, while cycle terminology helps connect them to more general cycle structures in graphs.
Key results and theory
Several classical theorems give sufficient (but not necessary) conditions for the existence of a Hamiltonian cycle: - Dirac's theorem: If G has n ≥ 3 vertices and every vertex has degree at least n/2, then G contains a Hamiltonian cycle. See Dirac's theorem for precise statements and proofs. - Ore's theorem: If G has n ≥ 3 vertices and for every pair of non-adjacent vertices u and v we have deg(u) + deg(v) ≥ n, then G is Hamiltonian. See Ore's theorem for details.
Beyond these, a rich line of inquiry investigates necessary and sufficient conditions, extremal properties, and the structure of Hamiltonian cycles in special graph families. The study of Hamiltonian cycles is also connected to broader topics in combinatorics and graph algorithms.
In the realm of computational complexity, the decision problem “does G contain a Hamiltonian cycle?” is a classic example of an NP-complete problem in general graphs. This places it among problems for which no known polynomial-time algorithms exist (assuming P ≠ NP). See NP-completeness and the historical landmark that identified the problem among Karp’s 21 NP-complete problems, Karp's 21 NP-complete problems.
Computational aspects and algorithms
Because the general Hamiltonian cycle problem is NP-complete, most exact algorithms require time that grows exponentially with the number of vertices. In practice, researchers use a mix of strategies: - Backtracking and branch-and-bound methods search through possible cycles while pruning infeasible partial solutions. See Backtracking for a general discussion of this paradigm. - Dynamic programming approaches, such as the Held–Karp algorithm, solve the weighted analogue (the traveling salesman problem) in time roughly O(n^2 2^n). This framework can be adapted to unweighted Hamiltonian cycles as a theoretical tool; see Held-Karp algorithm for the classical formulation. - Heuristic and exact optimization techniques, including SAT-based methods and modern metaheuristics, are widely used for large instances in practice, especially when exact guarantees are not required. - For special graph classes, there are polynomial-time algorithms in some restricted settings, though many natural graph families remain hard cases. The boundary between tractable and intractable instances is an active area of study in Algorithm design and Computational complexity.
In applied settings, the Hamiltonian cycle concept underpins approaches to routing, network design, and circuit layout. Its connection to the traveling salesman problem makes it a central object of study in optimization, with many practical heuristics and exact methods developed to address real-world instances. See Travelling salesman problem for the broader optimization problem and its relationship to Hamiltonian cycles.
Applications and related problems
Beyond pure theory, Hamiltonian cycles inform algorithms for route planning, logistics, and the design of efficient circuits. In some models of network design and genome assembly, the idea of visiting a set of nodes or features exactly once before returning to the start has practical interpretive value, and researchers draw on the same foundational results in graph theory to develop robust methods. Related notions include: - Hamiltonian path: a visit to every vertex exactly once without the requirement to form a cycle. See Hamiltonian path for comparison. - Cycle and cycle detection in graphs: the broader study of closed traversals and their properties. See Cycle (graph theory). - Variants such as directed graphs, weighted graphs, and various restricted graph families, each with its own algorithmic and structural nuances. See Directed graph and Travelling salesman problem for context.