Euler-kör

Ehhez a szócikkhez további forrásmegjelölések, lábjegyzetek szükségesek az ellenőrizhetőség érdekében. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts a szócikk fejlesztésében további megbízható források hozzáadásával.

Ennek a szócikknek hiányzik vagy nagyon rövid, illetve nem elég érthető a bevezetője. Kérjük, segíts olyan bevezetőt írni, ami jól összefoglalja a cikk tartalmát, vagy jelezd észrevételeidet a cikk vitalapján.

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? ^[1]

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. ^[1]

Definíció: A ${\displaystyle G}$ gráf Euler-köre olyan zárt élsorozat, mely ${\displaystyle 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.

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

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.

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.

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 ${\displaystyle n}$ egymást követő bináris jegyből álló részsorozatot, minden lehetséges ${\displaystyle n}$ jegyű bináris sorozat pontosan egyszer fordul elő.

Bizonyítás (de Bruijn):

Csinálunk egy gráfot, ahol az élek ${\displaystyle n}$ hosszú bináris sorok. Az élek kiindulópontja legyen az az ${\displaystyle n-1}$ hosszú bináris sor, amely az él ${\displaystyle n}$ hosszú bináris sorának első ${\displaystyle n-1}$ tagja, a másik végpontja pedig az utolsó ${\displaystyle 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).

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