Hamiltonpfad

Hamiltonpfad, in graph theory, is a path that visits every vertex of a graph exactly once. If such a path exists, the graph is said to contain a Hamiltonpfad; when the path also starts and ends at adjacent vertices so that it forms a cycle, it is called a Hamiltonian cycle (Hamiltonkreis). A graph may have a Hamiltonpfad without having a Hamiltonian cycle.

Not every graph has a Hamiltonpfad. Deciding the existence of one is known as the Hamiltonian path problem and is NP-complete for general graphs, both in undirected and directed settings. This means there is no known polynomial-time algorithm to solve the problem in the general case, although many special cases and classes of graphs are solvable efficiently.

Examples help illustrate the concept. In a complete graph Kn, a Hamiltonpfad always exists, and in fact many different Hamiltonian cycles exist. On the other hand, the existence of a Hamiltonpfad in arbitrary sparse graphs is not guaranteed and depends on the arrangement of edges.

There are several important results related to Hamiltonicity. Dirac’s theorem states that a graph with n vertices (n ≥ 3) and minimum degree at least n/2 is Hamiltonian, hence contains a Hamiltonpfad and a Hamiltonian cycle. Ore’s theorem provides a related sufficient condition based on degree sums of non-adjacent vertices. In practice, algorithms to find Hamiltonpfade use backtracking, sometimes augmented with pruning, or dynamic programming approaches (such as Held–Karp) and reductions to the traveling salesman problem for weighted graphs. Heuristic and approximate methods are common for large instances.

The concept is named after William Rowan Hamilton, who studied circuits and polyhedra in the 19th century, giving rise to the terms Hamiltonian path and Hamiltonian cycle.