Hamilton-kör
Hamilton-körnek nevezünk egy kört egy gráfban, ha a gráf összes csúcsán pontosan egyszer halad át. A Hamilton-kör, illetve a Hamilton-út Sir William Rowan Hamiltonról kapta nevét, aki 1859-ben egy olyan játékot hozott forgalomba, amelynek a lényege az volt, hogy egy előre megadott gráf csúcspontjait kellett bejárni úgy, hogy minden csúcsban pontosan egyszer kellett járni. Állítólag a játéknak nem volt átütő sikere Hamilton kortársai között.
Tulajdonságai
szerkesztés- Egy Hamilton-kör tetszőleges élét elhagyva egy Hamilton-utat kapunk.
- Látható, hogy nem minden gráfban van Hamilton-kör (például fák, Petersen-gráf). Viszont az is látható, hogy például esetén minden csúcsú teljes gráfban van. Viszont Hamilton-út lehet olyan gráfban is, ami nem tartalmaz Hamilton-kört. Erre jó példa a Petersen-gráf vagy a kétcsúcsú teljes gráf.
- A Hamilton-kör egy speciális kör a gráfban, ellentétben az Euler-körrel.
- A Hamilton-út és a Hamilton-kör létezése a gráfelmélet alapvető problémája. A sakktáblák bejárhatóságának vizsgálata az e témakörhöz kapcsolódó tapasztalatok szerzését, sejtések megfogalmazását segítheti.
- Látszólag nagyon hasonló probléma az, hogy egy gráf éleit vagy csúcsait járjuk be egyszer. Az utóbbi azonban jóval nehezebb. Sőt általános esetben Hamilton-körök illetve utak keresésére ma sem ismert igazán jó algoritmus. A Hamilton-kör létezésének kérdése speciális esete a széles körben felmerülő utazó ügynök problémájának: Egy ügynöknek kell meglátogatnia bizonyos városokat útja során, és végül haza kell érnie. Adott, hogy valamelyik városból egy másik városba milyen költséggel tud eljutni (buszjegy ára, autóút ára stb.). Természetesen szeretné az utak összköltségét minimalizálni. Ez a feladat sok alkalmazás során felmerül, és csak bizonyos speciális esetekben ismeretesek jó algoritmusok a megoldására. Ha most feltesszük, hogy bizonyos városokból nem lehet közvetlenül eljutni egyes másik városokba, míg a többi városba egységnyi költséggel lehet eljutni, és az ügynöknek minden várost meg kell látogatnia, akkor a Hamilton-kör létezésére redukálódik. Hiszen tekintsük azt a gráfot, amelynek pontjai a városoknak megfelelő pont, és amelyben két pont akkor és csak akkor van összekötve, ha a nekik megfelelő városok között közvetlen összeköttetés van. Ebben a gráfban akkor és csak akkor van Hamilton-kör, ha az ügynök összköltséggel meg tud látogatni minden várost.
Alapkérdések
szerkesztésHosszú ideig a gráfelmélet egyik nevezetes problémája volt, hogyan lehet eldönteni, van-e egy adott gráfban Hamilton-kör. A komplexitáselmélet kialakulásának egyik fontos első lépéseként Richard Karp 1972-ben megmutatta, hogy ez a probléma NP-teljes, így mai ismereteink szerint ekvivalens feltétel megadása nem remélhető.
Megadhatók viszont elégséges feltételek.
Akadályok
szerkesztésHa 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 pontot legfeljebb komponens keletkezik. Természetesen ugyanez igaz Hamilton-kört tartalmazó gráfokra is: Egy Hamilton-kört tartalmazó gráfból tetszőlegesen elhagyva pontot legfelejbb komponens keletkezik.
Tétel: Ha egy gráfban pontot elhagyva -nál több komponens keletkezik, akkor nem tartalmazhat Hamilton-kört.
Bizonyítás: Indirekt tegyük fel, hogy van a gráfban Hamilton-kör, legyen ez és legyen az a pont, melyet elhagyva a gráf több, mint komponensre esik szét. Vegyük észre azonban, hogy az elhagyott pontok közötti „ívek” biztosan összefüggő komponenseket alkotnak. Például a ív is biztosan összefüggő lesz, hiszen két szomszédos pontja között az eredeti Hamilton-kör egy éle fut. Mivel éppen ilyen ívet kapunk, nem lehet több komponens -nál. Kevesebb lehet, hiszen különböző ívek között futhatnak élek, lásd az 1. ábrát.
Megjegyzés: Sajnos ha tetszőlegesen elhagyva a ponthalmazt a keletkező komponensek száma legfeljebb , akkor sem biztos, hogy van Hamilton-kör a gráfban. (Azaz a feltétel csak szükséges, de nem elégséges.)
- Erre példa a Petersen-gráf.
- Bizonyítás: Tegyük fel, hogy létezik a Petersen-gráfban Hamilton-kör! Ekkor létezik a gráfnak három színnel való színezése úgy, hogy minden csúcsnál minden szín pontosan egyszer fordul elő, és a színek jelentése: Hamilton-kör páratlanadik élei, párosadik élei illetve a harmadik színűek a Hamilton-körben nem szereplő élek. Ha megpróbáljuk a feltételeknek megfelelően kiszínezni a gráfot, akkor a külső körön színnek kell szerepelnie. Ebből már bizonyos élek színezése adódik a feltételek miatt. A maradék éleket pedig nem tudjuk úgy kiszínezni, hogy teljesüljön minden színezési feltétel. Tehát ellentmondásra jutunk, azaz a Petersen-gráfban nem létezik Hamilton-kör. Ebből viszont az is következik, hogy a fenti feltétel nem elégséges.
Tétel: Ha létezik a gráfban olyan pont, amelyeket elhagyva a gráf több mint komponensre esik szét, akkor a gráfban nem létezik Hamilton-út.
Bizonyítás: Indirekt tegyük fel, hogy van a gráfban Hamilton-út. Legyen ez a Hamilton-út , azaz -re illeszkedik minden csúcsa. Bármely út, így persze is darab pontjának törlése után legfeljebb részre bomlik, és ez ellentmond a fenti feltételnek, hogy legalább részre kéne esnie. Ez az ellentmondás bizonyítja az állítást.
Elégséges feltétel Hamilton-kör létezésére
szerkesztésHamilton-kör létezésére több elégséges feltételt adtak. Természetesen mindenhol egyszerű gráfról van szó, és úgy is csak akkor érdekes a kérdés, ha . Előzőleg szükséges feltételeket láthattunk. Nem ismeretes olyan jól kezelhető feltétel, ami szükséges és elégséges is.
Dirac-tétel (1952)
szerkesztésHa egy egyszerű, legalább 3 pontú gráf, amelynek minden pontjának legalább a foka, akkor tartalmaz Hamilton-kört.
Ore-tétel (1961)
szerkesztésLegyen egy olyan pontú egyszerű gráf melyben nem szomszédos pontpárra teljesül a feltétel. Ekkor -ben van Hamilton-kör.
Megjegyzés: Az Ore-tétel feltétele gyengébb, mint a Dirac-tételé, hiszen ha minden pont fokszáma legalább , akkor nem szomszédos pontpárra .
Pósa-tétel (1962)
szerkesztésLegyenek csúcsú egyszerű gráf fokszámai nagyság szerint . Ha -re , akkor -ben van Hamilton-kör.
Chvátal-tétel (1972)
szerkesztésLegyenek csúcsú egyszerű gráf fokszámai nagyság szerint .
- Ha teljesül a következő feltétel:
(+) -ra, amelyre teljesül, hogy akkor tartalmaz Hamilton-kört. - Ha olyan pozitív egész számok, amikre (+) nem teljesül, akkor létezik olyan Hamilton-kört nem tartalmazó gráf, melynek fokszámaira -re .
Hamilton-körök véletlen gráfokban
szerkesztésA 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 -ra egy n pontszámú és élszámú véletlen gráf majdnem biztosan nem összefüggő, míg egy élszámú majdnem biztosan az. Azt az állítást azonban, hogy, ha az élek száma , 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
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:
Néhány jól használható állítás Hamilton-körökkel, illetve -utakkal kapcsolatban
szerkesztés- Az csúcsú teljes gráfnak ( esetén) különböző Hamilton-köre van.
- Bizonyítás: A csúcsok lehetséges sorrendjeinek száma: . Ezek mindegyike meghatároz egy Hamilton-kört a teljes gráfban, de vannak olyanok, amelyek ugyanazt. El szeretnénk érni, hogy minden egyes Hamilton-kört pontosan egyszer számoljunk. A gráfunk bármely Hamilton-köre pontosan -szer áll így elő, hiszen egy Hamilton-kör bármely pontjából kiindulva kezdhetjük el a csúcsok felsorolását, és ezt kétféle irányban tehetjük meg. Így a különböző Hamilton-körök száma: .
- A gráf, azaz az számosságú osztályokkal rendelkező teljes páros gráf ( esetén) különböző Hamilton-köreinek száma: .
- Bizonyítás: A gráf egy-egy pontosztályába tartozó csúcsokat nevezzük „alsó”, illetve „felső” csúcsoknak. Soroljuk fel a csúcsoknak az összes olyan permutációját, mely alsó csúccsal kezdődik, és felváltva tartalmaz alsó, illetve felső csúcsokat. Az ilyen permutációk száma , hisz külön-külön a két halmazban levő pontok -féleképp permutálhatók, de a permutációkat össze kell fésülni. Ezen permutációk mindegyike egy Hamilton-kört határoz meg, de vannak olyanok, amelyek ugyanazt. Minden Hamilton-kör pontosan -szer áll így elő, hisz a Hamilton-kör darab „alsó” csúcsának mindegyikéből kétféle irányban sorolhatjuk fel a csúcsokat. Így a különböző Hamilton-körök száma: .
- Ha egy egyszerű gráfnak pontja van, és minden pont fokszáma legalább , akkor tartalmaz Hamilton-utat.
- Bizonyítás: Vegyünk hozzá a gráfhoz egy új pontot, és kössük össze az összes többi ponttal. Így kapunk egy olyan gráfot, amelynek pontja van, és minden pont foka legalább , hiszen az eredeti pontok fokszáma az új pont miatt eggyel nő, az új pont fokszáma pedig . Ez a gráf Dirac tétele miatt tartalmaz Hamilton-kört. Ebből a Hamilton-körből az új pontot elhagyva az eredeti gráf egy Hamilton-útjához jutunk.
- Ha egy csúcsú egyszerű gráf kielégíti az Ore-tétel feltételeit, akkor bármely két pont távolsága legfeljebb kettő. (Két pont távolságán a köztük levő legrövidebb út éleinek számát értjük. Ha nincsenek összekötve, akkor egymástól való távolságuk végtelen.)
- Bizonyítás: Ha két pont szomszédos, akkor távolságuk egy. Ha (Ore-tétel). Az és csúcsokból kiinduló élek csak a többi csúcs valamelyikénél végződnek, ezért van köztük két olyan él, amelyik közös csúcsnál végződik. Mivel egyszerű gráf, azaz nem tartalmaz párhuzamos éleket, az előbbiek közül az egyik szükségszerűen -nél, a másik -nál kezdődik. Ezzel beláttuk, hogy -nek és -nak van közös szomszédja, azaz távolságuk kettő.
- Ha egy pontú egyszerű gráf kielégíti az Ore-feltételt, akkor a pontok legalább fele olyan, hogy a fokszáma legalább .
- Bizonyítás: Legyen az -nél kisebb fokú pontok halmaza , a többi csúcs halmaza pedig . Tegyük fel indirekt, hogy . Az Ore-feltétel miatt -ben bármely két csúcs szomszédos egymással. Az előző állítás miatt összefüggő, ezért létezik olyan pont, ahonnan vezet él valamely -beli pontba. (A nem lehet üres, hisz ha minden pont -beli lenne, akkor a pontok foka lenne, ami ellentmond választásának.) A pont így az összes -beli ponttal, és még legalább egy -beli ponttal szomszédos, ezért . Ez viszont ellentmondás, hiszen az -nél kisebb fokszámú pontok közül való.
- Ha egy pontú egyszerű gráf kielégíti a Pósa-tételben szereplő feltételt, akkor a pontok több mint felének a fokszáma legalább .
- Bizonyítás: A fokszámok növekvő sorozata legyen . Jelölje azt a legnagyobb egész számot, amely még kisebb -nél, azaz . Pósa feltétele miatt , ami legalább . A -nál nem kisebb fokú pontok száma legalább , és így az állítást beláttuk.
- Ha egy pontú egyszerű gráf kielégíti az Chvátal-tételbeli feltételt, akkor a pontok legalább fele olyan, hogy a fokszáma legalább .
- Bizonyítás: A fokszámok növekvő sorozata legyen . Jelölje azt a legnagyobb egész számot, amely még kisebb -nél, azaz . A Chvátal-tételbeli feltétel miatt vagy teljesül. A választásából adódóan és is fennáll, és mivel , ezért biztosan teljesül. A legalább fokú pontok száma legalább .
- Ha egy pontú egyszerű gráf kielégíti a Pósa-tételbeli feltételt, akkor összefüggő.
- Bizonyítás: Tegyük fel indirekt, hogy egy egyszerű gráf kielégíti a feltételt, de nem összefüggő. Ekkor van -nek olyan komponense, amelyben a csúcsok száma nem több -nél. Mivel egyszerű, ezért ebben a komponensben az összes csúcs fokszáma kisebb -nél. A kettővel korábbi állítás miatt az összes -nél kisebb fokszámú csúcs a fokszámokból alkotott sorozat első feléből való, ezért teljesülnie kell rájuk a egyenlőtlenségnek. Ha ez a komponens összes csúcsára teljesül, akkor a csúcsok között van olyan, amelyiknek a fokszáma nagyobb, mint a komponens csúcsainak száma. Ez ellentmondás, hisz feltettük, hogy egyszerű.
- Ha egy gráfban van Euler-kör, akkor -nek az élgráfjában van Hamilton-kör.
- Bizonyítás: Ha az Euler-kör szerinti sorrendben vesszük csúcsait, akkor egy Hamilton-kört kapunk.
- Minden turnamentben van irányított Hamilton-út. (Rédei László, 1934)
- Bizonyítás: Legyen egy turnament és ebben legyen egy maximális hosszúságú irányított út, melyben az irányítás mentén a pontok követik egymást. Indirekt tegyük fel, hogy nem Hamilton-út, azaz van olyan pont, amelyik nincs rajta -n. Az indoklás kulcsa az az észrevétel, hogy ha a és közti él felé irányított, ahol , hiszen különben a egy -nél hosszabb irányított út lenne. Szintén maximalitásából adódik, hogy az út összes pontjából felé mutat. Innen az észrevétel felhasználásával adódik, hogy az út összes pontjából felé mutatnak az élek. Mivel ez teljesül az utolsó pontra is, a egy -nél hosszabb irányított út, ami ellentmondás. Ez az ellentmondás bizonyítja az állítást.
- Rédei bebizonyította azt az erősebb állítást is, hogy minden turnamentben páratlan sok Hamilton-út van.
- Egy turnamentben pontosan akkor van irányított Hamilton-kör, ha a turnament erősen összefüggő.
Sejtések
szerkesztésA Hamilton-körhöz kapcsolódó fontos sejtések:
- D. W. Barnette (1969): Minden 3-összefüggő, 3-reguláris páros gráfban van Hamilton-kör.
- P. Seymour (1974): Ha G-ben a minimális fokszám , akkor G tartalmaz H Hamilton-kört, hogy .
Egy alkalmazás
szerkesztésA magasabb dimenziós (hiper)kockagráfok Hamilton-köreinek a csúcsokhoz írt standard címkéikkel együtt egy egyszerű (és gyors) konstrukciót ad Gray-kódok megkeresésére, amiket a Karnaugh-Veitch módszerben használnak logikai (Boole-) függvények egyszerűsítésekor.
Források
szerkesztés- The Hamilton page
- Sir William Rowan Hamilton
- Hajnal Péter: Gráfelmélet, Polygon, Szeged, 2003.
- Katona–Recski–Szabó: A számítástudomány alapjai, Typotex, Budapest, 2003.
- Friedl–Recski–Simonyi: Gráfelméleti feladatok, Typotex, Budapest, 2006.