Hamiltonian path
A Hamiltonian path is a path in a graph which contains each vertex of the graph exactly once. A Hamiltonian cycle is a Hamiltonian path, which is also a cycle. Knowing whether such a path exists in a graph, as well as finding it is a fundamental problem of graph theory. It is much more difficult than finding an Eulerian path, which contains each edge exactly once. The problem of finding a Hamiltonian path is NP-complete. There are two classes of graphs: directed and undirected graphs. In directed graphs, an edge can only be travelled in one direction, in undirected graphs it can be travelled in both directions. The Travelling Salesman Problem is an instance of this problem. Its task is to find the shortest Hamiltonian cycle, usually in a directed graph, with weight (or distances) attached to the edges.