Euler turteknik

Euler-rundtur i ett träd, med kanter märkta för att visa i vilken ordning de korsas av turen

Euler -turtekniken (ETT), uppkallad efter Leonhard Euler , är en metod inom grafteorin för att representera träd . Trädet ses som en riktad graf som innehåller två riktade kanter för varje kant i trädet. Trädet kan sedan representeras som en Eulerisk krets av den riktade grafen, känd som Euler Tour representation (ETR) av trädet. ETT möjliggör effektiv, parallell beräkning av lösningar på vanliga problem inom algoritmisk grafteori . Den introducerades av Tarjan och Vishkin 1984.

Konstruktion

Givet ett oriktat träd som presenteras som en uppsättning kanter, kan Euler-turrepresentationen (ETR) konstrueras parallellt enligt följande:

• Vi konstruerar en symmetrisk lista med riktade kanter:
  • För varje oriktad kant { u , v } i trädet, infoga ( u , v ) och ( v , u ) i kantlistan.
• Sortera kantlistan lexikografiskt . (Här antar vi att trädets noder är ordnade och att roten är det första elementet i denna ordning.)
• Konstruera närliggande listor för varje nod (kallas nästa ) och en karta från noder till de första posterna i närliggande listor (kallas först ):
  • För varje kant ( u , v ) i listan, gör parallellt:
    • Om föregående kant ( x , y ) har x ≠ u , dvs startar från en annan nod, sätt först( u ) = ( u , v )
    • Annars om x = u , dvs startar från samma nod, sätt nästa( x , y ) = ( u , v )

Konstruera en kantlista (kallad succ ) i Euler-turordning genom att sätta pekare succ( u , v ) för alla kanter ( u , v ) parallellt enligt följande regel:

$\mathrm {succ} (u,v)={\begin{cases}\mathrm {next} (v,u)&\mathrm {next} (v,u)\neq \mathrm {noll} \\ \mathrm {först} (v)&{\text{annars}}.\end{fall}}$

Den resulterande listan kommer att vara cirkulär.

Den övergripande konstruktionen tar arbete W ( n ) = O(sort( n )) (tiden det tar att sortera n objekt parallellt) om trädet har n noder, som i träd är antalet kanter en mindre än antalet knutpunkter.

Rötter, avancerar och drar sig tillbaka kanter

Om trädet har en rot kan vi dela den cirkulära listan efter den roten. I så fall kan vi tala om fram- och reträttkanter : givet ett par noder u , v , kallas den första förekomsten av antingen ( u , v ) eller ( v , u ) i ETR för framkant , och den andra händelsen kallas reträttkanten . Detta tilltalar intuitionen att första gången en sådan kant korsas ökar avståndet till roten, medan avståndet minskar andra gången.

Omrotning av trädet kan göras på konstant tid O(1) genom att dela den cirkulära listan succ vid den nya roten.

Ansökningar

Alla följande problem kan lösas i O(Prefix summa( n )) (den tid det tar att lösa prefixsummaproblemet parallellt för en lista med n poster):

1. Klassificering av fram- och reträttkanter: Gör listrankning på ETR och spara resultatet i en tvådimensionell array A . Då är ( u , v ) en framstegskant iff A ( u , v ) < A ( v , u ), och en reträttkant annars.
2. Bestäm nivån för varje nod: Gör en prefixsumma på ETR, där varje framstegsflank räknas som 1, och varje reträttkant räknas som −1. Då är värdet vid framkantskanten ( u , v ) nivån på v .
3. Antal noder i ett underträd med rötter vid v : anta att föräldern till v är u, bestäm framkantskanten ( u , v ) och reträttkanten ( v , u ) parallellt och räkna sedan antalet framflanker mellan ( u ) , v ) och ( v , u ) med prefixsumma.
4. Djupet -första sökindexet för en nod v : räkna antalet framkanter upp till och inklusive ( u , v ).
5. Bestäm den lägsta gemensamma förfadern av två noder.

Euler tour träd

Henzinger och King föreslår att representera ett givet träd genom att hålla dess Euler-tur i ett balanserat binärt sökträd , knappat av indexet i turen. Så till exempel kommer det obalanserade trädet i exemplet ovan, med 7 noder, att representeras av ett balanserat binärt träd med 14 noder, en för varje gång varje nod dyker upp på turen.

Vi kan representera en skog (en acyklisk graf) med hjälp av en samling ET-träd - ett ET-träd för ett skogsträd. Denna representation låter oss snabbt svara på frågan "vad är roten till nod v?" genom att bara flytta till den första noden i ET-trädet (eftersom noder i ET-trädet är nycklade av deras plats i Euler-turen, och roten är den första och sista noden i turen). När den representerade skogen uppdateras (t.ex. genom att koppla två träd till ett enda träd eller genom att dela ett träd till två träd), kan motsvarande Euler-turstruktur uppdateras i tiden O(log(n)).

Länk-/kapträd har liknande prestandagarantier. Medan LC-träd är bra för att upprätthålla aggregat på vägar i ett träd (gör det till ett bra val av datastruktur i nätverksflödesalgoritmer), är ET-träd bättre på att behålla aggregerad information om underträd.