Hamilton-kör

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

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

• 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 $n\geq 3\$ esetén minden $n\$ 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ő $n\$ 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 $n\$ összköltséggel meg tud látogatni minden várost.

Alapkérdések

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

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.

Tétel: Ha egy gráfban $k\$ pontot elhagyva $k\$-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 $(v_{1},v_{2},\ldots ,v_{n})$ és legyen $v_{i_{1}},v_{i_{2}},\ldots ,v_{i_{k}}$ az a $k\$ pont, melyet elhagyva a gráf több, mint $k\$ 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_{i_{1}+1},v_{i_{1}+2},\ldots ,v_{i_{2}-1})$ í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 $k\$ ilyen ívet kapunk, nem lehet több komponens $k\$-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 $K\$ ponthalmazt a keletkező komponensek száma legfeljebb $|K|\$, 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 $2*2+1\$ 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 $k\$ olyan pont, amelyeket elhagyva a gráf több mint $k+1\$ 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 $L\$, azaz $L\$-re illeszkedik $G\$ minden csúcsa. Bármely út, így persze $L\$ is $k\$ darab pontjának törlése után legfeljebb $k+1\$ részre bomlik, és ez ellentmond a fenti feltételnek, hogy legalább $k+2\$ 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

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 $n\geq 3$. 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)

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.

Ore-tétel (1961)

Legyen $G\$ egy olyan $n\geq 3$ pontú egyszerű gráf melyben $\forall x,y\in V(G)$ nem szomszédos pontpárra teljesül a $d(x)+d(y)\geq n$ feltétel. Ekkor $G\$-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 ${\frac {|V(G)|}{2}}$, akkor $\forall x,y\$ nem szomszédos pontpárra $d(x)+d(y)\geq n$.

Pósa-tétel (1962)

Legyenek $G\$ $n\$ csúcsú egyszerű gráf fokszámai nagyság szerint $d_{1}\leq d_{2}\leq ...\leq d_{n}$. Ha $\forall k<{\frac {n}{2}}$-re $d_{k}\geq k+1$, akkor $G\$ -ben van Hamilton-kör.

Chvátal-tétel (1972)

Legyenek $G\$ $n\$ csúcsú egyszerű gráf fokszámai nagyság szerint $d_{1}\leq d_{2}\leq ...\leq d_{n}$.

• Ha teljesül a következő feltétel: (+) $\forall k$-ra, amelyre $d_{k}\leq k<{\frac {n}{2}}$ teljesül, hogy $d_{n-k}\geq n-k$ akkor $G\$ tartalmaz Hamilton-kört.
• Ha $d_{1}\leq d_{2}\leq ...\leq d_{n}$ olyan pozitív egész számok, amikre (+) nem teljesül, akkor létezik olyan Hamilton-kört nem tartalmazó $G\$ gráf, melynek $d_{1}^{'}\leq d_{2}^{'}\leq ...\leq d_{n}^{'}$ fokszámaira $\forall i$-re $d_{i}^{'}\geq d_{i}$.

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 $\epsilon >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 $cn\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.

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

${\frac {1}{2}}n\log n+{\frac {1}{2}}n\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}}.$

Néhány jól használható állítás Hamilton-körökkel, illetve -utakkal kapcsolatban

• Az $n\$ csúcsú teljes gráfnak ($n\geq 3$ esetén) ${\frac {(n-1)!}{2}}$ különböző Hamilton-köre van.

Bizonyítás: A csúcsok lehetséges sorrendjeinek száma: $n!\$. 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 $2n\$-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: ${\frac {n!}{2n}}={\frac {(n-1)!}{2}}$.

• A $K_{n,n}\$ gráf, azaz az $n$ számosságú osztályokkal rendelkező teljes páros gráf ($n\geq 2$ esetén) különböző Hamilton-köreinek száma: ${\frac {(n!)^{2}}{2n}}$.

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 $(n!)^{2}\$, hisz külön-külön a két halmazban levő pontok $n!\$-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 $2n\$-szer áll így elő, hisz a Hamilton-kör $n\$ 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: ${\frac {(n!)^{2}}{2n}}$.

• Ha egy egyszerű gráfnak $2n+1\$ pontja van, és minden pont fokszáma legalább $n\$, 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 $2n+2\$ pontja van, és minden pont foka legalább $n+1\$, hiszen az eredeti pontok fokszáma az új pont miatt eggyel nő, az új pont fokszáma pedig $2n+1\$. 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 $n\$ csúcsú egyszerű $G\$ 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 $x,y\in V(G),\{x,y\}\notin E(G)\Rightarrow d(x)+d(y)\geq n$ (Ore-tétel). Az $x\$ és $y\$ csúcsokból kiinduló élek csak a többi $n-2\$ 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 $G\$ egyszerű gráf, azaz nem tartalmaz párhuzamos éleket, az előbbiek közül az egyik szükségszerűen $x\$-nél, a másik $y\$-nál kezdődik. Ezzel beláttuk, hogy $x\$-nek és $y\$-nak van közös szomszédja, azaz távolságuk kettő.

• Ha egy $G\$ $n\$ pontú egyszerű gráf kielégíti az Ore-feltételt, akkor a pontok legalább fele olyan, hogy a fokszáma legalább ${\frac {n}{2}}\$.

