تسجيل الدخول

تسجيل

Hamiltonian Path

المؤلف:  Angluin, D. and Valiant, L

المصدر:  "Probabilistic Algorithms for Hamiltonian Circuits and Matchings." J. Comput. Sys. Sci. 18

الجزء والصفحة:  ...

11-5-2022

4168

Hamiltonian Path

A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once. If a Hamiltonian path exists whose endpoints are adjacent, then the resulting graph cycle is called a Hamiltonian cycle (or Hamiltonian cycle).

A graph that possesses a Hamiltonian path is called a traceable graph.

In general, the problem of finding a Hamiltonian path is NP-complete (Garey and Johnson 1983, pp. 199-200), so the only known way to determine whether a given general graph has a Hamiltonian path is to undertake an exhaustive search

Any bipartite graph with a vertex parity unbalance  has no Hamiltonian paths.

Finding a single Hamiltonian path of a graph  is implemented in the Wolfram Language as FindHamiltonianPath[g]. All Hamiltonian paths of a given graph can be found (inefficiently) using the command HamiltonianPath[g, All] in the Wolfram Language package Combinatorica` . A precomputed list of all Hamiltonian paths for many named graphs can be obtained using GraphData[graph, "HamiltonianPaths"], where and both orientations of paths are included (so that {" src="https://mathworld.wolfram.com/images/equations/HamiltonianPath/Inline3.svg" style="height:21px; width:6px" />1, 2, 3}" src="https://mathworld.wolfram.com/images/equations/HamiltonianPath/Inline4.svg" style="height:21px; width:6px" /> is considered distinct from {" src="https://mathworld.wolfram.com/images/equations/HamiltonianPath/Inline5.svg" style="height:21px; width:6px" />3, 2, 1}" src="https://mathworld.wolfram.com/images/equations/HamiltonianPath/Inline6.svg" style="height:21px; width:6px" />). A precomputed count of the corresponding number of Hamiltonian paths is given by GraphData[graph, "HamiltonianPathCount"].

The total numbers of directed Hamiltonian paths for all simple graphs of orders , 2, ... are 0, 2, 8, 50, 416, 5616, 117308, 4862736, ... (OEIS A193352).

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. A probabilistic algorithm due to Angluin and Valiant (1979), described by Wilf (1994), can also be useful to find Hamiltonian cycles and paths. A Hamiltonian path between two vertices  and  can be found if an algorithm for Hamiltonian cycles is available. This can be done by checking if the original graph  contains the edge  and adding it if not to obtain . Since a Hamiltonian path with adjacent endpoints is a Hamiltonian cycle and since  and  are now adjacent, finding a Hamiltonian cycle and splitting at the edge gives a Hamiltonian path from  to  in . Similarly, if no Hamiltonian cycle exists in , then there is no Hamiltonian path from  to  in .

The following table summarizes the numbers of (undirected) Hamiltonian paths on various classes of graphs.

graph	formula
barbell graph
cocktail party graph
complete graph
complete bipartite graph
-crossed prism graph
cycle graph
gear graph
ladder graph
Möbius ladder
path graph	1
prism graph
sun graph
wheel graph

Recurrence relations for the number of directed Hamiltonian paths for some graph families are summarized below.

graph	order	recurrence
antiprism graph	9
crown graph	3
prism graph	6

---

REFERENCES

Angluin, D. and Valiant, L. "Probabilistic Algorithms for Hamiltonian Circuits and Matchings." J. Comput. Sys. Sci. 18, 155-190, 1979.

Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, p. 199, 1983.

Rubin, F. "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21, 576-580, 1974.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 175, 1990.

Sloane, N. J. A. Sequences A005843, A006070/M5295, A046092, A158664, A033996, A091299, A096969, A096970, A124350, A124352, A137890, A137892, A165134, A193346, and A233826 in "The On-Line Encyclopedia of Integer Sequences."Wilf, H. S. Algorithms and Complexity. pp. 120-122. Summer, 1994. http://www.math.upenn.edu/~wilf/AlgoComp.pdf.