Euler ösvény - ez
Megléte Euler ciklus és az Euler útvonal
Természetesen Euler ciklus / path csak létezik egy gráf vagy grafikonok, amelyek eltávolítása után az egységes csúcsok kerül kapcsolatba.
Az irányítatlan gráf
Továbbá, az a tétel bizonyítása Euler. Euler ciklus akkor és csak akkor, ha a gráf nincsenek csúcsai páratlan fokú. Euler útvonal akkor és csak akkor, ha a csúcsok száma páratlan mértéke nem nagyobb, mint kettő.
Tétel: Euler utat a grafikonon akkor és csak akkor, ha a gráf összefüggő, és nem több, mint két csúcsa páratlan fokú. [1] [2]
Egy irányított gráf
Connected irányított gráf tartalmaz Euler ciklus akkor és csak akkor minden csúcsra a-foka van a Half-eredmény, ami a felső része azonos számú bordák, méghozzá ki és be.
Keresés Euler utat a grafikonon
Bármikor problémájának csökkentésére megállapító Euler utat a probléma megtalálásának Euler ciklust. Valóban, tegyük fel, hogy az Euler ciklus nem létezik, és az Euler útvonal létezik. Aztán a grafikonon lesz pontosan 2 csúcsai páratlan fokú. Csatlakoztassa a tetején a borda, és szerezzen be egy grafikont, amelyben minden csúcs még fokozatot, és Euler ciklus létezik. Mi található a grafikonon Euler ciklus (algoritmus. Lásd alább), majd vegyük ki a válasz nesuschestvueschee szélét.
Keresés Euler ciklus egy gráf
Figyelembe vesszük a leggyakoribb eset - esetében irányított multigráf. esetleg hurkok. Azt is feltételezzük, hogy Euler ciklust a grafikon létezik (és legalább egy csúcs). Találni egy Euler ciklus, használja a tény, hogy Euler ciklus - társulás valamennyi egyszerű ciklus a grafikon. Ezért a mi feladatunk -, hogy megtalálja az összes hurok hatékonyan és egyesíti őket egy.
Lehetőség van, hogy észre, például olyan rekurzív:
Ez elég, hogy ezt az eljárást minden neodinochnoy csúcsot, és megtalálja az összes ciklusban a grafikonban távolítsa el őket a grafikonon, és összekapcsolják őket egy Euler ciklust.
Keresni a ciklus 1. lépésben használja a mélységi keresést.
A komplexitás ezen algoritmus - O (M), azaz a lineáris bordák száma M a grafikonon.
Példa megvalósítása C ++
Nézze meg, mi a „Euler út” más szótárak:
Euler ciklus - Count Kőnigsbergi hidak. Ez a grafikon nem Euler, így nincs megoldás ... Wikipedia
Az útvonal a digráf - meghatározását tartalmazza gráfelmélet. Dőlt hivatkozásokat a feltételeket a szótárban (ezen az oldalon). # A B C D E F G H I J K L M N O P Q R S T U V ... Wikipedia
Egy egyszerű módja annak, hogy digráf - meghatározását tartalmazza gráfelmélet. Dőlt hivatkozásokat a feltételeket a szótárban (ezen az oldalon). # A B C D E F G H I J K L M N O P Q R S T U V ... Wikipedia
Euler grafikonok - Count Kőnigsbergi hidak. Ez a grafikon nem Euler, így nincs megoldás. Minden csúcs ezen grafikont chotnuyu mértékben, így a grafikonon Euler. Bypass élek alfabetikus sorrendben adja Euler ciklust. Euler út (Euler ... ... Wikipedia
Euler ciklus - Count Kőnigsbergi hidak. Ez a grafikon nem Euler, így nincs megoldás. Minden csúcs ezen grafikont chotnuyu mértékben, így a grafikonon Euler. Bypass élek alfabetikus sorrendben adja Euler ciklust. Euler út (Euler ... ... Wikipedia
Graph (matematika) - Ebben a kifejezést, vannak más célra, grafikon (érték) .. Irányítatlan gráfot hat csúcsok és hét élek matematikai gráfelmélet és számítástechnika gráf egy sor nem üres csúcsok halmaza, és több pár ... ... Wikipedia