FindHamiltonianCycle

FindHamiltonianCycle[g]
finds a Hamiltonian cycle in the graph g.

FindHamiltonianCycle[g,k]
finds at most k Hamiltonian cycles.

Details and OptionsDetails and Options

Background
Background

  • FindHamiltonianCycle attempts to find one or more distinct Hamiltonian cycles, also called Hamiltonian circuits, Hamilton cycles, or Hamilton circuits. Cycles are returned as a list of edge lists or as if none exist. A Hamiltonian cycle (more properly called a Hamiltonian circuit when the cycle is identified using a explicit path with particular endpoints) is a consecutive sequence of distinct edges such that the first and last edge coincide at their endpoints and in which each vertex appears exactly once. A Hamiltonian cycle is therefore a graph cycle of length n, where n is the number of nodes in the graph. Hamiltonian cycles are used to reconstruct genome sequence, to solve some games (most obviously the Icosian game), to find knight's tour on the chessboard, and to find attractive circular embeddings for regular graphs. A graph possessing a Hamiltonian cycle is known as a Hamiltonian graph.
  • FindHamiltonianCycle[g,k] attempts to find k Hamiltonian cycles, where the count specification k may be omitted (in which case it is taken as 1), may be a positive integer, or may be All.
  • Finding a Hamiltonian cycle is an NP-complete problem. However, various heuristic algorithms exist that sometimes (but not always) can find Hamiltonian cycles very quickly. For this reason, simply permuting the vertices in a graph may give a vastly different run time for FindHamiltonianCycle. A number of Method options may be specified to FindHamiltonianCycle, with the default being Automatic.
  • While Hamiltonian cycles in an n-node graph correspond to cycles of length n, a cycle of arbitrary length may be found using FindCycle. Hamiltonian cycles visit all vertices, but don't necessarily pass through each edge. A cycle that visits each edge exactly once is known as an Eulerian cycles and may be found using FindEulerianCycle. A graph may be tested to see if it is Hamiltonian using HamiltonianGraphQ.
Introduced in 2010
(8.0)
| Updated in 2014
(10.0)