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, amely nem Hamilton-út. Ekkor P triviális vagy csavart módon növelhető.
Bizonyítás: Legyen P a tétel nem Hamilton-útja. Legyen U a csavart változtok végponthai által alkotott halmaz. Legyen v egy nem P-re eső csúcs és legyen S a v csúcs szomszédainak halmaza. U és S mindkét halmaz legalább |V(G)|/2 elemű részhalmaza V(G)-{v}-nek, egy |V(G)|-1 elemű halmaznak. Így van U és S halmazonak egy x közös eleme. Csavarjuk P-t úgy, hogy x legyen a végpontja (x U eleme), majd a csavart utat folytassuk v-be (x S eleme).
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:
Élesített mohó algoritmus:
Inicializálás: Legyen P egy kiinduló út (például
egy tetszőleges pont, mint egy 0 hosszú út).
Mohó növelési kísérlet:
Próbáljuk meg P-t mohó módon növelni.
Ha sikerül, tegyük meg és ismét a mohó növelési kísérlettel
folytassuk eljárásunkat.
%%%% Ha a mohó hosszabbítás nem működik, akkor P végpontjának összes szomszédja P-re esik és mindegyik
P egy csavarását adja. %%%%
Csavart változatok sorbavétele:Rendezzük sorba P csavart változatait:
C1, C2, C3, ...
Csavart növelési kísérlet:
Sorba nézzük meg Ci mohó módon növelhető-e.
Ha igen, végezzük el a növelést és a növelt úttal
kezdjük üjra mohó növelési kísérletet.
Ha egyik Ci sem növelhető mohó módon, akkor álljunk le,
aktuális utunk az output.
A bizonyításunkból az is adódik, hogy feltételeink mellett az élesített mohó algoritmus Hamilton-utat talál.
A fenti bizonyításban előforduló gondolatok egyszerű felhasználása vezet el a következő élesítéshez.
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.
Az élesített mohó algoritmus sem használja ki ötleteinket a végletekig. Ha egyik csavarás sem vezet el növeléshez leállunk, pedig csavarás csavarása újabb helyzetet hozhat elő. Az alábbi algoritmusvázlat ezeket a továbblépéseket próbálja összegezni.
Továbbélesített mohó algoritmus:
Inicializálás: Legyen P egy kiinduló út (például
egy tetszőleges pont, mint egy 0 hosszú út).
Mohó növelési kísérlet:
Próbáljuk meg P-t mohó módon növelni.
Ha sikerül, tegyük meg és ismét a mohó növelési kísérlettel
folytassuk eljárásunkat.
%%%% Ha a mohó hosszabbítás nem működik, akkor P végpontjának összes szomszédja P-re esik és mindegyik
P egy csavarását adja. %%%%
Csavart növelési kísérlet:
Sorba nézzük meg Ci mohó módon növelhető-e.
Ha igen, végezzük el a növelést és a növelt úttal
kezdjük újra mohó növelési kísérletet.
Ha nem, akkor próbálkozzunk egy másik csavarással, vagy ezt a csavarást
csavarjuk tovább.
Ez azért csak egy vázlat, mert a próbálkozásaink kiválasztását nem tárgyalja, az algoritmus leállásáról nem szól. Természetesen, ha Hamilton-úthoz jutunk leállunk. Ha azonban ``elég sokáig'' nem tudunk javítani, akkor elképzelhető, hogy próbálkozásaink rossz irányban haladnak. Ennek ellenére érdemes egy példát végiggondolni.
Gabriel Andrew Dirac a fenti tétel szerzője a neves Nobel-díjas fizikus Paul Adrien Maurice Dirac mostohafia. Paul Adrien Maurice Dirac Wigner Jenő (szintén Nobel-díjas) fizikus testvérét vette el.