IsHamiltonian - Maple Help

# Online Help

###### All Products    Maple    MapleSim

GraphTheory

 IsHamiltonian
 test if graph is Hamiltonian

 Calling Sequence IsHamiltonian(G, opt) IsHamiltonian(G, C, opt)

Parameters

 G - unweighted graph C - (optional) name opt - (optional) equation of the form method = value; specify method to use

Options

 • method=one of legacy, sat, or tsp.
 Specifies the algorithm to use in seeking a Hamiltionian circuit. The default, method=legacy, uses a simple depth-first search to find a Hamiltonian circuit. The sat method encodes the problem as a logical formula and seeks a satisfying solution, and the tsp method seeks to find a Hamiltonian circuit which is an optimal solution to the traveling salesman problem.

Description

 • A graph G on n vertices is Hamiltonian if there exists a Hamiltonian circuit, that is, a cycle in G containing each of the n vertices exactly once.
 • The IsHamiltonian(G) function returns true if the graph is Hamiltonian and false otherwise.  If G is Hamiltonian and a name C is specified as a second argument, then C is assigned a list of vertices of a Hamiltonian cycle of the graph starting and ending with the first vertex in G. For example, if the graph G is the triangle graph created with Graph({{1,2},{1,3},{2,3}}), the cycle is output as $\left[1,2,3,1\right]$.
 • The algorithm works for directed graphs and it ignores the edge weights of weighted graphs.
 • The algorithm first checks whether G is disconnected or whether it has any articulation points.  If so, then G is not Hamiltonian. Then it tests whether the minimum degree of G is at least $\frac{n}{2}$ where $n$ is the number of vertices.  If so G is Hamiltonian.  Then, if G is not too sparse, the algorithm checks whether the independence number of G is greater than $\frac{n}{2}$. If so, then G is not Hamiltonian.  Failing these checks, the default algorithm does a simple exhaustive search for a Hamiltonian cycle using depth-first-search. By setting infolevel[IsHamiltonian] to an integer greater than 1 a message will be displayed stating how the graph was proven, or disproven, to be Hamiltonian.
 • An example of a graph which is Hamiltonian for which it will take exponential time to find a Hamiltonian cycle is the hypercube in d dimensions which has $n={2}^{d}$ vertices and $m=d{2}^{d-1}$ edges. The algorithm has no difficulty in finding a Hamiltonian cycle for $d=5$ where $n=32$ and $m=80$ but for $d=6$, $n=64$, and $m=192$ it takes a long time.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (1)
 > $\mathrm{IsHamiltonian}\left(P\right)$
 ${\mathrm{false}}$ (2)
 > $\mathrm{AddEdge}\left(P,\left\{1,3\right\}\right)$
 ${\mathrm{Graph 1: an undirected unweighted graph with 10 vertices and 16 edge\left(s\right)}}$ (3)
 > $\mathrm{IsHamiltonian}\left(P,'C'\right)$
 ${\mathrm{true}}$ (4)
 > $C$
 $\left[{1}{,}{2}{,}{9}{,}{8}{,}{5}{,}{4}{,}{10}{,}{6}{,}{7}{,}{3}{,}{1}\right]$ (5)
 > $\mathrm{DrawGraph}\left(P\right)$
 > $\mathrm{H3}≔\mathrm{HypercubeGraph}\left(3\right)$
 ${\mathrm{H3}}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 8 vertices and 12 edge\left(s\right)}}$ (6)
 > $\mathrm{IsHamiltonian}\left(\mathrm{H3},'C'\right)$
 ${\mathrm{true}}$ (7)
 > $C$
 $\left[{"000"}{,}{"100"}{,}{"110"}{,}{"010"}{,}{"011"}{,}{"111"}{,}{"101"}{,}{"001"}{,}{"000"}\right]$ (8)
 > $\mathrm{HighlightTrail}\left(\mathrm{H3},C,\mathrm{red}\right)$
 > $\mathrm{DrawGraph}\left(\mathrm{H3}\right)$
 > $\mathrm{infolevel}\left[\mathrm{IsHamiltonian}\right]≔2$
 ${{\mathrm{infolevel}}}_{{\mathrm{IsHamiltonian}}}{≔}{2}$ (9)
 > $\mathrm{IsHamiltonian}\left(\mathrm{H3}\right)$
 ${\mathrm{true}}$ (10)
 > $\mathrm{K33}≔\mathrm{CompleteGraph}\left(3,3\right)$
 ${\mathrm{K33}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 6 vertices and 9 edge\left(s\right)}}$ (11)
 > $\mathrm{IsHamiltonian}\left(\mathrm{K33}\right)$
 IsHamiltonian:   "graph satisfies MinimumDegree(G) >= NumberOfVertices(G)/2 ==> it is hamiltonian"
 ${\mathrm{true}}$ (12)
 > $\mathrm{K34}≔\mathrm{CompleteGraph}\left(3,4\right)$
 ${\mathrm{K34}}{≔}{\mathrm{Graph 4: an undirected unweighted graph with 7 vertices and 12 edge\left(s\right)}}$ (13)
 > $\mathrm{IsHamiltonian}\left(\mathrm{K34}\right)$
 IsHamiltonian:   "graph satisfies IndependenceNumber(G) > NumberOfVertices(G)/2 ==> it's not hamiltonian"
 ${\mathrm{false}}$ (14)

Compatibility

 • The GraphTheory[IsHamiltonian] command was updated in Maple 2019.
 • The method option was introduced in Maple 2019.
 • For more information on Maple 2019 changes, see Updates in Maple 2019.

 See Also