Hopp til innhold

Hamiltonvei

Fra Wikipedia, den frie encyklopedi
Et eksempel på en Hamiltonsyklus

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.