Forståelse av euleriske kretser i grafisk teori

En eulerisk krets er en lukket gang som krysser hver kant av en graf nøyaktig én gang og vender tilbake til startpunktet. Konseptet stammer fra de berømte syv broene i Königsberg problem som Leonhard Euler utgjorde i 1736. Euler beviste at en slik krets eksisterer bare hvis hver hjørne i grafen har jevn grad og grafen er koblet til (isolert vertikk). Dette grunnleggende resultatet la grunnlaget for grafteori og forblir avgjørende i nettverksanalyse, kretsdesign og kombinatorial optimering.

For å oppgi det formelt: La G = (]V, ]E]) være en udirektert graf. En eulerisk krets eksisterer om og bare om hver hjørne ]v] ⁇ V har en jevn grad, og grafen er koblet når man vurderer bare svinger med ikke-null grad. For rettede grafer er forholdene som hver hjørne har lik i ⁇ grad og ut ⁇ grad og den underliggende udirekterte grafen er koblet.

Hva er Hierholzers algoritme?

Hierholzers algoritme, publisert av den tyske matematikeren Carl Hierholzer i 1873, er en effektiv metode for å bygge en eulerisk krets når de nødvendige forholdene er oppfylt. Den bygger kretsen ved å finne en serie sykluser og slå dem sammen. Algoritmen kjører i lineær tid O]]]]]) med hensyn til antall kanter, noe som gjør det optimalt for tette og sparsomme grafer likt.

Nøkkelkonsepter

  • Cycle deteksjon: Fra et hjørne, følg ubrukte kanter til tilbake til startvirvelen. Dette danner en enkel syklus.
  • Når en hjørne på den aktuelle kretsen fortsatt har ubrukte kanter, dannes en ny syklus fra den hjørne og settes inn i kretsen.
  • Som kanter brukes, er de merket eller fjernet for å unngå å revisiting dem.

Trinn-for-steg Beskrivelse av Hierholzers algoritme

Algoritmen kan implementeres rekursivt eller iterativt. Kjernen ideen er å bygge en krets ved gjentatte ganger å forlenge underkretser. Nedenfor er en detaljert nedbrytning.

Trinn 1: Velg en startvertex

Velg et hjørne med minst én kant. Siden grafen er tilkoblet og alle grader er like, vil alle hjørner fungere. Vanligvis starter algoritmen ved hjørner [[FLT: 0]]] v[FLT: 1].

Trinn 2: Traverse en syklus

Fra den aktuelle hjørnen, følg alle ubrukte kanter til en nabo. Fortsett å bevege seg langs ubrukte kanter, markere hver kant som brukt, til du vender tilbake til startpunktet. Dette produserer en syklus C]. Hvis syklusen inneholder alle kanter av grafen, avsluttes algoritmen ⁇ vi har en eulerisk krets.

Trinn 3: Finn vibrasjoner med ubrukte kanter

Skann den gjeldende kretsen for alle hjørner u] som fortsatt har ubrukte kanter. Hvis ingen eksisterer, er algoritmen fullstendig. Ellers, la ]u være en slik hjørne.

Trinn 4: Bygg en ny syklus fra ]u

Starter på u], gjentar syklusen ⁇ finne prosessen blant de ubrukte kantene. Dette skaper en ny syklus C ⁇ ] som begynner og slutter på u].

Trinn 5: Slå den nye syklusen sammen i hovedkretsen

Sett inn C ⁇ ] i hovedkretsen i posisjon av u]. Den resulterende gangen er fortsatt en krets (lukket) og dekker alle kanter som besøkes så langt. Gå tilbake til trinn 3.

Fordi hver hjørne har jevn grad, blir prosessen aldri fast: når du går inn i en hjørne, vil det alltid være en ubrukt kant å forlate, til hjørnets grad blir null. Algoritmen garanterer at den endelige spaserturen inkluderer hver kant nøyaktig én gang.

Eksempel: Konstruering av en eulerisk krets

