Hamilton-kör

gráfelméleti fogalom
Ez a közzétett változat, ellenőrizve: 2024. július 24.

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.

Három példa egy 8x8 rácsgráfra

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és

Hosszú 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és

Ha   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.

 
1. ábra

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és

Hamilton-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és

Ha   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és

Legyen   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és

Legyenek     csúcsú egyszerű gráf fokszámai nagyság szerint  . Ha  -re  , akkor   -ben van Hamilton-kör.

Chvátal-tétel (1972)

szerkesztés

Legyenek     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és

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  -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.
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ő.

A 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és

A 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.

  • 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.