Euler-kör

A Wikipédiából, a szabad enciklopédiából
A königsbergi hidak problémája gráffal ábrázolva

Euler-út és Euler-kör[szerkesztés]

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épezett gráf nem tartalmaz Euler-kört, sőt Euler-utat sem.

Definíció: A gráf Euler-köre olyan zárt élsorozat, mely ö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 hagyományosan az Euler-út és az Euler-kör elnevezés terjedt el, ezért ezeket használjuk.

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[szerkesztés]

Egy összefüggő 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 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 < -ra igaz az állítás. Induljunk el 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 egy olyan zárt élsorozat -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 -ben van. Ha -nek Euler-köre, akkor készen vagyunk. Amennyiben nem Euler-köre -nek, akkor vizsgáljuk -nek azt a részgráfját, mely pontosan azokat az éleket tartalmazza, amelyeket nem tartalmaz. Ennek a részgráfnak kevesebb csúcsa van mint -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 -ben is szerepel. Ha ugyanis nem lenne közös pontjuk, akkor 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 -et. Ekkor egy -nél nagyobb élszámú zárt élsorozatot kapunk. Ez azonban ellentmond a feltevésünknek. Tehát Euler-kör.

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

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[szerkesztés]

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)[szerkesztés]

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

Bizonyítás (de Bruijn):

Csinálunk egy gráfot, ahol az élek hosszú bináris sorok. Az élek kiindulópontja legyen az az hosszú bináris sor, amely az él hosszú bináris sorának első tagja, a másik végpontja pedig az utolsó 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ó témák[szerkesztés]