IsHamiltonian - Maple Help

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.

Hamiltonian graphs in SpecialGraphs

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

 Graph Number of Vertices Number of Edges 5 6 10 18 11 20 12 18 12 18 12 18 12 24 14 21 15 39 16 24 16 32 16 48 18 27 19 38 20 30 23 63 24 36 24 36 27 216 30 75 32 48 32 80 36 90 50 175 52 104 56 280 57 171 60 90 70 105 77 616 81 810 90 135 100 1100 100 1800 102 153 112 168 275 15400

Examples

 > $\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 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 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 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}}_{\mathrm{IsHamiltonian}}≔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 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 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.