Euler cykel

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 augusti 2021; kontroller kräver 2 redigeringar .

En Euler-bana ( Eulerian chain ) i en graf är en bana som passerar genom grafens alla kanter och dessutom bara en gång. (jfr Hamiltons väg )

En Euler-cykel  är en Euler-bana som är en cykel , det vill säga en stängd bana som passerar genom varje kant av grafen exakt en gång.

En Euler-graf  är en graf som innehåller en Euler-cykel.

En semi- Euler-graf  är en graf som innehåller en Euler-bana.

Förekomsten av en Euler-cykel och en Euler-bana

I en oriktad graf

Enligt satsen bevisad av Euler existerar en Euler-cykel om och endast om grafen är ansluten eller kommer att anslutas om alla isolerade hörn tas bort från den, och det inte finns några hörn av udda grad i den .

En Euler-bana i en graf finns om och endast om grafen är sammankopplad och innehåller högst två hörn av udda grad. [1] [2] Med tanke på handslagslemma måste antalet hörn med en udda grad vara jämnt. Det betyder att Euler-vägen endast existerar när detta tal är lika med noll eller två. Dessutom, när den är lika med noll, degenererar Euler-banan till en Euler-cykel.

I en riktad graf

En riktad graf innehåller en Euler-cykel om och endast om den är starkt ansluten eller bara en av dess starkt anslutna komponenter innehåller kanter (och alla andra är isolerade hörn) och för varje hörn av grafen dess indegree är lika med dess utgrad , att är, hörn innehåller lika många revben som det kommer ut: .

Eftersom en Euler-cykel är ett specialfall av en Euler-bana är det tydligt att en riktad graf innehåller en Euler-bana om och endast om den innehåller antingen en Euler-cykel eller en Euler-bana som inte är en cykel. En riktad graf innehåller en Euler-bana som inte är en cykel om och endast om den är svagt ansluten och det finns två hörn och (vägens initiala respektive slutliga hörn) så att deras grader och utgrader är relaterade till likheter och , och alla andra hörn har samma halvgrader av utgående och ingående: [3] .

Hitta en Euler-bana i en graf

Man kan alltid reducera problemet med att hitta en Euler-väg till problemet med att hitta en Euler-cykel. Anta faktiskt att Eulercykeln inte existerar, men Eulervägen existerar. Då kommer grafen att ha exakt 2 hörn av udda grad. Vi förbinder dessa hörn med en kant, och vi får en graf där alla hörn är av jämn grad, och en Euler-cykel finns i den. Låt oss hitta en Euler-cykel i den här grafen ( med algoritmen som beskrivs nedan), och sedan ta bort en icke-existerande kant från svaret.

Hitta en Euler-cykel i en graf

Fleurys algoritm

Algoritmen föreslogs av Fleury 1883.

Låt en graf ges . Vi utgår från någon vertex och varje gång stryker vi över den korsade kanten. Vi passerar inte längs en kant om borttagandet av denna kant leder till en uppdelning av grafen i två sammankopplade komponenter (ej att räkna med isolerade hörn), dvs. det är nödvändigt att kontrollera om kanten är en bro eller inte.

Denna algoritm är ineffektiv : körtiden för den ursprungliga algoritmen är O (| E | 2 ). Om du använder en mer effektiv algoritm för att hitta broar [4] , så kan exekveringstiden reduceras till , men den är fortfarande långsammare än andra algoritmer.

Algoritmen kan utökas till riktade grafer.

Loop-baserad algoritm

Vi kommer att överväga det mest allmänna fallet - fallet med en riktad multigraf , eventuellt med loopar . Vi antar också att Eulercykeln i grafen existerar (och består av minst en vertex). För att söka efter en Euler-cykel använder vi det faktum att en Euler-cykel är föreningen av alla enkla cykler i en graf. Därför är vår uppgift att effektivt hitta alla cykler och effektivt slå samman dem till en.

Detta kan till exempel göras rekursivt:

procedur hitta_alla_cykler (v) var arraycykler 1. medan det går en cykel genom v, hittar vi den lägg till alla hörn av den hittade cykeln till cykler-arrayen (bevara genomgångsordningen) ta bort cykel från grafen 2. gå igenom elementen i cykler array varje element i cykler[i] läggs till svaret kallar oss rekursivt från varje element: hitta_alla_cykler (cykler[i])

Det räcker att anropa denna procedur från valfri hörn av grafen, och den kommer att hitta alla cykler i grafen, ta bort dem från grafen och kombinera dem till en Euler-cykel.

För att söka efter en cykel i steg 1 använder vi djup-först-sökning.

Komplexiteten hos den resulterande algoritmen är O (|E|), det vill säga linjär med avseende på antalet kanter i den givna grafen.

Anteckningar

  1. ↑ Euler Paths (otillgänglig länk) . Hämtad 26 november 2008. Arkiverad från originalet 5 januari 2009. 
  2. ↑ V. Alekseev, V. Talanov, Kurs "Graphs and Algorithms", Föreläsning nr 2 "Rutter, connectivity, distances" : Routes and connectivity in digraphs // Intuit.ru , 09/27/2006
  3. ↑ Christophides N. Grafteori. Algoritmisk ansats (kapitel 9.5) - M .: Mir, 1978.
  4. ↑ Mikkel Thorup. Nästan optimal fullt [ sic ] -dynamisk grafanslutning // Fortsätt STOC '00 Proceedings of the trettio-andra årliga ACM symposium on Theory of computing. - Portland : Association for Computing Machinery, 2000. - 21-23 5. - S. 343-350 . - doi : 10.1145/335305.335345 .

Se även

Länkar