Online Help

•

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.

•

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.

•

The following are graphs in the SpecialGraphs subpackage which are Hamiltonian..

>

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

>

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

>

$P≔\mathrm{PetersenGraph}\left(\right)$

$P≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edges}$

(1)

>

$\mathrm{IsHamiltonian}\left(P\right)$

$\mathrm{false}$

(2)

>

$\mathrm{AddEdge}\left(P\,\left\{1\,3\right\}\right)$

$\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 16\; edges}$

(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\; graph\; with\; 8\; vertices\; and\; 12\; edges}$

(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\; graph\; with\; 6\; vertices\; and\; 9\; edges}$

(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\; graph\; with\; 7\; vertices\; and\; 12\; edges}$

(13)

>

$\mathrm{IsHamiltonian}\left(\mathrm{K34}\right)$

IsHamiltonian: "graph satisfies IndependenceNumber(G) > NumberOfVertices(G)/2 ==> it's not hamiltonian"

$\mathrm{false}$

(14)

•

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 .