Eulertour-Technik

Berechnungen auf Bäumen im parallelen
Eulergraph G
- G ist ein
  - Digraph
- besitzt gerichteten Kreis, der jede Kante genau einmal durchläuft
- Satz:
  - sei G zusammenhängend
  - G ist Euergraph ↔" vÎV: indegree(v) = outdegree(v)
- Sei T ein
  - Baum
- man erhält den Euler-Graphen durch
  - Ersetzen der Kanten durch Doppelkanten
    - → Digraph
    - → indegree aller Knoten = outdegree
    - → es gibt einen Euler-Kreis
- Anwendung
  - gegeben: Wurzelbaum T.
  - Aufgabe: durchnummerieren der Blätter
  - dazu: Eulertour im zugehörigen Digraph T'
    - Eulertour:
      - die Eulertour auf T @ Eulerkreis auf T'
    - Blauer Weg: Euler-Pfad
      - eine an einem Knoten "aufgeschnittene" Euler-Tour
      - z.B. von Wurzel ausgehend durch den gesamten Baum bis man wieder an der Wurzel ist
Ziel für eine Euler-Tour:
- O(1) Time
- O(n) Work
- ist dann erreichbar, wenn Baum in einer speziellen Form als Input gegeben ist → Input-sensitiver Algorithmus
- gesucht: Nachfolgebeziehung in der Form i Þ s(i)
  - Kanten und Successor (Nachfolger) davon
  - ist parallel auszurechnen
- notwendige Darstellung:
  - Adjazenzlisten als Ringlisten
  - rot: Querbeziehungen (gegenseitige Zeiger)
- Bezeichnungen:
  - v Î T' ist ein Knoten aus dem Eulergraph
  - adj(v) = <u₀, u₁, ..., u_d-1> = Liste der zu v adjazenten Knoten (Ringliste)
Eulertour:
- Kantenreihenfolge ist über Beziehung Kante - Nachfolger gegeben:
  wenn i eine Kante ist so soll s(i) die Nachfolgekante sein
