Hamilton paths and circuits
A path x0,x1,…,xn-1,xn in the graph G=(V,E) is called a Hamilton path
iff V={x0,x1,…,xn-1,xn} and xi?xj for 0?i<j?n.
A circuit x0,x1,…,xn-1,xn ,x0 in a graph is called a Hamilton circuit iff
x0,x1,…,xn-1,xn is a Hamilton path in this graph.
Unfortunately, there are no fast algorithms for finding Hamilton paths.
Example. Nodes denote cities, arcs denote roads between them.
Is it possible to visit every city exactly once? In other words, is there
a Hamilton path in the graph?
This graph has a Hamilton
This graph has no Hamilton