Definíció: Egy C kör egy G gráfban Hamilton-kör, ha C a G gráf összes csúcsán áthalad.
Definíció: Egy P út egy G gráfban Hamilton-út, ha P a G gráf összes csúcsán áthalad.
A Hamilton-kör, illetve Hamilton-út fogalma Sir William Rowan Hamilton -ról kapta nevét.
Megjegyzés: Egy Hamilton-kör tetszőleges élét elhagyva egy Hamilton-utat kapunk.
Alapkérdések: Adott egy G gráf. Hogyan dönthető el, hogy G-ben van-e Hamilton-kör? Ha van benne, hogyan található meg egy? Ha nincs, akkor mi akadályozza meg?
A fenti kérdésekre csak részleges válaszok ismertek. Ezekből szemezgetünk az alábbiakban.
Természetesen, ha G nem összefüggő, de ha már nem is kétszeresen összefüggő, akkor nem tartalmazhat Hamilton-kört. Ezt a feltételt általánosítja a következő egyszerű megállapítás. Egy körgráfból tetszőlegesen elhagyva k pontot legfeljebb k komponens keletkezik. természetesen ugyanez igaz Hamilton-kört tartalmazó gráfokra is: Egy Hamilton-kört tartalmazó gráfból tetszőlegesen elghagyva k pontot legfelejbb k komponens keletkezik. Azaz, ha egy gráfban k pontot elhagyva k-nál több komponens keletkezik, akkor nem tartalmazhat Hamilton-kört.
Sajnos ha tetszőlegesen elhagyva a K ponthalmazt a keletkező komponensek száma legfeljebb |K|, akkor sem biztos, hogy van Hamilton-kör gráfban. Erre példa a Petersen-gráf:
Hamilton-út, illetve Hamilton-kör keresését relaxáljuk: először csak hosszú utat keressünk. Ezt is úgy tegyük, hogy egy adott utat próbálunk hosszabbítani/javítani/növelni, majd ezt a javítást ismételgetjük addig, amíg tudjuk. Elakadáskor egy olyan utunk lesz, amelyet növelési eljárásunk nem tud meghosszabbítani.
A naív hosszabbítás, ha egy P út v végpontjának van olyan u szomszédja, amely nem esik P-re, akkor P-t leírő sorozatot kibővítjük ey vu éllel és az u csúccsal. Ekkor P triviális javításáról beszélünk. A triviális javítás ismételgetésével jutunk el a mohó útnövelési eljáráshoz.
Lemma: Ha egy egyszerű, minden pontjának legalább d a foka, akkor a mohó útnövelési eljárás outputja egy legalább d hosszú út.
Vegyük észre, hogy a mohó útnövelést bármelyik pontból elindíthatjuk és az útnövelé során útjaink kezdőpontja nem változik. Ezen észrevétel alapján fogalmazhatjuk meg a következő lemmát.
Lemma: Ha egy egyszerű, minden pontjának legalább d a foka, akkor minden pontjából indul ki egy legalább d hosszú út.
Könnyű példákat adni, amelyek azt mutatják, hogy ha egy egyszerű gráf minden foka legalább d, akkor előfordulhat, hogy d hosszú út megtalálása után a mohó útnövelés elakad. Hosszabb út megtalálásához újabb ötletre van szükségünk. Az ötlet már előttünk hever: a mohó útnövelés elakadásánál az aktuális P út u végpontjának mindegyik szomszédja P-re esik. Legyen s egy szomszéd, amely különbözik az úton u-t megelőző csúcstól. Járjuk be az utat. s-be érkezve egy elágazáshoz jutunk. A kiinduló úttól eltérő folytatást követve egy új P' úthoz jutunk. Erre az útra igaz, hogy
Tétel (Dirac-tétel): Legyen G egy egyszerű gráf, amelynek minden pontjának legalább |V(G)|/2 a foka, és P egy út G-ben, amley nem Hamilton-út. Ekkor P triviális vagy csavart módon növelhető. Ennek egy következménye, hogy egy egyszerű gráfban, amelynek minden pontjának legalább |V(G)|/2 a foka egy egyszerű algoritmussal Hamilton-utat tudunk találni.
Tétel (Dirac-tétel): Ha G egy egyszerű, legalább 3 pontú gráf, amelynek minden pontjának legalább |V(G)|/2 a foka, akkor G tartalmaz Hamilton-kört.
A Hamilton-problémakörrel foglalkozó honlapok:
The Hamiltonian Page (Maintained by Pablo Moscato and Z. Gregory Gutin)
Basil Vandegriend tézise a Hamilton problémáról.
A Hamiltonian Circuit címszó Eric Weisstein on-line matematikai enciklopédiájában.