Euler-kör

Lehet-e olyan sétát tenni a 18. századi Königsbergben, amely minden hídon pontosan egyszer megy át és ugyanoda érkezünk, ahonnan elindultunk? Leonhard Euler megmutatta, hogy nem. Ez a gráfelmélet egyik fontos kérdése: van-e olyan kör-séta a gráfban, amely minden élet pontosan egyszer érint?

A königsbergi hidak problémája gráffal ábrázolva

Euler-út és Euler-kör

Az Euler-kör a gráfelmélet speciális sétáinak egyike.

Leonhard Euler néhány évig a Königsbergi Egyetemen dolgozott. Ezen idő alatt tették fel neki a város lakói azt a kérdést, hogy miért nem tudnak úgy átmenni a város hídjain, hogy mindegyiken pontosan egyszer haladnak át. Erre az a válasz, hogy a város hídjaiból mint élekből képzett gráf nem tartalmaz Euler-kört, sőt Euler-utat sem.

Definíció: A $G$ gráf Euler-köre olyan zárt élsorozat, mely $G$ összes élét pontosan egyszer tartalmazza. Euler-útról akkor beszélünk, hogyha az élsorozat nem feltétlenül zárt.

Megjegyzés: Minden Euler-kör egyben Euler-út is.

Megjegyzés: A gráfelméletben értelmezett kör és út egy ponton nem halad át többször, ezért pontosabb lenne az Euler-vonal és az Euler-séta elnevezés (a vonalnál, illetve a sétánál már megengedett az egy ponton történő többszöri áthaladás), de az irodalom egy része az Euler-út és az Euler-kör elnevezést használja, ennek megfelelően szerepel ebben a szócikkben is.

Az Euler-kört tartalmazó gráfokat Euler-gráfnak nevezik.

Szükséges és elégséges feltétel Euler-kör létezésére

Egy összefüggő $G$ gráfban akkor és csak akkor létezik Euler-kör, ha minden csúcsának fokszáma páros.

Bizonyítás:

Először azt látjuk be, hogy ha a gráf tartalmaz Euler-kört, akkor minden csúcs foka páros. Ha elindulunk a gráf egyik pontjából, és körbejárjuk az Euler-köre mentén, akkor minden pontba pontosan annyiszor megyünk be, ahányszor kimegyünk belőle. A bemenések és kimenések számának összege nyilvánvalóan páros, és ez egyben minden csúcsnál a fokszámot adja. Most azt bizonyítjuk, hogy ha minden pont foka páros, akkor valóban tartalmaz Euler-kört. Ezt a $G$ pontszámára vonatkozó teljes indukcióval bizonyítjuk. A legkisebb pontszámú olyan gráf, melynek minden fokszáma páros, a három pontú teljes gráf, vagyis a háromszög. Ebben van Euler-kör. Tegyük fel, hogy minden k < $|V(G)|$-ra igaz az állítás. Induljunk el $G$ egyik csúcsából, és haladjunk úgy az élek mentén, hogy egyiken sem megyünk át egynél többször. Ha elakadunk, vagyis az egyik pontból már nem vezet ki él, akkor az biztosan a kiindulási csúcs a fokszám páros volta miatt. Ekkor kaptunk egy zárt élsorozatot. Legyen $F$ egy olyan zárt élsorozat $G$-ben, melyben a lehető legtöbb él szerepel. A fenti eljárásban azért álltunk meg, mert a kezdőpontból nem indult ki újabb él, tehát az ebből a pontból kiinduló összes él $F$-ben van. Ha $F$ $G$-nek Euler-köre, akkor készen vagyunk. Amennyiben $F$ nem Euler-köre $G$-nek, akkor vizsgáljuk $G$-nek azt a részgráfját, mely pontosan azokat az éleket tartalmazza, amelyeket $F$ nem tartalmaz. Ennek a részgráfnak kevesebb csúcsa van mint $G$-nek, hiszen nem tartalmazza azt a csúcsot, amely a fenti eljárásban a kiinduló pont volt. Az indukciós feltevés miatt ennek a részgráfnak minden komponensében található Euler-kör. Ennek a részgráfnak valamely komponense tartalmaz egy olyan pontot, mely $F$-ben is szerepel. Ha ugyanis nem lenne közös pontjuk, akkor $G$ nem lenne összefüggő. Az előbb említett komponens Euler-körét járjuk be a közös pontból elindulva, majd járjuk be $F$-et. Ekkor egy $F$-nél nagyobb élszámú zárt élsorozatot kapunk. Ez azonban ellentmond a feltevésünknek. Tehát $F$ Euler-kör.

Szükséges és elégséges feltétel Euler-út létezésére

Egy összefüggő gráf akkor és csak akkor tartalmaz Euler-utat, ha a páratlan fokszámú csúcsok száma 0 vagy 2.

Bizonyítás:

Az előző tétel alapján egyértelmű, hogy 0 páratlan fokú csúcs esetén a gráfban van Euler-kör, ami egyben Euler-út is. Ha 2 páratlan fokú csúcsa van, akkor ezeket összekötve, a gráfban keletkezik egy Euler-kör. Ha ezt az élet újból elhagyjuk, akkor olyan élsorozatot kapunk, amely nem zárt, de eleget tesz az Euler-út definíciójának.

Euler-kör irányított gráfokban

A fenti gondolatmenet alapján belátható, hogy egy irányított gráfban pontosan akkor van Euler-kör, ha minden csúcsnál a bemenő és kimenő élek száma megegyezik, és a gráf erősen összefüggő (azaz bármely csúcsból kiindulva bármely csúcsba létezik irányított út). Megjegyzés: Egy irányított gráfban pontosan akkor létezik Euler-út, ha vagy minden csúcsnál megegyezik a bemenő és kimenő élek száma, vagy pontosan egy csúcsnál eggyel kevesebb a kimenő élek száma, mint a bemenőké, illetve pontosan egy csúcsnál eggyel nagyobb.

Egy példa az Euler-kör alkalmazására (Diaconis)

2ⁿ darab bináris számjegy (2^n-1 darab 0 és 2^n-1 darab 1-es) elrendezhető olyan ciklikus sorrendben, hogy (ciklikusan) tekintve az összes $n$ egymást követő bináris jegyből álló részsorozatot, minden lehetséges $n$ jegyű bináris sorozat pontosan egyszer fordul elő.

Bizonyítás (de Bruijn):

Csinálunk egy gráfot, ahol az élek $n$ hosszú bináris sorok. Az élek kiindulópontja legyen az az $n-1$ hosszú bináris sor, amely az él $n$ hosszú bináris sorának első $n-1$ tagja, a másik végpontja pedig az utolsó $n-1$ tagja (például a 0,1,1,1,0 élhez tartozó végpontok: 0,1,1,1 és 1,1,1,0). Ekkor minden csúcsban a bemenő élek száma egyenlő a kimenő élek számával, konkrétan minden csúcsból két él indul ki és kettő fut be (például az előbbi 0,1,1,1 csúcshoz tartozó kimenő élek, azok a bináris sorok, ahol a csúcs kezdőszeletnek felel meg: 0,1,1,1,0 és 0,1,1,1,1, a bejövő élek pedig azok a sorok, ahol a csúcs zárószelet: 0,0,1,1,1 és 1,0,1,1,1).

Kapcsolódó szócikkek

• Königsbergi hidak problémája
• Hamilton-kör
• Hamilton-út
• Kínai postás probléma