- es sei i die Kante <u_i, v>
- es seien <u₀, u₁, ..., u_d-1> = adj(v) die d mit Knoten v verbundenen Knoten
- Dann ist s(i) = s(<u_i,v>) := <v,u_{(i+1) mod d}> für 0 ≤ i ≤ d-1
- Satz: s definiert eine Eulertour auf T'
- Beweis:
  - klar ist: es handelt sich um Kreise
  - zu zeigen: es handelt sich um nur einen Kreis!
  - Induktion über die Anzahl von Knoten
    - Induktionsanfang: n=2 - trivial
    - Induktionsbehauptung (n>2):
      - sei T ein Baum mit n Knoten
      - sei v Blatt des Baumes T
        
        (jeder Baum hat mind. 1 Blatt)
      - adj(v) = <u>,
        s(<u,v>) = <v,u>
      - adj(u) = <....,v', v, v'', ....>
      - s(<v',u>) = <u,v>, s(<v,u>) = <u,v''>
      - Entfernen von v aus T Þ T₁ Þ T₁'
      - → adj(u) = <...v', v'',....>
      - Þ s(<v',u>) = <u,v''>
      - → |T₁| = n-1
    - nach Induktionsvorraussetzung gilt der Satz für T₁'.
      - mit s(<v',u>)=<u,v> und s(<v,u>) = <u,v''>
    - Erneutes Einfügen von v mit beiden Pfeilen liefert den gewünschten Eulerkreis
Implementierung
der Berechnung von s
- am Beispiel
  - beginnen bei 1
  - gehen zu 2
  - Nachschlagen in Adjazenzliste von 2
  - gehen zu 5
  - Nachschlagen in Adjazenzliste von 5
  - zurück zu 2
  - weiter in Adjazenzliste von 2
  - gehen zu 6
  - ...
Satz: wenn T' über Adjazenzlisten und die zusätzlichen
Doppelpointer gegeben ist, kann man s parallel berechnen
- in O(1) Time
- mit O(n) WORK
- geht auf EREW?
Anwendungen
- Rooting (Wurzeln)
  - Aufgabe:
    - es ist ein Baum T mit einer Euler-Tour im Digraph T' gegeben
    - ein Knoten ist als Wurzel r markiert
    - für jeden Knoten v ≠ r soll der Vater p(v) bestimmt werden, wenn r die Wurzel ist
  - Lösung:
    - Start bei r
    - gib Eulerpfad an und durchlaufe diesen
    - dazu: Wichten aller Kanten <x,y> mit 1,
      bis auf die letzte Kante: w(<u,r>) := 0
    - u = letzter Knoten in der Adjazenzliste von r
  - Schlüsselbeobachtung:
    - seien seien u und v zwei adjazente Knoten
    - dann gibt es eine gerichtete Kante <u,v> und eine gerichtete Kante <v,u>
    - es gilt: Wenn u der Vater von v ist, dann ist die
      Präfixsumme von <u,v> kleiner als die Präfixsumme von <v,u>
  - Algorithmus:
    - INPUT: Baum T, Wurzel r Î T, Nachfolgefunktion s (für Eulertour)
    - OUTPUT: "v≠r: p(v)
    - begin
    - 1. identifiziere den letzten Knoten in adj(r)
      - markiere diesen als u
      - s(<u,r>):=nil
        
        // "aufschneiden"
    - 2. weise den Kanten das Gewicht 1 zu; berechne Parallel-Präfix
    - 3. für jede Kante <x,y> sei x:=p(y) genau dann,
      wenn Präfix-Summe(<x,y>) < Präfix-Summe(<y,x>)
    - end
    - Analyse:
      - Rooting geht mit der Eulertour-Technik
      - in O(log n) Zeit
      - mit O(n) WORK
      - Beweis: Parallel Präfix geht in entsprechender Zeit, Rest trivial J
- Post-Order-Nummerierungen für Baum T mit Wurzel r
  - serielle Idee:
    - gehe Teilbäume von links nach rechts durch
    - gib Söhne vor ihren Vätern aus
  - Algorithmus:
    - INPUT: Wurzelbaum (T,r), Eulertour s
    - OUTPUT: "v: post(v)
    - begin
    - 1. "v≠ r: w(<v,p(v)>):=1, w(<p(v),v)):=0
      - // Wichten der Kanten
      - // aufwärtsgerichtete mit 1
      - // abwärtsgerichtete mit 0
    - 2. berechne Parallel Präfix
      - Präfixsummenproblem
    - 3. post(v):=Präfixsumme(<v,p(v)>); v=r: post(r)=n
      - // n = |V| ist die Anzahl der Knoten
    - end
  - Beispiel
    - Ablauf
    - Ergebnis
- Definition:
  - v Kanten
  - Size(v) := Anzahl der Knoten mit Teilbaum mit Wurzel v
- Satz: In O(log n) TIME mit O(n) WORK lassen sich auf der EREW berechnen:
  - " v: Size(v)
    - Gewichtsfunktion w(v,p(v)) = 1
      w(p(v),v) = 0 verwenden
    - size(v) = Präfixsumme(v,p(v))-Präfixsumme(p(v),v)
    - Anmerkung: geht so nur für v≠root, aber mit etwas Aufwand geht auch dieser Spezialfall
  - level(v)
    - einfach Gewichtsfunktion w(v,p(v)) = -1
      w(p(v),v) = 1 verwenden und dann Präfixsumme
    - Level des Knotens = Summe an der Kante <p(v),v>
  - postorder siehe oben
  - preorder
  - inorder
    - Lösung relativ schwer
    - Grajetzki fragen
- Blätter-Theorem:
  - mit der Eulertour-Technik kann man die Blätter von links nach rechts durchnummerieren
    - in O(log n) Time
    - mit O(n) WORK
    - auf der EREW
  - Beweisidee: Blätter mit 1 Gewichten und dann Präfixsumme berechnen
  - Blätter sind die Knoten, für die s(<p(v),v>) = <v,p(v)>