Hamiltonian path
From Wikipedia, the free encyclopedia
Contents |
[edit] Hamiltonian Circuit
A Hamiltonian circuit, also called a Hamiltonian cycle, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196). By convention, the trivial graph on a single node is considered to posses a Hamiltonian circuit, but the connected graph on two nodes is not. A graph possessing a Hamiltonian circuit is said to be a Hamiltonian graph. The Hamiltonian circuit is named after Sir William Rowan Hamilton, who devised a puzzle in which such a path along the polyhedron edges of an dodecahedron was sought (the Icosian game).
Different types of graphs that are Hamiltonian circuits include antiprism graph, complete graph, cycle graph, hypercube graph, and the Möbius ladder.
[edit] Finding a Hamiltonian Circuit
In general, the problem of finding a Hamiltonian circuit is NP-complete (Garey and Johnson 1983), so the only known way to determine whether a given general graph has a Hamiltonian circuit is to undertake an exhaustive search. Rubin (1974) describes an efficient search procedure that can find some or all Hamilton paths and circuits in a graph using deductions that greatly reduce backtracking and guesswork.
[edit] Hamiltonian Path
A Hamiltonian path, also called a Hamilton path, is a path between two vertices of a graph that visits each vertex exactly once. A Hamiltonian path that is also a graph cycle is called a Hamiltonian circuit (or Hamiltonian cycle).
A graph that possesses a Hamiltonian path is called a traceable graph.
A Hamiltonian path of a graph can be identified using HamiltonianPath[g] in the Mathematica add-on package DiscreteMath`Combinatorica` (which can be loaded with the command <<DiscreteMath`) , which however only gives correct results for undirected graphs. Similarly, all Hamiltonian paths of a given graph can be found using the command HamiltonianPath[g, All]
Rubin (1974) describes an efficient search procedure that can find some or all Hamilton paths and circuits in a graph using deductions that greatly reduce backtracking and guesswork.
The number of Hamiltonian paths on an n-hypercube is 0, 0, 48, 48384, ... (Sloane's A006070; Gardner 1986, pp. 23-24).
The following table summarizes the numbers of (directed) Hamiltonian paths on various classes of graphs.
[edit] Eulerian Path
An Euler path, also called an Eulerian trail, is a walk on the graph edges of a graph which uses each graph edge in the original graph exactly once. A connected graph has an Eulerian trail iff it has at most two graph vertices of odd degree.
[edit] Eulerian Circuit
An Eulerian trail which starts and ends at the same graph vertex. In other words, it is a graph cycle which uses each graph edge exactly once. The term Eulerian cycle is also used synonymously with Eulerian circuit. For technical reasons, Eulerian circuits are mathematically easier to study than are Hamiltonian circuits.
As a generalization of the Königsberg bridge problem, Euler showed (without proof) that a connected graph has an Eulerian circuit iff it has no graph vertices of odd degree.
Fleury's algorithm is an elegant, but inefficient, method of generating Eulerian circuit. An Eulerian cycle of a graph may be found using EulerianCycle[g] in the Mathematica add-on package DiscreteMath`Combinatorica` (which can be loaded with the command <<DiscreteMath`) .
The only Platonic solid possessing an Eulerian circuit is the octahedron, which has Schläfli symbol {4}; all other Platonic graphs have odd degree sequences. Similarly, the only Eulerian Archimedean solids are the cuboctahedron, icosidodecahedron, small rhombicosidodecahedron, and small rhombicuboctahedron.
