3. Hamilton-körök és -utak
Alapfogalmak
A $G$ gráf egy $P$ sétáját Euler-sétának nevezzük, ha az $G$ minden élét tartalmazza (pontosan egyszer).
Ha $P$ ráadásul körséta, akkor $P$-t Euler-körsétának (vagy Euler-körnek) mondjuk.
Vizuális különbség
Míg egy egyszerű kör csak a csúcsok egy részét érinti, az Euler-körnek a gráf összes élén át kell haladnia.
Minden él bejárható egyetlen vonallal.
A belső él kimarad, így ez nem Euler-körséta.
Az Euler-tétel
Legyen $G$ összefüggő gráf. Ekkor:
- $G$-ben akkor és csak akkor van Euler-körséta, ha $G$ minden csúcsának a foka páros;
- $G$-ben akkor és csak akkor van Euler-séta, ha $G$-nek legföljebb két páratlan fokú csúcsa van.
Ha $G$ tartalmaz hurokélt, azokat töröljük: ezzel sem a csúcsok fokszámának paritását nem változtatjuk meg, sem az Euler-vonal létezését (hiszen a hurokél bármikor beszúrható a sétába az adott csúcsnál).
A „csak akkor” irány (szükségesség):
Ha van $P$ Euler-séta, amely nem a $v$ csúcsból indul és nem oda érkezik, akkor $v$ foka páros, mert a $v$-n való áthaladások párosával fogyasztják a $v$-re illeszkedő éleket.
Ugyanez igaz az Euler-körséta kezdő- és végpontjára ($u$) is: az induláskor felhasznált él és a megérkezéskor használt utolsó él párba rendeződik, a közbülső áthaladásokkal együtt így $u$ foka is páros lesz.
Az „akkor” irány (elégségesség):
A bizonyításhoz egy algoritmust adunk meg, amely minden páros fokszámú, összefüggő gráfban megad egy Euler-körsétát. Az eljárás lényege az „Increasing step” (növelő lépés), amely a körséta hosszát növeli.
A módszer kulcsa: Egy $v$ csúcsból indulva „vaktában, elakadásig sétálunk”. Ez azt jelenti, hogy mindig egy olyan, még nem használt élen lépünk tovább, amely még nem szerepelt a sétánkban.
Miért kell páros fokszám?
Minden alkalommal, amikor áthaladsz egy csúcson, két élt használsz el: egyet a belépéshez és egyet a kilépéshez.
Belépő él (1) + Kilépő él (1) = 2 él (Páros egység)
Lemma a vaktában sétáláshoz
Tegyük fel, hogy a $H$ gráfban minden csúcs foka páros és legyen $v \in V(H)$ tetszőleges csúcs. Ha $v$-ből indulva vaktában, elakadásig sétálunk, akkor az így kapott $Q$ séta végpontja szintén $v$.
A bizonyításhoz vegyük észre, hogy a $Q$ séta párosával fogyasztja az általa érintett, $v$-től különböző csúcsok éleit; vagyis egy csúcson való minden áthaladása kettőt használ fel az arra illeszkedő élek közül.
Ha a séta éppen egy $x \neq v$ csúcsnál tart, akkor $x$ élei közül korábban páros sokat használt fel (pontosan kétszer annyit, mint ahányszor eddig $x$-en áthaladt) és még egyet most, amikor $x$-be legutóbb megérkezett.
Így $x$-nél összesen páratlan sokat használtunk fel.
Mivel azonban $x$ eredeti foka páros, ezért a rá illeszkedő élek között kell legyen olyan is, amit a $Q$ séta még nem tartalmaz.
Ebből következik, hogy $Q$ valóban nem akadhat el $x$-ben, tehát csak $v$-ben érhet véget.
Az elakadás elkerülése
Figyeld meg a paritást: a belépéshez mindig tartoznia kell egy kilépésnek.
Élek száma: Páratlan
Élek száma: Páros
Euler-körséta kereső algoritmus
Bemenet: Egy összefüggő $G = (V,E)$ gráf, amiben minden csúcs foka páros.
$u \in V$ legyen tetszőleges csúcs
$P \leftarrow (u)$ (egy csúcsú, nulla hosszúságú séta); $v \leftarrow u$
ciklus:
SÉTÁLJUNK VAKTÁBAN, ELAKADÁSIG $v$-ből indulva a $P$-be nem tartozó élek által alkotott gráfban; a kapott séta: $Q$
$P$-ben $v$ egy előfordulásának a helyére szúrjuk be $Q$-t
ha $P$ tartalmazza $G$ minden élét, akkor: stop
$v$ legyen olyan csúcs, amire illeszkedik $P$-béli és nem $P$-béli él is
ciklus vége
Hogyan működik a beszúrás?
Az algoritmus lényege, hogy a már meglévő $P$ körbe újabb és újabb $Q$ köröket "varrunk bele" a közös $v$ csúcsok mentén. Ez garantálja, hogy a végén egyetlen összefüggő vonallal minden élet érintünk.
Interaktív szimuláció
Gráfépítő felület
Kattints a vászonra csúcsokért, kösd össze őket élekért!
Algoritmus napló
Kidolgozott feladat: Euler-vonalak vizsgálata
a) Tartalmaz-e az alábbi $G$ gráf Euler-sétát, illetve Euler-körsétát? Ha a válasz igen, akkor adjunk meg egyet!
b) Adjuk hozzá a gráfhoz a $\{p,x\}$ élet és oldjuk meg a feladatot az így kapott gráfra is!
A vizsgált gráf ($G$)
A kék szaggatott vonal jelöli a b) részben hozzáadott $\{p, x\}$ élet.
Megoldás
a) rész: Alapállapot elemzése
A gráfban a $p$ és $u$ csúcsok foka 3, az összes többi csúcs foka páros. Mivel vannak páratlan fokú csúcsok, a gráf nem tartalmaz Euler-körsétát. Továbbá a gráf két külön komponenst alkot, így Euler-sétát sem tartalmaz.
b) rész: A $\{p, x\}$ él hozzáadása után
Az új éllel a gráf összefüggővé válik. $p$ foka páros (4), $x$ foka páratlan (3) lesz. Mivel pontosan két páratlan fokú csúcs marad ($x$ és $u$), a gráfban létezik Euler-séta.
Kidolgozott feladat: Salsa és az Euler-vonalak
Feladat
Összefüggőség vizualizálása
A bizonyítás kulcsa: Ha egy komponens tartalmaz egy fiút, akkor tartalmaznia kell mind a 6 lányismerősét is, azoknak pedig mind a 6 fiúismerősüket.
Megoldás levezetése
Alkossák a résztvevők a $G$ gráf csúcshalmazát. Két csúcs akkor szomszédos, ha a táncosok ellenkező neműek és ismerik egymást. A feladat állítása ekvivalens azzal, hogy létezik-e a gráfban Euler-vonal.
Mindenki pontosan 6 ismerőst jelölt meg, így minden csúcs foka 6. Mivel a 6 páros szám, ez a feltétel teljesül.
Legyen $K$ egy komponens. Ha $K$ tartalmaz egy fiút, akkor annak 6 lányismerősét is tartalmaznia kell, azoknak pedig mind a 6 fiúismerősüket.
Mivel $G$ összefüggő és minden csúcsának foka páros, a 3.2. Tétel szerint létezik benne Euler-körséta, tehát a cél megvalósítható.
Hamilton-út és Hamilton-kör
A $G$ gráf egy $C$ körét Hamilton-körnek nevezzük, ha $C$ a $G$ minden csúcsát tartalmazza.
Hasonlóan, egy $P$ utat Hamilton-útnak nevezünk $G$-ben, ha $P$ a $G$ minden csúcsát tartalmazza.
Vizuális különbségtétel
Míg az Euler-vonalaknál az élek összeszámolása a cél, a Hamilton-vonalaknál minden csúcson kell pontosan egyszer áthaladnunk.
Minden csúcsot érint, de nem minden élet.
Zárt hurok, ami minden csúcson átmegy.
Hamilton-vonalak vizsgálata feladatokon keresztül
Feladat
a) Van-e Hamilton-kör, illetve Hamilton-út az alábbi $G$ gráfban?
b) Töröljük $G$-ből a $\{c,g\}$ élet és oldjuk meg a feladatot az így kapott gráfra is!
(c, a, f, d, e, b, h, g, c)
Az "e" csúcs törlése után a gráf szétesik: {a,c,d,f} és {b,g,h} komponensekre.
Részletes levezetés
a) rész: Némi kísérletezés után találhatunk $G$-ben Hamilton-kört. Például a csúcsokat az alábbi sorrendben járva be: (c, a, f, d, e, b, h, g, c). Mivel van Hamilton-kör, és bármely élét elhagyva Hamilton-utat kapunk, a gráf Hamilton-utat is tartalmaz.
b) rész: A {c, g} él elhagyása után
A $\{c,g\}$ él törlésével kapott gráf továbbra is tartalmaz Hamilton-utat (mivel a fenti körből ezt az élet elhagyva éppen egy Hamilton-utat kapunk).
Hamilton-kört azonban ez a gráf már nem tartalmaz!
Ennek igazolásához használjuk a 3.7-es tétel ötletét: ha töröljük a gráfból az e csúcsot, a maradék gráf már nem összefüggő: az $\{a, c, d, f\}$ és a $\{b, g, h\}$ csúcsok két külön komponenst alkotnak.
Mivel egyetlen csúcs ($k=1$) törlésével több komponens ($2$) keletkezett, a gráfban nem lehet Hamilton-kör.
Szükséges feltétel Hamilton-vonalakra
Legyen $G$ tetszőleges gráf és $k \geq 1$ egész szám.
- Ha $G$-ben van Hamilton-kör, akkor $G$-ből bárhogyan $k$ csúcsot törölve a kapott gráf komponenseinek száma legföljebb $k$.
- Ha $G$-ben van Hamilton-út, akkor $G$-ből bárhogyan $k$ csúcsot törölve a kapott gráf komponenseinek száma legföljebb $k+1$.
Bizonyítás
(i) eset bizonyítása: Legyen $C$ egy Hamilton-kör $G$-ben, és töröljünk $G$-ből $k$ tetszőleges csúcsot. Ekkor a törölt csúcsok a $C$ kört legföljebb $k$ ívre (szakszra) bontják.
Ebből következik, hogy $G'$ komponenseinek száma nem lehet több az ívek számánál, vagyis $k$-nál.
(ii) eset bizonyítása: Egy Hamilton-utat $k$ csúcs törlése legföljebb $k+1$ szakaszra bont. Mivel egy szakaszon belül a csúcsok összefüggőek maradnak, a gráf nem eshet szét $(k+1)$-nél több komponensre.
Komponensek és vágások
Képzeld el a Hamilton-kört egy láncként. Ha $k$ helyen elvágod (törölsz egy szemet), legfeljebb $k$ darab összefüggő láncdarabot kapsz.
A tétel segít cáfolni a Hamiltonicity-t: ha találsz $k$ csúcsot, aminek törlése >$k$ komponenst ad, nincs Hamilton-kör.
Lólépés bejárás vizsgálata
Feladat
Bejárható-e egy $3 \times 5$-ös sakktábla lóval úgy, hogy közben minden mezőre pontosan egyszer lépünk rá?
Logikai levezetés
A kérdés gráfelméleti megfogalmazása: Van-e Hamilton-út a $3 \times 5$-ös lólépés-gráfban?
Alkalmazzuk a 3.6-os Tétel (ii) állítását: töröljünk ki $k=5$ alkalmasan választott csúcsot a gráfból (a vizualizáción piros X-szel jelölt mezők).
A törlés után a megmaradó gráf 7 összefüggő komponensre esik szét:
- Egy 4 csúcsból álló kör (a kék élek mentén);
- 6 darab izolált pont (mező).
Az ellentmondás:
A 3.6-os tétel szerint, ha létezner Hamilton-út, akkor $k=5$ csúcs elhagyása után legföljebb k + 1 = 6 komponens maradhatna. Mivel mi 7 komponenst kaptunk, a gráfban nem létezhet Hamilton-út.
Dirac-tétel: Elégséges feltétel Hamilton-körre
Ha az $n \geq 3$ csúcsú $G$ egyszerű gráfban minden csúcs foka legalább $\frac{n}{2}$, akkor $G$-ben van Hamilton-kör.
Bizonyítási alapelv
A tétel bizonyításának kiindulópontja az a megfigyelés, hogy ha $G$-ben minden csúcs foka legalább $\frac{n}{2}$, akkor bármely nemszomszédos $\{u,v\}$ csúcspárra a fokszámok összege legalább $n$:
Ez az összefüggés biztosítja, hogy a gráf "elég sűrű" ahhoz, hogy ne lehessenek benne olyan elszigetelt részek, amelyek megakadályoznák egy minden csúcsot érintő kör kialakulását.
A feltétel vizualizálása ($n=6$)
Ha $n=6$, akkor minden csúcsnak legalább 3 szomszédja kell legyen ($d \geq 3$).
Megjegyzés: A Dirac-feltétel elégséges, de nem szükséges. Egy körgráf ($C_n$) esetén minden fok 2, ami kisebb mint $n/2$, mégis van benne Hamilton-kör.
Ore tétele és a bizonyítási eljárás
Tegyük fel, hogy az $n \geq 3$ csúcsú $G$ egyszerű gráfra teljesül: minden $u, v \in V(G), \{u, v\} \notin E(G)$ esetén $d(u) + d(v) \geq n$. Ekkor $G$-ben van **Hamilton-kör**.
A bizonyítási eljárás menete
Az eljárás során végig karbantartjuk a csúcsok egy $\pi = (v_1, v_2, \dots, v_n)$ sorrendjét (permutációját). Jelölje $e(\pi)$ azon $\{v_i, v_{i+1}\}$ és $\{v_n, v_1\}$ párok számát, amik szomszédosak $G$-ben. Ha $e(\pi) = n$, akkor a $\pi$ által kijelölt sorrendben bejárva a csúcsokat Hamilton-kört kapunk.
A növelő lépés: e(π) növelése
Tegyük fel, hogy $e(\pi) < n$, azaz a sorrend még nem Hamilton-kör. Feltehetjük, hogy $\{v_n, v_1\} \notin E(G)$ (szükség esetén a csúcsok indexeit „eltoljuk” a kör mentén).
Keressünk egy olyan $k$ indexet, amire $\{v_k, v_n\} \in E(G)$ és $\{v_1, v_{k+1}\} \in E(G)$ egyszerre teljesülnek.
Új permutáció ($\pi'$):
$(v_1, v_2, \dots, v_k, v_n, v_{n-1}, \dots, v_{k+1})$
Az 5.4a ábra mutatja, hogy $\pi$-ről $\pi'$-re áttérve a sorrendben egymást követő csúcspárok listája csak két helyen változik: a $\{v_1, v_n\}$ és $\{v_k, v_{k+1}\}$ párok helyett a $\{v_1, v_{k+1}\}$ és $\{v_k, v_n\}$ párok lépnek be. Ezzel $e(\pi')$ legalább 1-gyel nagyobb lesz $e(\pi)$-nél.
Létezik-e mindig ilyen k? (Skatulya-elv)
Fessük zöldre $v_n$ összes szomszédját, és kékkel az összes olyan csúcsot, ami $v_1$ valamelyik szomszédját a $\pi$ sorrendben eggyel megelőzi.
Zöld csúcsok száma: $d(v_n)$
Kék csúcsok száma: $d(v_1)$
Mivel $\{v_1, v_n\} \notin E(G)$, a tétel feltétele szerint $d(v_1) + d(v_n) \geq n$. A kék és zöld színt kapott csúcsok száma együtt legalább $n$.
Mivel azonban legföljebb $n-1$ csúcs közül választhatunk (hiszen $v_n$ nem lehet sem kék, sem zöld), a skatulya-elv miatt kell lennie olyan $v_k$ csúcsnak, ami mindkét színt megkapta.
Alkalmazás: Az ötöslottó gráfmodellje
5.7. Feladat
Mutassuk meg, hogy ha az összes lehetséges ötöslottó-szelvényt kitöltenénk, akkor azok elrendezhetők lennének egy sorban úgy, hogy az egymás mellé kerülő szelvényeken soha ne legyen közös szám!
Modellezés és Bizonyítás
A feladatot átfogalmazzuk gráfelméleti állítássá: a $G$ gráf csúcsai legyenek a lehetséges lottószelvények, és két csúcs akkor legyen szomszédos, ha a megfelelő szelvényeken nincs közös szám. A feladat célja annak igazolása, hogy $G$-ben van Hamilton-út.
Csúcsok száma ($n$):
Az összes 5 elemű részhalmaz száma.
Tetszőleges $v$ csúcs foka ($d(v)$):
Ennyiféleképpen választható 5 szám a szelvényen nem szereplő 85-ből.
Dirac-tétel feltételének ellenőrzése
Látható, hogy $d(v) \geq \frac{n}{2}$ minden csúcsra teljesül. Mivel $G$ egyszerű gráf, Dirac tétele szerint $G$-ben van Hamilton-kör (és így Hamilton-út is).
Fejezeti összefoglaló: Euler vs. Hamilton
| Tulajdonság | Euler-vonalak | Hamilton-vonalak |
|---|---|---|
| Fókusz | Minden **él** | Minden **csúcs** |
| Fő feltétel | Fokszám-paritás | Gráfsűrűség ($d \ge n/2$) |
| Algoritmus | Hierholzer | Permutáció-javítás |
Hamilton-út Tervező: A Csúcsok Bejárása
Szabályok
- Kezdj egy tetszőleges csúccsal!
- Minden pontot pontosan egyszer érints.
- Csak szomszédos pontra léphetsz.
Összefoglaló Kvíz
Készen állsz a vizsgára?
Vidd az egeret a kártyák fölé a válaszokért!
#01 Euler-körséta
Milyen feltételnek kell teljesülnie a fokszámokra, hogy egy összefüggő gráfban legyen Euler-kör?
#02 Hamilton vs Euler
Mi a fő különbség a Hamilton-kör és az Euler-kör között?
#03 Hamilton szükségesség
Ha egy gráfból törlünk $k$ csúcsot, és a maradék több mint $k$ komponensre esik szét, lehet-e benne Hamilton-kör?
#04 Dirac-tétel
Mi az elégséges fokszám-feltétel Dirac tétele szerint a Hamilton-kör létezéséhez?
Tudtad-e?
A gráfelmélet születése
Tudtad, hogy a gráfelmélet egy polgári séta dilemmájával kezdődött? Leonhard Euler 1736-ban bizonyította be, hogy a hét königsbergi hídon nem lehet úgy végigmenni, hogy minden hídon pontosan egyszer haladjunk át. Ez volt a történelem első Euler-vonala.
Biológia és Euler-út
A modern genetika Euler-utakat használ a DNS-szekvenciák összerakásához. A rövid DNS-darabkákat egy gráf éleiként kezelik, és a teljes lánc rekonstrukciója valójában egy Euler-út megkeresése ebben a hatalmas hálózatban.
Hamilton „bukott” játéka
Sir William Rowan Hamilton 1857-ben egy dodekaéder élei mentén játszható logikai játékot dobott piacra. Bár a játék anyagilag bukás volt, a gráfelméletben örökre megmaradt a neve a Hamilton-kör fogalmában.
Miért nehéz a logisztika?
Míg egy Euler-kört találni könnyű, a legrövidebb Hamilton-kör megtalálása (TSP) a számítástudomány egyik legnehezebb feladata. Nincs rá olyan algoritmus, ami minden esetben gyorsan megoldaná, pedig ezen alapul a globális csomagszállítás.