Euler ciklusok és láncok

Euler ciklus - egy ciklus, amely tartalmazza az összes szélei a grafikonon. Euler gráf - grafikon, amely Euler ciklust.

A koncepció az Euler ciklus kapcsolódik a jól ismert probléma az Euler Kőnigsbergi hidak a folyón Pregal. Meghajtja ezen összekötő hidak rakpart 2,3-1,4 két szigetek és a szigetek együtt, ábrán látható. 3.8a. Euler fogalmazott ez a probléma a következő: Van-e lehetőség, kezdve egy bizonyos ponton, hogy menjen végig a hidak csak egyszer, és térjen vissza a kiindulási ponthoz. A probléma megoldása érdekében Euler átalakított rajz egy grafikon jelző folyó partján és a szigetek, mint a csúcsa a grafikon, és hidak, a széleit a grafikon (ábra. 3.8.b).

Ábra. 3.8 rendszer és a gróf a probléma Kőnigsbergi hidak.

Könnyen belátható, hogy ebben a készítményben jelen a probléma a hidak Kőnigsbergi egyenértékű meghatározásának problémáját a grafikon a ciklus (gyűrűs útvonalat, amely nem tartalmaz ismétlődő szélek), amely áthalad az összes gráf élek. A megoldás adott az alábbi tétel.

Euler-tétel. véges irányítatlan gráf Euler akkor és csak akkor, ha csatlakoztatva van, és a fokozatok minden csúcsa még.

Annak szükségességét, hogy ilyen körülmények között meglehetősen nyilvánvaló. A grafikonon megszakad minden ciklus tartozik bármely csatlakoztatott rész, vagyis a Ez nem megy át minden alkatrészét. Másrészt, minden alkalommal, amikor Euler ciklus jön minden csúcs, meg kell kijutni belőle, a másik szélén, azaz élek incidens a vertex osztható két szomszédos Euler ciklust. Ez vonatkozik a kezdeti csúcs, ami szintén a végén. Neki, a beeső élek és szét pár, de emellett van egy él, utalva az elején a ciklus és a széle kapcsolatos a ciklus végéig.

Bezár jelentésű a probléma megtalálásának Euler gráf úgynevezett problémája a plotter. Megállapítható az alábbiak szerint: adott egy sík gráf kell ábrázolni felemelése nélkül ceruzát a papírról és körözés kétszer ugyanazt a szélét.

A feladat a plotter nem egyenértékű a Kőnigsbergi hidak és az oldat nem csak az osztály Euler ciklusok, így nem szükséges, hogy a fej a plotter visszatér a kiindulási ponthoz. A megoldás eshet osztályában Euler áramkörök.

Euler lánc - a láncot, amely tartalmazza az összes a széleit a n-gráf. de attól eltérő kezdési és befejezési csúcsot.

Tétel. Befejezéséhez n-oszlop létezett Euler-lánc, az szükséges és megfelelő kohéziót és a paritás fok az összes csúcsot, kivéve a start és a végén, amely kell páratlan fokú.

Tekintsük néhány példát.

Példa. Az áramkör és a gróf a probléma Kőnigsbergi hidak ábrán mutatjuk be. 3.8.

A grafikonon az összes csúcsának páratlan fokú. Ennélfogva a grafikon nincs Euler ciklus és a probléma megoldása lehetetlen.

Példa. Do ötszögletű piramis pentaéder és ábrán látható 3.9, az Euler hurok (áramkör)?

A helyi minden csúcsa a ötszög két, azaz még. Ennek megfelelően, egy ötszög - Euler grafikon.

Pentagon piramis páratlan fokú összes csúcsot, és nem egy Euler gráf.

Példa. Keresse Euler ciklusa az ábrán mutatjuk be. 3.10.

Ábra. 3.10. Megállapító Euler túra

A gráf összefüggő és 6 csúcsa van, minden páros. Ezért ez a grafikon - Euler és lehet levonni egyetlen tollvonással. Honnan indul rajzoló?

Ott van a következő módszer meghatározására sorrendben rajz: az oszlop, válasszon egy régiót és annak árnyékában; határos területeken az árnyékos, hagyja, és a közös vertex árnyékban, és így cselekedni, amíg minden lehetséges területen nem árnyékolt (ábra. 3.10b).

Továbbá, a grafikon kell árnyékolni húzza ki egy vagy több, a csúcsok úgy, hogy egy egyszerűen csatlakoztatva (anélkül, hogy „lyukak”) árnyékolt terület (ris.3.10s). Így gráfelmélet adott nemcsak a feltételeket megoldhatóságának a probléma, hanem a konstruktív megoldási módja is.