GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/IsHamiltonian

GraphTheory

  

IsHamiltonian

 

Calling Sequence

Parameters

Options

Description

Examples

Compatibility

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 1,2,3,1.

• 

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 n2 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 n2. 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=2d vertices and m=d2d1 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

withGraphTheory:

withSpecialGraphs:

PPetersenGraph

PGraph 1: an undirected unweighted graph with 10 vertices and 15 edge(s)

(1)

IsHamiltonianP

false

(2)

AddEdgeP,1,3

Graph 1: an undirected unweighted graph with 10 vertices and 16 edge(s)

(3)

IsHamiltonianP,C

true

(4)

C

1,2,9,8,5,4,10,6,7,3,1

(5)

DrawGraphP

H3HypercubeGraph3

H3Graph 2: an undirected unweighted graph with 8 vertices and 12 edge(s)

(6)

IsHamiltonianH3,C

true

(7)

C

000,100,110,010,011,111,101,001,000

(8)

HighlightTrailH3,C,red

DrawGraphH3

infolevelIsHamiltonian2

infolevelIsHamiltonian2

(9)

IsHamiltonianH3

true

(10)

K33CompleteGraph3,3

K33Graph 3: an undirected unweighted graph with 6 vertices and 9 edge(s)

(11)

IsHamiltonianK33

IsHamiltonian:   "graph satisfies MinimumDegree(G) >= NumberOfVertices(G)/2 ==> it is hamiltonian"

true

(12)

K34CompleteGraph3,4

K34Graph 4: an undirected unweighted graph with 7 vertices and 12 edge(s)

(13)

IsHamiltonianK34

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

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

DrawGraph

HighlightTrail

IsEulerian

SpecialGraphs[HypercubeGraph]

TravelingSalesman