Bizonyítás: Legyen az ${\frac {n}{2}}\$-nél kisebb fokú pontok halmaza $V_{1}\$, a többi csúcs halmaza pedig $V_{2}\$. Tegyük fel indirekt, hogy $|V_{1}|>|V_{2}|\$. Az Ore-feltétel miatt $V_{1}\$-ben bármely két csúcs szomszédos egymással. Az előző állítás miatt $G\$ összefüggő, ezért létezik olyan $v\in V_{1}\$ pont, ahonnan vezet él valamely $V_{2}\$-beli pontba. (A $V_{2}\$ nem lehet üres, hisz ha minden pont $V_{1}\$-beli lenne, akkor a pontok foka $|V_{1}|-1=n-1\$ lenne, ami ellentmond $V_{1}\$ választásának.) A $v\$ pont így az összes $V_{1}\$-beli ponttal, és még legalább egy $V_{2}\$-beli ponttal szomszédos, ezért $d(v)\geq |V_{1}|\geq {\frac {n}{2}}\$. Ez viszont ellentmondás, hiszen $v\in V_{1}\$ az ${\frac {n}{2}}\$-nél kisebb fokszámú pontok közül való.

• Ha egy $n\$ pontú egyszerű $G\$ 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 ${\frac {n}{2}}\$.

Bizonyítás: A fokszámok növekvő sorozata legyen $d_{1}\leq d_{2}\leq \ \ldots \leq d_{n}$. Jelölje $k\$ azt a legnagyobb egész számot, amely még kisebb ${\frac {n}{2}}\$-nél, azaz $k=\left[{\frac {(n-1)}{2}}\right]$. Pósa feltétele miatt $d_{k}\geq k+1\$, ami legalább ${\frac {n}{2}}\$. A $d_{k}\$-nál nem kisebb fokú pontok száma legalább $n-k+1>{\frac {n}{2}}\$, és így az állítást beláttuk.

• Ha egy $G\$ $n\$ 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 ${\frac {n}{2}}\$.

Bizonyítás: A fokszámok növekvő sorozata legyen $d_{1}\leq d_{2}\leq \ \ldots \leq d_{n}$. Jelölje $k\$ azt a legnagyobb egész számot, amely még kisebb ${\frac {n}{2}}$-nél, azaz $k=\left[{\frac {(n-1)}{2}}\right]$. A Chvátal-tételbeli feltétel miatt $d_{k}\geq k+1\$ vagy $d_{n-k}\geq n-k\$ teljesül. A $k\$ választásából adódóan $k+1\geq {\frac {n}{2}}\$ és $n-k\geq {\frac {n}{2}}\$ is fennáll, és mivel $d_{n-k}\geq d_{k}\$, ezért $d_{n-k}\geq {\frac {n}{2}}\$ biztosan teljesül. A legalább $d_{n-k}\$ fokú pontok száma legalább $k+1\geq {\frac {n}{2}}\$.

• Ha egy $n\$ pontú egyszerű $G\$ gráf kielégíti a Pósa-tételbeli feltételt, akkor összefüggő.

Bizonyítás: Tegyük fel indirekt, hogy egy $G\$ egyszerű gráf kielégíti a feltételt, de nem összefüggő. Ekkor van $G\$-nek olyan komponense, amelyben a csúcsok száma nem több ${\frac {n}{2}}\$-nél. Mivel $G\$ egyszerű, ezért ebben a komponensben az összes csúcs fokszáma kisebb ${\frac {n}{2}}\$-nél. A kettővel korábbi állítás miatt az összes ${\frac {n}{2}}\$-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 $d_{i}>i\$ 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 $G\$ egyszerű.

• Ha egy $G\$ gráfban van Euler-kör, akkor $G$-nek az $L(G)\$ élgráfjában van Hamilton-kör.

Bizonyítás: Ha az Euler-kör szerinti sorrendben vesszük $L(G)\$ 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 $G\$ egy turnament és ebben legyen $P\$ egy maximális hosszúságú irányított út, melyben az irányítás mentén a $v_{1},v_{2},\ldots ,v_{k}\$ pontok követik egymást. Indirekt tegyük fel, hogy $P\$ nem Hamilton-út, azaz van olyan $w\$ pont, amelyik nincs rajta $P\$-n. Az indoklás kulcsa az az észrevétel, hogy ha a $v_{j}\$ és $w\$ közti él $w\$ felé irányított, ahol $j=1,2,\ldots ,k-1\$, hiszen különben a $v_{1},v_{2},\ldots ,v_{j},w,v_{j+1},\ldots ,v_{k}\$ egy $P\$-nél hosszabb irányított út lenne. Szintén $P\$ maximalitásából adódik, hogy az út összes pontjából $w\$ felé mutat. Innen az észrevétel felhasználásával adódik, hogy az út összes pontjából $w\$ felé mutatnak az élek. Mivel ez teljesül az utolsó pontra is, a $v_{1},v_{2},\ldots ,v_{k},w\$ egy $P\$-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

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 $\delta (G)\geq {\frac {k}{k+1}}n$, akkor G tartalmaz H Hamilton-kört, hogy $H^{k}\subseteq G$.

Egy alkalmazá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.

Források

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