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.
Simple to state, but difficult to solve (NP-hard).
Example graph and two possible Hamilton paths:
![[Diagram:Pics/graphs/hamilton1.png]](Pics/graphs/hamilton1.png)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}