Hamiltonian Path and Circuit
Hamiltonian path problem:
- find a 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 Hamiltonian circuit
Simple to state, but difficult to solve (NP-complete)
Many real-world applications require you to visit all vertices of a graph:
- Travelling salesman
- Bus routes
- …
Problem named after Irish mathematician, physicist and
astronomer Sir William Rowan Hamilton (1805 — 1865)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}