Euler grafikonok - studopediya
A híres Euler probléma Kőnigsbergi hidak, csuklós nyelv grafikonok 1736 vezetett egy matematikai gráfelmélet. Ez a játék a problémát, amelynek lényege a következő: a város Königsberg a folyón Pregel, két sziget, amelyek kapcsolódnak egymáshoz, és a partján hét hidat, amint azt a 34. ábra. Séta a városban, és mivel a mozgás bármely pontján, azt szeretnénk, hogy menjen át minden híd pontosan egyszer, és visszatér a kiindulási ponthoz.
Ahhoz, hogy minden csúcsa a terület, és minden hidat - a szélén. Ezután a „városi terv” jelenik meg a 35. ábrán látható. És most a probléma lehet fogalmazni grafikonok: találni egy gráf egy zárt kör, amely végigfut minden éle, vagy ahogy mondják, a borító minden éle a grafikonon. Egy ilyen lánc az úgynevezett Euler-láncot vagy Euler-ciklusban. és grafikonok, amelyekben egy ilyen lánc létezik, az úgynevezett Euler grafikonok. Nyilvánvaló, hogy a grafikon a 35. ábrán látható, Euler nem. A grafikon a 36. ábra - Euler és a megfelelő Euler lánc - sorozatából élek (1,2, ¼, 12).
Tétel 3.13.1. Connected gráf Euler akkor és csak akkor, ha minden csúcs még fokozatot.
Bizonyítás: (a) Tegyük fel, hogy a gráf Euler és C - Euler ciklus. Ezután halad szélén egyes csúcsainak, akkor növelje meg 2 fok, hanem azért, mert minden éle a grafikon megtalálható a C pontosan egyszer, a minden csúcsa lesz páros szám.
(B) Most minden csúcs van még foka, azaz a ° (VI) ³2 tetszőleges számú vertex i. Ezért a grafikon nincs medál csúcsot, és ez nem egy fa. Ezért, az oszlop legalább egy ciklus, akkor is, ha C1. Tekintsük a gráf G1 = G \ C1. Minden csúcsa G1 kell még mértékben, mivel az összes csúcsának a fokszáma C1 2. Azonban, lehetséges, hogy G1 - szétkapcsolt grafikon. Ha G1 áll izolált csúcsok, azaz, ° (vi) = 0 minden i. A C1 ciklus - és az Euler tétel bizonyítása, ha ez nem így van, akkor mindegyik komponens G1 - egy összefüggő gráf csúcsait is fokú, és az egyes komponens legalább egy ciklusban. (Azt is feltételezhetjük, hogy a G1 áll izolált csúcsok és egyetlen összefüggő komponens). Legyen ez a ciklus C2 1, C2 2, ¼, C2K. Tekintsük most a grafikon G2 = G1 \ C2. ahol C2 =. Csakúgy, mint korábban a minden csúcsa a grafikon G2 - páros vagy nulla. Ha G2 áll izolált csúcsok, akkor a gráfnak egy Euler ciklus, amely előállítható a következőképpen: menjen a bordák C1 ciklust mindaddig, amíg megfelelnek a felső tartozó bármely komponensének a grafikon G1 (például csúcsok óhatatlanul, mert . az eredeti gráf összefüggő). Akkor megyünk át a ciklus a komponensek, majd továbbra is mozog az élek mentén C1. amíg a következő vertex komponensek megfelelnek, és megy borda ciklus ezt a komponenst, majd ismét mozog tovább a következő C1 komponensek, stb Mi megy a szélek körül a gráf pontosan egyszer, és visszatér a kiindulási csúcsból. Ha G2 egy nem szigetelt tetején, majd alkotnak csatlakoztatott komponensek, amelyek mindegyike legalább egy ciklusban C3 1, C3 2, ¼, C3k. Ezután úgy a grafikon G3 = G2 \ C3. ahol C3 =. Ha G3 áll izolált csúcsok, akkor a tétel bizonyított, és megadható Euler ciklusban az eljárás. Ellenkező esetben távolítsa el az összes G3 ciklusok és cselekedni, így addig, amíg egy grafikon, csak elszigetelt csúcsok.
Következmény 1: Egy család a bordák Euler gráf feloszthatjuk diszjunkt ciklusok a bordái.
Corollárium 2: Euler minden csúcsa a grafikon tartalmazza legalább egy ciklusban.
Tétel 3.13.2. Mindenesetre gráf páratlan 2k csúcsai egy család k áramkörök (nem metszi a bordák), amelyek együttesen az összes szélei a grafikonon.
Bizonyítás: Jelölje furcsa csúcsok: A1. A2. ¼, Ak. B1. B2. ¼, Bk - minden 2k csúcsot. Hozzáadás a száma k bordák (A1, B1), (A2, B2), ¼, (Ak, Bk). Most minden csúcsának még fokozat, és van egy Euler-ciklust. Eltávolítása írásbeli k bordák, törjük a ciklus k láncokat tartalmazó minden éle az eredeti gráf.
Következmény. Earl polueylerovym akkor és csak akkor, ha pontosan két csúcsa páratlan fokú. Természetesen egy ilyen csúcsok elkezdi megnyitni az Euler-lánc grafikon, a másik - a végső.
Tekintsük az építési algoritmus Fleury Euler lánc Euler gráf.
Legyen G - Euler grafikon, akkor a következő eljárást mindig lehetséges, és vezet a Euler gráf áramkört G. Coming egy tetszőleges vertex, menjen szélei mentén tetszőleges módon, megfigyelve csak a következő szabályok: 1), hogy törölje a szélek, mert át, és törli is izoláltuk csúcsok, így formált; 2) minden egyes szakaszában megy át a hídon csak akkor, ha nincs más lehetőség.