Euler cyklus

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. august 2021; checks kræver 2 redigeringer .

En Euler-sti ( Euler -kæde ) i en graf er en sti , der går gennem alle grafens kanter og desuden kun én gang. (jf. Hamiltonsk sti )

En Euler-cyklus  er en Euler-sti, der er en cyklus , det vil sige en lukket sti, der passerer gennem hver kant af grafen nøjagtigt én gang.

En Euler-graf  er en graf, der indeholder en Euler-cyklus.

En semi -Euler-graf  er en graf, der indeholder en Euler-sti.

Eksistensen af ​​en Euler-cyklus og en Euler-sti

I en urettet graf

Ifølge sætningen bevist af Euler eksisterer en Euler-cyklus, hvis og kun hvis grafen er forbundet eller vil blive forbundet, hvis alle isolerede hjørner fjernes fra den, og der ikke er nogen hjørner af ulige grad i den .

En Euler-sti i en graf eksisterer, hvis og kun hvis grafen er forbundet og indeholder højst to hjørner af ulige grader. [1] [2] I lyset af håndtrykslemmaet skal antallet af hjørner med en ulige grad være lige. Det betyder, at Euler-stien kun eksisterer, når dette tal er lig med nul eller to. Desuden, når den er lig med nul, degenererer Euler-stien til en Euler-cyklus.

I en rettet graf

En rettet graf indeholder en Euler-cyklus, hvis og kun hvis den er stærkt forbundet eller kun én af dens stærkt forbundne komponenter indeholder kanter (og alle de andre er isolerede hjørner), og for hvert hjørne af grafen er dens indegree lig med dens udgrad , at er, toppunktet omfatter lige så mange ribben, som det kommer ud :.

Da en Euler-cyklus er et specialtilfælde af en Euler-sti, er det klart, at en rettet graf indeholder en Euler-sti, hvis og kun hvis den indeholder enten en Euler-cyklus eller en Euler-sti, der ikke er en cyklus. En rettet graf indeholder en Euler-sti, der ikke er en cyklus, hvis og kun hvis den er svagt forbundet, og der er to knudepunkter og (henholdsvis de indledende og sidste knudepunkter på stien), således at deres indegrees og outgraders er forbundet med ligheder og , og alle andre hjørner har samme halve grader af udgående og indgående: [3] .

At finde en Euler-sti i en graf

Man kan altid reducere problemet med at finde en Euler-sti til problemet med at finde en Euler-cyklus. Antag faktisk, at Euler-cyklussen ikke eksisterer, men Euler-stien eksisterer. Så vil grafen have præcis 2 toppunkter med ulige grader. Vi forbinder disse hjørner med en kant, og vi får en graf, hvor alle hjørner er af lige grad, og der findes en Euler-cyklus i den. Lad os finde en Euler-cyklus i denne graf ( ved hjælp af algoritmen beskrevet nedenfor), og derefter fjerne en ikke-eksisterende kant fra svaret.

Find en Euler-cyklus i en graf

Fleurys algoritme

Algoritmen blev foreslået af Fleury i 1883.

Lad en graf gives . Vi starter fra et eller andet toppunkt og krydser hver gang den krydsede kant ud. Vi passerer ikke langs en kant, hvis fjernelsen af ​​denne kant fører til en opsplitning af grafen i to forbundne komponenter (ikke medregnet isolerede hjørner), dvs. det er nødvendigt at kontrollere, om kanten er en bro eller ej.

Denne algoritme er ineffektiv : køretiden for den oprindelige algoritme er O (| E | 2 ). Hvis du bruger en mere effektiv algoritme til at finde broer [4] , så kan udførelsestiden reduceres til , men den er stadig langsommere end andre algoritmer.

Algoritmen kan udvides til rettede grafer.

Loop-baseret algoritme

Vi vil overveje det mest generelle tilfælde - tilfældet med en rettet multigraf , muligvis med loops . Vi antager også, at Euler-cyklussen i grafen eksisterer (og består af mindst et toppunkt). For at søge efter en Euler-cyklus bruger vi det faktum, at en Euler-cyklus er foreningen af ​​alle simple cyklusser i en graf. Derfor er vores opgave effektivt at finde alle cyklusser og effektivt fusionere dem til én.

Dette kan for eksempel gøres rekursivt:

procedure find_alle_cyklusser (v) var array cykler 1. mens der går en cyklus gennem v, finder vi den føje alle hjørnerne af den fundne cyklus til cyklus-arrayet (bevar gennemløbsrækkefølgen) fjern cyklus fra grafen 2. gennemgå elementerne i cyklusarrayet hvert element i cyklusser[i] føjes til svaret kalder os selv rekursivt fra hvert element: find_all_cycles (cyklusser[i])

Det er nok at kalde denne procedure fra et hvilket som helst toppunkt på grafen, og det vil finde alle cyklusserne i grafen, fjerne dem fra grafen og kombinere dem til en Euler-cyklus.

For at søge efter en cyklus i trin 1 bruger vi dybde-først-søgning.

Kompleksiteten af ​​den resulterende algoritme er O (|E|), det vil sige lineær i forhold til antallet af kanter i den givne graf.

Noter

  1. ↑ Euler-stier (utilgængeligt link) . Hentet 26. november 2008. Arkiveret fra originalen 5. januar 2009. 
  2. ↑ V. Alekseev, V. Talanov, Kursus "Graphs and Algorithms", Forelæsning nr. 2 "Rutes, connectivity, distances" : Routes and connectivity in digraphs // Intuit.ru , 09/27/2006
  3. ↑ Christophides N. Grafteori. Algoritmisk tilgang (kapitel 9.5) - M .: Mir, 1978.
  4. ↑ Mikkel Thorup. Næsten optimal fuldt [ sic ] -dynamisk grafforbindelse // Proceeding STOC '00 Proceedings of the tredive-second annual ACM symposium on Theory of computing. - Portland : Association for Computing Machinery, 2000. - 21-23 5. - S. 343-350 . - doi : 10.1145/335305.335345 .

Se også

Links