Euler grafikonok - 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, mit „Euler vonal” más szótárak:
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
Gráf (gráfelmélet) - irányítatlan gráf hat csúcsok és hét élek matematikai gráfelmélet és számítástechnika gráf egy sor tárgyak köztük lévő kapcsolat. Az objektumok képviseletében a csomópontok, vagy csomópontok a grafikon, valamint egy kapcsolatot arch, vagy bordák. Mert ... ... Wikipedia
Kétoldalú digráf - irányítatlan gráf hat csúcsok és hét élek matematikai gráfelmélet és számítástechnika gráf egy sor tárgyak köztük lévő kapcsolat. Az objektumok képviseletében a csomópontok, vagy csomópontok a grafikon, valamint egy kapcsolatot arch, vagy bordák. Mert ... ... Wikipedia
Irányítatlan gráf - hat csúcsok és hét élek matematikai gráfelmélet és számítástechnika gráf egy sor tárgyak köztük lévő kapcsolat. Az objektumok képviseletében a csomópontok, vagy csomópontok a grafikon, valamint egy kapcsolatot arch, vagy bordák. Különböző területei számára ... ... Wikipedia
Digráf - irányítatlan gráf hat csúcsok és hét élek matematikai gráfelmélet és számítástechnika gráf egy sor tárgyak köztük lévő kapcsolat. Az objektumok képviseletében a csomópontok, vagy csomópontok a grafikon, valamint egy kapcsolatot arch, vagy bordák. Mert ... ... Wikipedia
Egyszerű ciklus - irányítatlan gráf hat csúcsok és hét élek matematikai gráfelmélet és számítástechnika gráf egy sor tárgyak köztük lévő kapcsolat. Az objektumok képviseletében a csomópontok, vagy csomópontok a grafikon, valamint egy kapcsolatot arch, vagy bordák. Mert ... ... 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
Euler ösvény - 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 ... Wikipedia
Hamilton grafikon - A grafikon a dodekaéder a kiválasztott Hamilton hurok ... Wikipedia
- Euler grafikonok és a kapcsolódó kérdésekről. G. Flyayshner. A monográfia szentelt egyik legfontosabb részei a gráfelmélet - Euler gráf elmélet. A könyv tartalmazza a klasszikus és modern eredmények figyelmet fordítanak algoritmikus kérdések ... Tovább Vásárlás 1178 rubelt
- Euler grafikonok és a kapcsolódó kérdésekről. Flyayshner G. A könyv egyaránt tükrözi a legújabb elméleti fejlődés, valamint a különböző alkalmazási kérdések. A matematikai tanulmány a használt eszköz a könyv az elmélet ... Tovább Vásárlás 1126 rubelt
- Euler grafikonok és a kapcsolódó kérdésekről. G. Flyayshner. A monográfia szentelt a híres osztrák Matematika Euler gráfok - az egyik gyorsan fejlődő részei a gráfelmélet. Ez az első monográfia a témában. A könyv ... Tovább Vásárlás 1023 UAH (Ukrajna esetében)