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 | forrásszöveg szerkesztése]

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 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 hagyományosan az Euler-út és az Euler-kör elnevezés terjedt el, ezért ezeket használjuk.

Szükséges és elégséges feltétel Euler-kör létezésére[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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 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ó témák[szerkesztés | forrásszöveg szerkesztése]