FindHamiltonianCycle
finds a Hamiltonian cycle in the graph g.
FindHamiltonianCycle[g,k]
finds at most k Hamiltonian cycles.
FindHamiltonianCycle[{vw,…},…]
uses rules vw to specify the graph g.
Details and Options
- A Hamiltonian cycle visits each vertex exactly once.
- FindHamiltonianCycle returns a list of paths consisting of Hamiltonian cycles.
- FindHamiltonianCycle returns the list {} if no Hamiltonian cycles exist.
- FindHamiltonianCycle[g] is equivalent to FindHamiltonianCycle[g,1].
- FindHamiltonianCycle[g,All] finds all Hamiltonian cycles in the graph g.
- FindHamiltonianCycle works with undirected graphs, directed graphs, multigraphs, and mixed graphs.
Background & Context
- 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 an explicit path with particular endpoints) is a consecutive sequence of distinct edges such that the first and last edges coincide at their endpoints and in which each vertex appears exactly once. A Hamiltonian cycle is therefore a graph cycle of length
, where 
is the number of nodes in the graph. Hamiltonian cycles are used to reconstruct genome sequences, to solve some games (most obviously the Icosian game), to find a knight's tour on a 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 different runtime for FindHamiltonianCycle.
- A graph may be tested to see if it is Hamiltonian using HamiltonianGraphQ. FindShortestTour is another function that attempts to find a single Hamiltonian cycle on a graph (or a more generally specified set of vertices), with the advantage that it sometimes succeeds more quickly than FindHamiltonianCycle.
- While Hamiltonian cycles in an
-node graph correspond to cycles of length 
, a cycle of arbitrary length may be found using FindCycle. Hamiltonian cycles visit all vertices, but do not necessarily pass through each edge. A cycle that visits each edge exactly once is known as an Eulerian cycle and may be found using FindEulerianCycle.
Examples
open all close allBasic Examples (2)
Scope (8)
FindHamiltonianCycle works with undirected graphs:
FindHamiltonianCycle[[image]]FindHamiltonianCycle[[image]]FindHamiltonianCycle[[image]]FindHamiltonianCycle[[image]]Find several Hamiltonian cycles:
FindHamiltonianCycle[[image], 2]Use rules to specify the graph:
FindHamiltonianCycle[{1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3, 3 -> 4, 4 -> 1}]FindHamiltonianCycle returns an empty result for non-Hamiltonian graphs:
FindHamiltonianCycle[[image]]FindHamiltonianCycle works with large graphs:
g = CompleteGraph[10000];FindHamiltonianCycle[g] //Length// TimingApplications (5)
Solve the Icosian game [MathWorld] by finding a Hamiltonian cycle along the edges of the dodecahedron:
{g = PolyhedronData["Dodecahedron", "Skeleton"], Graphics3D[{Opacity[.8], PolyhedronData["Dodecahedron", "GraphicsComplex"]}]}h = PathGraph@First[FindHamiltonianCycle[g]];{HighlightGraph[g, h, GraphHighlightStyle -> "Thick"], Graphics3D[{Opacity[.8], PolyhedronData["Dodecahedron", "GraphicsComplex"], Red, Tube[PolyhedronData["Dodecahedron", "Vertices"][[Append[VertexList[h], VertexList[h][[1]]]]], 0.1]}]}On a labeled dodecahedron, find Hamiltonian cycles that contain a given sequence of labels:
g = [image];Obtain cycles containing the sequence B, C, P, N, M:
StringJoin /@ Map[First, FindHamiltonianCycle[g, All], {2}]Flatten[StringCases[%, __ ~~ ("BCPNM" | "MNPCB" ) ~~ __ ]]Map[HighlightGraph[g, PathGraph[Characters[#]], GraphHighlightStyle -> "Thick"]&, %]Find a sequence of moves by a knight chess piece that visits each square of an 8×8 chessboard exactly once:
g = KnightTourGraph[8, 8];cycle = First[FindHamiltonianCycle[g]]checkerboard = ArrayPlot[Table[Mod[j + i, 2], {i, 8}, {j, 8}], ColorRules -> {1 -> RGBColor[0, .55, .77], 0 -> RGBColor[.67, .9, .99]}, Frame -> False, DataRange -> {{1, 8}, {1, 8}}];Show[{checkerboard, HighlightGraph[g, PathGraph[cycle], GraphHighlightStyle -> "DehighlightHide", EdgeStyle -> Directive[Thick, Red]]}]Graph-based assembly of a circular genome "ATGGCGTGCA" with vertices as k-mers and edges as pairwise alignments:
threeMers = StringJoin /@ Partition[Characters["ATGGCGTGCA"], 3, 1, 1]edges = Flatten[Table[StringCases[threeMers, x : (StringDrop[e, 1] ~~ _) :> ex], {e, threeMers}]]Graph[threeMers, edges, GraphLayout -> "CircularEmbedding", PlotTheme -> "DiagramGold"]FindHamiltonianCycle [%]//FirstStringJoin[StringTake[First /@ %, 1]]The Gray code of order 
is a Hamiltonian cycle of the hypercube graph 
:
graycode3 = With[{n = 3}, Table[IntegerString[BitXor[BitShiftRight[i], i], 2, n]
, {i, 0, 2 ^ n - 1}]]Subscript[𝒬, 3] = VertexReplace[HypercubeGraph[3, VertexShapeFunction -> "Name"], Table[i + 1 -> IntegerString[i, 2, 3], {i, 0, 7}]]Find all Hamiltonian cycles of 
:
Map[First, FindHamiltonianCycle[Subscript[𝒬, 3], All], {2}]MemberQ[%, graycode3]HighlightGraph[Subscript[𝒬, 3], PathGraph[graycode3]]Properties & Relations (5)
Use GraphData for an extensive collection of Hamiltonian graphs:
Short[GraphData["Hamiltonian"]]Short[GraphData["Nonhamiltonian"]]Test whether a graph has a Hamiltonian cycle by using HamiltonianGraphQ:
GraphData[{"DutchWindmill", {4, 4}}]HamiltonianGraphQ[%]Hamiltonian graphs are biconnected:
g = GraphData["Foster038A"]FindHamiltonianCycle[g]The line graph of a Hamiltonian graph has a Hamiltonian cycle:
CompleteGraph[4]{HamiltonianGraphQ[%], FindHamiltonianCycle[LineGraph[%]]}The line graph of an Eulerian graph has a Hamiltonian cycle:
g = Graph[{12, 23, 31, 34, 45, 53}]{EulerianGraphQ[%], FindHamiltonianCycle[LineGraph[g]]}An undirected graph with 
vertices and minimal degree greater than 
has a Hamiltonian cycle:
g = [image];{Min[VertexDegree[g]] > VertexCount[g] / 2, FindHamiltonianCycle[g]}A directed graph with 
vertices and minimum degree greater than 
has a Hamiltonian cycle:
g = [image];{Min[VertexDegree[g]] > VertexCount[g], FindHamiltonianCycle[g]}Neat Examples (1)
g = PolyhedronData["Dodecahedron", "Skeleton"];Shallow[cycle = First[FindHamiltonianCycle[g]]]Dynamically highlight a cycle:
color[cycles_] := {cycles, cycles[[All, 1]], Style[cycles[[-1, 2]], Yellow]}Dynamic[HighlightGraph[g, color[cycle[[1 ;; Clock[{1, Length[cycle], 1}, 40]]]]]]Text
Wolfram Research (2010), FindHamiltonianCycle, Wolfram Language function, https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html (updated 2015).
CMS
Wolfram Language. 2010. "FindHamiltonianCycle." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html.
APA
Wolfram Language. (2010). FindHamiltonianCycle. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindHamiltonianCycle.html