Hamiltonian path

A path in a graph that visits every vertex exactly once. Its endpoints may differ, unlike a Hamiltonian cycle, which returns to its starting vertex.

Graph: A mathematical structure consisting of vertices connected by edges. A Hamiltonian path is defined by the vertices and edges of a graph.
Hamiltonian path problem: The decision problem of determining whether a graph contains a Hamiltonian path. It formalizes the existence question for this graph structure.
Eulerian path: A trail in a graph that uses every edge exactly once, though it may revisit vertices. It covers edges rather than requiring each vertex to appear once.
NP-complete: A complexity class of decision problems that are both in NP and at least as hard as every problem in NP. Hamiltonian path in general graphs is NP-complete.
Path in graph theory: A sequence of distinct vertices in which consecutive vertices are joined by edges. Hamiltonian paths are paths with the additional requirement of including every vertex.
Backtracking: A search method that builds candidate solutions and abandons partial solutions that cannot succeed. It explores vertex sequences while pruning choices that cannot form a full path.
Traveling salesperson problem: An optimization problem seeking a shortest tour that visits each city once and returns to its start. Its tours are Hamiltonian cycles with edge costs and an optimization objective.
NP-hardness: A property of problems at least as difficult as every problem in NP under polynomial-time reductions. Optimization variants, including finding a longest path, are NP-hard.
Hamiltonian cycle: A cycle in a graph that visits every vertex exactly once before returning to its starting vertex. It adds a closing edge between the path’s endpoints.
Held–Karp algorithm: A dynamic programming algorithm that solves the traveling salesperson problem in exponential time. Its subset-based recurrence can also decide whether a graph has a Hamiltonian path.

Linked from 6 pages