Euler-kör
A Wikipédiából, a szabad lexikonból.
Tartalomjegyzék |
[szerkesztés] Euler-út és Euler-kör
Az Euler-kör a gráfelmélet speciális sétáinak egyike.
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.
[szerkesztés] 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 aG 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.
[szerkesztés] 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.
[szerkesztés] Kapcsolódó témák
- Königsbergi hidak
- Hamilton-kör
- Hamilton-út
- Kínai postás probléma


Based on work by