Hamiltono maršrutas

Hamiltono maršrutas - maršrutas grafe, kuriuo galima pereiti visas jo viršūnes po vieną kartą. Jei tokiu maršrutu grįžtama į pradinę viršūnę, jis vadinamas Hamiltono ciklu, jei ne - Hamiltono keliu arba Hamiltono grandine. Pavadinimas kilo nuo pavardės matematiko Viljamo Rovano Hamiltono, 1857 m. sukūrusio žaidimą, kuriame reikėjo apeiti visas dodekaedro (tiksliau - jį atitinkančio grafo) viršūnes einant jo briaunomis.

Egzistavimo sąlygos 
Nėra žinoma jokios paprastos būtinos ir pakankamos Hamiltono maršruto egzistavimo sąlygos.

Taikymai 
Uždavinys, kai pilnajame svoriniame grafe ieškoma minimalaus Hamiltono ciklo, vadinamas keliaujančio pirklio uždaviniu ir taikomas logistikoje.

Algoritmas Hamiltono ciklui rasti C++ kalba:

Išnašos 

Grafų teorija