V roce 1857 formuloval irsky matematik William Rowan Hamilton nasledujici problem: jak najit v danem grafu cestu mezi danymi dvema vrcholy tak, aby prochazela kazdym z ostatnich vrcholu, a to prave jednou? Dodnes se tento problem po nem jmenuje problem Hamiltonovske cesty. Specialnim pripadem tohoto problemu je pak problem Hamiltonovske kruznice, coz je stejna uloha s tim, ze vychozi a cilovy vrchol jsou totozne. Zobecnenim problemu Hamiltonovske kruznice na ohodnoceny graf ziskame problem obchodniho cestujiciho (travelling salesman), kdy hledame nejkratsi Hamiltonovskou kruznici daneho ohodnoceneho grafu.

      Vsechny tyto problemy patri do tridy tzv. NP-uplnych problemu, pro ktere zatim neexistuje lepsi nez exponencialni algoritmus k reseni daneho problemu. Chceme-li tedy znat optimalni reseni, musime proste vyzkouset vsechny moznosti. Aby se daly NP-uplne problemy resit v realnem case, pouzivaji se nejruznejsi heuristiky, tj. algoritmy, ktere nenajdou nejlepsi, ale nejake prijatelne reseni.

      Konkretne pro pripad Hamiltonovskych cest lze pouzit nasledujici heuristiku: cestu tvorime tak, ze pridavame vzdy jednu hranu, a sice tu, ktera ma nejmensi vahu z tech hran, ktere se nam k jiz existujici ceste "hodi". Postup opakujeme, dokud nedostaneme vyslednou cestu. Jde tedy o tzv. hladovy algoritmus pouzivany napriklad pri tvorbe minimalni kostry grafu.