Hamilton-kör

A Wikipédiából, a szabad lexikonból.

Tartalomjegyzék

[szerkesztés] Hamilton-út és Hamilton-kör

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.

[szerkesztés] Alapkérdések

A gráfelmélet egyik nevezetes problémája, hogy van-e könnyen megadható ekvivalencia feltétel Hamilton-kör létezésére. Mivel az a probléma, hogy egy adott gráfban van-e Hamilton-kör, NP-teljes, ilyen ekvivalens feltétel megadása nem remélhető.

Olyan feltételek viszont megadhatók, amelyek teljesülése esetén mindenképpen van Hamilton-kör.

[szerkesztés] Akadályok

Ha G nem összefüggõ, de ha már nem is kétszeresen összefüggõ, akkor nem tartalmazhat Hamilton-kört. Ennek az általánosítása a következő:
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 elhagyva 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 a gráfban. Erre példa a Petersen-gráf.

[szerkesztés] Elégséges feltétel Hamilton-kör létezésére

Tétel (Dirac-tétel): Ha G egy egyszerû, legalább 3 pontú gráf, amelynek minden pontjának legalább \frac{|V(G)|}{2} a foka, akkor G tartalmaz Hamilton-kört.

[szerkesztés] Hamilton-körök véletlen gráfokban

A véletlen gráfok elméletének hosszú ideig megoldatlan, nevezetes problémája volt, hogy milyen élszám garantálja 1-hez konvergáló valószínűséggel Hamilton-kör létezését. Erdős és Rényi nevezetes cikkükben megmutatták, hogy ε > 0-ra egy n pontszámú és \left(\frac{1}{2}-\epsilon\right)n\log n élszámú véletlen gráf majdnem biztosan nem összefüggő, míg egy \left(\frac{1}{2}+\epsilon\right)n \log n élszámú majdnem biztosan az. Azt az állítást azonban, hogy, ha az élek száma cnlogn, akkor, elég nagy c-re, a gráf majdnem biztosan összefüggő, csak 1976-ban igazolta Pósa Lajos és A. D. Korsunov.

Végül, finom módszerek használatával, Komlós János és Szemerédi Endre azt is igazolta, hogy ha az élek száma

\frac12n\log n+\frac12n\log\log n+cn,

akkor n növekedtével annak valószínűsége, hogy a gráf tartalmaz Hamilton-kört, a következő értékhez konvergál:

e^{-e^{-2c}}.

[szerkesztés] Hivatkozások

The Hamilton page
Sir William Rowan Hamilton
Hajnal Péter: Gráfelmélet, Polygon, Szeged, 2003.