Hamiltonvei
Utseende
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/60/Hamiltonian_path.svg/250px-Hamiltonian_path.svg.png)
Hamiltonvei er i matematisk grafteori en vei i en rettet eller urettet graf som går gjennom alle nodene akkurat én gang. En hamiltonsyklus er en hamiltonvei som ender opp i samme node som den startet. Å finne ut om en villkårlig graf inneholder en hamiltonvei er et NP-komplett problem.
Hamiltonvei er oppkalt etter matematikeren William Rowan Hamilton.
Kilder[rediger | rediger kilde]
- Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th Edition (side 671-676) ISBN 9780071315012