GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

FindHamiltonianCycle

  

find Hamiltonian cycle

  

FindHamiltonianPath

  

find Hamiltonian path

 

Calling Sequence

Parameters

Options

Description

Examples

Compatibility

Calling Sequence

FindHamiltonianCycle(G, opts)

FindHamiltonianPath(G, opts)

Parameters

G

-

graph

opts

-

(optional) zero 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 circuit 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.

• 

A 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 circuit contains a Hamiltonian path, but the reverse is not true.

• 

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.

Examples

withGraphTheory:

withSpecialGraphs:

CCycleGraph5

CGraph 1: an undirected unweighted graph with 5 vertices and 5 edge(s)

(1)

IsHamiltonianC

true

(2)

FindHamiltonianCycleC

1,2,3,4,5,1

(3)

FindHamiltonianCycleC,startvertex=4

4,3,2,1,5,4

(4)

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

PPetersenGraph

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

(5)

IsHamiltonianP

false

(6)

FindHamiltonianPathP

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

(7)

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

FindHamiltonianPathP,startvertex=8,endvertex=4

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

(8)

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

FindHamiltonianPathP,startvertex=8,endvertex=9

Compatibility

• 

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

• 

For more information on Maple 2019 changes, see Updates in Maple 2019.

See Also

DrawGraph

HighlightTrail

IsEulerian

IsHamiltonian

TravelingSalesman