Hamilton Path and Tour
Hamilton path problem:
find a simple path connecting two vertices
v,w
in graph
G
such that the path includes each
vertex
exactly once
If
v = w
, then we have a Hamilton Tour.
No efficient algorithm known
(use generate-and-test)
![[Diagram:Pics/graphs/hamilton1.png]](Pics/graphs/hamilton1.png)
![[prev]](icon/prev.gif){kind=icon}
![[index]](icon/up.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}