find Hamiltonian cycle
find Hamiltonian path
(optional) one or more options as specified below
startvertex=a valid vertex in G
Specifies the starting vertex for a Hamiltonian cycle or path. If provided, the algorithm will only consider cycles or paths beginning at startvertex.
endvertex=a valid vertex in G
Specifies the ending vertex for a Hamiltonian path. If provided, the algorithm will only consider paths terminating at endvertex.
The FindHamiltonianCycle(G) function returns a Hamiltonian cycle as a list of vertices of G if such a path exists in G, and NULL otherwise.
The FindHamiltonianPath(G) function returns a Hamiltonian path as a list of vertices of G if such a path exists in G, and NULL otherwise.
Optional starting and ending vertices may be specified with the startvertex and endvertex options, respectively. Note that endvertex is valid only for FindHamiltonianPath.
The algorithm works for both undirected and directed graphs and ignores edge weights for weighted graphs.
Note that the TravelingSalesman command also returns a Hamiltonian cycle, specifically the least-weight Hamiltonian cycle. By contrast FindHamiltonianCycle returns the first Hamiltonian cycle it can find, if one exists, and does not attempt to find a cycle of least weight.
A Hamiltonian cycle (also called Hamiltonian circuit) for a graph G on n vertices is a cycle in G containing each of the n vertices exactly once.
A Hamiltonian path for a graph G on n vertices is a path of length n which visits each vertex of G exactly once. Note that every Hamiltonian cycle contains a Hamiltonian path, but the reverse is not true.
C ≔ CycleGraph⁡5
C≔Graph 1: an undirected graph with 5 vertices and 5 edge(s)
The Petersen graph is not Hamiltonian (that is, it does not contain a Hamiltonian cycle), but it does contain a Hamiltonian path.
P ≔ PetersenGraph⁡
P≔Graph 2: an undirected graph with 10 vertices and 15 edge(s)
The Petersen graph has a Hamiltonian path starting at 8 and ending at 4.
The Petersen graph does not have a Hamiltonian path starting at 8 and ending at 9.
The GraphTheory[FindHamiltonianCycle] and GraphTheory[FindHamiltonianPath] commands were introduced in Maple 2019.
For more information on Maple 2019 changes, see Updates in Maple 2019.
Download Help Document