Hosszú utakat, köröket keresõ algoritrmusok, Dirac-tétel

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

ugyanabból a pontból indul ki mint P,
hossza megegyezik P hosszával,
sõt ugyanazokat a pontokat járja be, mint P,
de végpontja P végpontjától különbözõ lesz.

P'-t a P csavart vátozatának nevezzük. u-nak a P-n u-t megelõzõ u ' csúcstól különbözõ szomszédai mindegyikéhez tartozik egy csavart változat. A végpont ú szomszédához is rendelhetõ egy csavart változat: maga P. Ha u foka d, akkor d darab csavart változatot kapunk, ezek közül egy P, a maradék d-1 darab pedig valódi csavart. Így a mohó algoritmus egy módosítását építhetjük fel: az aktuális út helyett d darab csavart úttal dolgozunk. ha bármelyiket triviális módon növelhetjük, akkor megtesszük. Amennyiben P-t növeljük, akkor egy triviális javítást végeztünk. Ha egy valódi csavart változatot hosszabbítottunk meg, akkor csavart útnövelésrõl beszélünk. Ezt ismételgetjük, amíg olyan úthoz nem jutunk, amely bármely csavart változata már nem növelhetõ triviálisan.

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: C₁, C₂, C₃, ...
Csavart növelési kísérlet: Sorba nézzük meg C_i 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 C_i 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.

A Továbbélesített mohó algoritmus (már nem mohó):
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 C_i 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.