Lehet-e olyan sétát tenni a 18. századi Königsbergben, ami minden hídon pontosan egyszer megy át és ugyan oda érkezünk ahonnan elindultunk? Leonhard Euler (1707 Bázel - 1783 Szentpétervár) válasza: 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örSzerkeszté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épzett 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 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éreSzerkeszté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éreSzerkeszté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áfokbanSzerkeszté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ákSzerkesztés