Tenk på en udirektert graf med hjørner A, B, D, D og E. Edges: AB, AC, AD, BC, BD, CE, DE. (Dette er en liten graf der hver hjørne har jevn grad: deg(A)=3, deg(B)=3, deg(C)=2, deg(D)=3, deg(E)=1? Det tilfredsstiller ikke jevn gradsbetingelsen. La oss gjøre det riktig: Bruk en graf der alle grader er like: A ⁇ B, B ⁇ C, C ⁇ D, D ⁇ A, pluss A ⁇ C og B ⁇ D. Det gir hver hjørnegrad 3? Det er rart. Faktisk en enkel jevn ⁇ gradseksemplar: en trekant med hver hjørnegrad 2? Ikke interessant. La oss bruke et mer typisk eksempel: hjørner 1,2,3, 5 med kanter: 1 ⁇ 2, 2 ⁇ 3, 3 ⁇ 4, 3 ⁇ 4, 3 ⁇ 4, 3 ⁇ 3, 3 ⁇ 3, 2 (f.eks. 2) (f.

Kjør Hierholzers algoritme:

  • Start på hjørne 1. Følg kanter: 1 ⁇ 2 (bruk), 2 ⁇ 3 (bruk), nå på 3. Velg ubrukt kant 3 ⁇ 4 (bruk), 4 ⁇ 5 (bruk), 5 ⁇ 3 (bruk). Return til 3, men det første utgangspunktet var 1. Vi har ikke returnert til 1 ennå. Faktisk må algoritmen danne en syklus som returnerer til startpunktet. La oss spore riktig: Start på 1, gå 1 ⁇ 2, 2 ⁇ 3, nå fra 3 kan vi gå 3 ⁇ 1 (ubrukt) ⁇ som gir syklus 1 ⁇ 2 ⁇ 3 ⁇ 1. Det er syklus C1. Etter det, kanter venstre: 3 ⁇ 4, 4 ⁇ 5, 5 ⁇ 3.
  • Scan C1: Vertex 3 har ubrukte kanter. Start ny syklus på 3: 3 ⁇ 4, 4 ⁇ 5, 5 ⁇ 3. Syklus C2 = 3 ⁇ 4 ⁇ 5 ⁇ 3.
  • Føy C2 til C1 ved hjørne 3: resulterende krets: 1 ⁇ 2 ⁇ 3 ⁇ 4 ⁇ 5 ⁇ 3 ⁇ 1. Alle kanter som brukes, kretsen er eulerisk.

Dette eksemplet illustrerer elegansen i algoritmen: sykluser oppdages og kombineres sømløst.

Kompleksitet og implementeringsoverveielser

Hierholzers algoritme kjører i ]]]V + ]E]) tid når du bruker en adjacensliste representasjon og effektive datastrukturer for kantfjernelse (f.eks. ved hjelp av iteratorer eller lenkede lister). Algoritmen er optimal fordi hver kant behandles nøyaktig én gang. minneoverdelen er ]O]] + ]]]) for lagring av grafen og kretsen.

For regisserte grafer, de samme tilnærmingsarbeidene gitt grafen er eulerisk (i ⁇ grader lik ut ⁇ grad ved hver hjørne). Algoritmens krav om jevne grader oversettes også til det rettrettede tilfellet.

Sammenligning med Fleurys algoritme

En annen velkjent algoritme for å finne euleriske kretser er Fleurys algoritme, som fungerer ved å krysse kanter samtidig som den gjenværende grafen forblir koblet (dvs. unngå broer). Fleurys algoritme kjører i O]]2]]]) tid fordi den trenger å sjekke tilkobling ved hvert trinn. Hierholzers algoritme er generelt foretrukket for sin lineære tidskompleksitet og enklere implementering. Den eneste ulempen er at Hierholzers krever imidlertid at grafen skal være eulerisk (selv grader) mens Fleurys også kan håndtere semi-Eulerian grafer (når nøyaktig to hjørner har en merkelig grad, produserer en eulerisk sti). Imidlertid kan Hierholzers tilpasses godt for eulere kant ved å bygge en kjendistribusjonell kant kant ved å bygge en kling mellom de to kretsene, og å fjerne en dugle

Søknader om Hierholzers algoritme

Eulerisk krets har mange virkelige bruksområder.

Kinesisk postman problem

I det kinesiske postman-problemet (rutekontroll) er målet å finne den korteste lukkede spaserturen som dekker alle kanter minst én gang. For grafer som allerede er euleriske, er løsningen ganske enkelt Eulerian-kretsen. Hierholzers algoritme gir den kretsen. For ikke-eulerian-grafer reduserer problemet til å duplisere kanter for å gjøre alle grader selv, og deretter bruke Hierholzers.

Nettverksrute og kretsdesign

Euleriske kretser brukes til å designe effektive ruter for gatesveipere, søppelsamling og nettverkspakkeoverføring der hver lenke må krysses nøyaktig én gang. Algoritmen bidrar til å minimere overflødig reise.

DNA fragment-samling

I beregningsbiologien er de Bruijn-grafen tilnærming til genomsammenstilling avhengig av å finne euleriske stier eller kretser gjennom k ⁇ mer-grafer. Hierholzers algoritme er en kjernekomponent i mange samlere, noe som gjør det mulig å rekonstruere sammenhengende sekvenser fra korte lesninger.

Datagrafikk og Maze Generation

Euleriske spor brukes til å generere labyrinter og i visse graf tegning algoritmer der kanter må tegnes uten å løfte pennen. Algoritmen gir en optimal konstruksjon.

Integrert kretstesting

I svært stor-skala integrasjon (VLSI) design kan testing av alle forbindelser modelleres som et Eulerisk kretsproblem, minimering tester bevegelse.

Lese og eksterne ressurser

For å utdype din forståelse av Euleriske kretser og Hierholzers algoritme, anbefales følgende ressurser:

Konklusjon

Hierholzers algoritme forblir en hjørnestein i grafen traversal for sin eleganse, hastighet og bred anvendelse. Ved å avkomponere problemet i å finne og slå sammen sykluser, gir det en enkel og optimal løsning for å konstruere euleriske kretser. Enten du designer nettverksruter, samle genomer eller løse puslespill, forstår denne algoritmen utstyrer deg med et kraftig verktøy for å håndtere grafer med jevne ⁇ graders hjørner. Dens lineære tidskompleksitet og enkle rekursiv struktur gjør det til en favoritt blant algoritmeentusiaster og utøvere.