FindHamiltonianCycle - Maple Help

GraphTheory

 FindHamiltonianCycle
 find Hamiltonian cycle
 FindHamiltonianPath
 find Hamiltonian path

 Calling Sequence FindHamiltonianCycle(G, opts) FindHamiltonianPath(G, opts)

Parameters

 G - graph opts - (optional) one or more options as specified below

Options

 • 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.

Description

 • 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.

Definition

 • 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.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $C≔\mathrm{CycleGraph}\left(5\right)$
 ${C}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 5 vertices and 5 edge\left(s\right)}}$ (1)
 > $\mathrm{IsHamiltonian}\left(C\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{FindHamiltonianCycle}\left(C\right)$
 $\left[{1}{,}{2}{,}{3}{,}{4}{,}{5}{,}{1}\right]$ (3)
 > $\mathrm{FindHamiltonianCycle}\left(C,\mathrm{startvertex}=4\right)$
 $\left[{4}{,}{3}{,}{2}{,}{1}{,}{5}{,}{4}\right]$ (4)

The Petersen graph is not Hamiltonian (that is, it does not contain a Hamiltonian cycle), but it does contain a Hamiltonian path.

 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (5)
 > $\mathrm{IsHamiltonian}\left(P\right)$
 ${\mathrm{false}}$ (6)
 > $\mathrm{FindHamiltonianPath}\left(P\right)$
 $\left[{10}{,}{9}{,}{8}{,}{7}{,}{6}{,}{1}{,}{5}{,}{4}{,}{3}{,}{2}\right]$ (7)

The Petersen graph has a Hamiltonian path starting at 8 and ending at 4.

 > $\mathrm{FindHamiltonianPath}\left(P,\mathrm{startvertex}=8,\mathrm{endvertex}=4\right)$
 $\left[{8}{,}{9}{,}{10}{,}{6}{,}{7}{,}{3}{,}{2}{,}{1}{,}{5}{,}{4}\right]$ (8)

The Petersen graph does not have a Hamiltonian path starting at 8 and ending at 9.

 > $\mathrm{FindHamiltonianPath}\left(P,\mathrm{startvertex}=8,\mathrm{endvertex}=9\right)$

Compatibility

 • The GraphTheory[FindHamiltonianCycle] and GraphTheory[FindHamiltonianPath] commands were introduced in Maple 2019.