Hamilton-kör

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

Tartalomjegyzék

1 Hamilton-út és Hamilton-kör
2 Alapkérdések
3 Akadályok
4 Elégséges feltétel Hamilton-kör létezésére
5 Hamilton-körök véletlen gráfokban
6 Hivatkozások

[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

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 $c n log n$ , akkor, elég nagy c-re, a gráf majdnem biztosan összefüggő, csak 1976-ban igazolta Pósa Lajos és A. D. Korsunov.