84
Henneberg- Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Embed Size (px)

Citation preview

Page 1: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Henneberg-Konstruktion

in O(n²)Konstruktion von Laman-Graphen mittels

Rot-Schwarz-Hierarchien

Marko Walther WS 07/08

Page 2: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Überblick

1. Grundlagen und Definitionen2. Die Rot-Schwarz-Hierarchie (RSH)3. Charakterisierung von Laman-Graphen

mittels der RSH4. Berechnung der Henneberg-Konstruktion

mittels der RSH in O(n²)

Page 3: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

1. Grundlagen

Page 4: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 1(Charakterisierung von Laman-Graphen):Ein Graph G(V,E) heißt Laman-Graph genau dann, wenn:

I. II.

2 3E V

2 3 für jeden Untergraphen

, von

E V

G V E G

Page 5: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 2 (Henneberg):

Ein Graph ist genau dann ein Laman-Graph,wenn für ihn eine Henneberg-Konstruktionexistiert.

Page 6: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 3 (Lovász und Yemini):Ein Graph G(V,E) mit n Ecken und 2n-3Kanten ist ein Laman-Graph genau dann, wennfür jede Kante e aus E der Multigraph G+e, derdurch Hinzufügen einer Kante parallel zu eentsteht, die Vereinigung von zweikantendisjunkten Spannbäumen ist.

Page 7: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Definition 1: 3tree2-Partition

1 2 3

,

, ,

i

Eine zulässige eines GraphenG V E ist eine Partition von E in drei Bäume T T T so dass jede Ecke von G zu genau 2 dieser Bäume gehört und kein Teilbaum zweier verschiedener T diese

3tree2 - Partition

lbe Eckenmenge besitzt.

Page 8: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beispiel für 3tree2-Partition:6v

2v5v

1v

4v3v

1 1 2 3 4

2 3 4 5 6

3 2

6

1

5, , , , ,

, , ,

,

V T

V T

V T v v v v

v v v

v

v

v

v

v

Page 9: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 4:

Ein Graph G(V,E) ist ein Laman-Graph genaudann, wenn er eine 3tree2-Partition zulässt.

Page 10: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

2. Die Rot-Schwarz-Hierarchie (RSH)

Page 11: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Definitionen:

,

T T

T

- Sei T ein Baum und sei L T die Menge der Blätter von T.- Sei G V E ein Graph und T= V ,E ein Baum mit ausgezeichneter Wurzel. Zwischen L T und V soll eine 1:1-Abbildung existieren.- Sei :V V u

T Tnd :E V V

Page 12: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Definition: Hierarchie

Eine ist ein Graph

mit Eckenmenge V und

Kantenmenge E .

Hierarchie H G,T,α,β

T

T e

Page 13: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Definition: Hierarchie

1 2

1 2

e= , aus E.

bildet die Kante e auf ,

ab, so dass und Vorfahren in T

von jeweils und jedoch keine

gemeinsamen Vorfahren von und

sind.

Sei u v

e e e

e e

u v

u v

Page 14: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Definition: Hierarchie

1 2Die Knotentiefen von und

seien in T gleich.

folgt sofort, dass keine

Kante in T sein kann.Man nennt von H.

Querkante

e e

Daraus e

e

Page 15: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beispiel: Hierarchie

6v

2v5v

1v

4v3v

1v 2v

3v 4v 5v 6v

e

1 5,e v v

, , ,H G T ,G V E

1v

Page 16: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Definition: Rot-Schwarz-HierarchieEine Rot-Schwarz-Hierarchie ist eineHierarchie welche folgenden 4 Regeln genügt:

Page 17: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

1. Wurzel-Regel:

Die Wurzel von T hat genau zwei Kinder.

Page 18: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

2. Blatt-Regel:

Eine Ecke v von T ist genau dann das einzigeKind seines Elternknotens, wenn v ein Blatt ist.

Page 19: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

3. Querkanten-Regel:

Die Endecken jeder Querkante habendenselben Großelternknoten, jedochunterschiedliche Elternknoten.

Page 20: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

4. Baum-Regel:

Für jede Ecke v aus T bilden die Querkanten,die inzident zu Enkelknoten von v sind einenBaum, der alle Enkel von v verbindet.

Page 21: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Färbung der RSH:

Ecken gerader/ungerader Tiefe werden rot/schwarz eingefärbt.

Kanten können rot oder schwarz gefärbt sein. Querkanten haben die Farbe ihrer

Endpunkte.

Page 22: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beispiel: Rot-Schwarz-Hierarchie

1v 2v

3v 4v 5v 6v

1v 2v

3v 4v 5v 6v

Hierarchie H

Page 23: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

3. Charakterisierung von Laman-Graphen mittels der RSH

Die RSH als Charakterisierung von Laman-Graphen.

Page 24: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Bezeichnungen:

Sei im Folgenden n= V und m= E .

Page 25: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Lemma 5:

Sei G V,E ein Graph für den eine RSH

existiert.Dann ist m 2n - 3.

Page 26: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 5

,

.

H

H

L GP

P = V - L GP

V = L + P + GP

H H

H

Sei H= V ,E eine RSH für G V E .

Sei die Menge der Blätter und sei die Menge derGroßelternknoten in V .

Sei die Menge der restlichen Elternknoten.

Daraus folgt sofort:

Page 27: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

v

v

v

Sei die Menge der Enkel des Knotens v in H.

Sei die Menge der Kanten von

G in H.

GC

E GCGC

Page 28: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 5

v

v v vv GP v GP v GP v GP

vv GP

Nach der Blatt-Regel ist P L n

Durch Aufsummierung der GC ergibt sich:

GC E GC E GC + 1

GC #Querkanten + GP

.

1

GC = m +

H

Es gibt nur 3 Ecken, die keine Enkel sind (die Wurzel und ihre beiden Kinder).

m GC GP V GP L P GP GP n n 3 3 3

H

GP

V = GC + 3

2n - 3

Page 29: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 5

Lemma 5 impliziert auch, dass nicht für jedenGraphen eine RSH existiert.

Page 30: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Lemma 6:

Sei G V,E ein Graph, für den eine RSH existiert.

Sei G V ein durch V V ( V ) induzierter

Untergraph von G mit Kantenmenge E .Dann besitzt G V höchstens k Kanten.

2

2 - 3

Page 31: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis(Skizze): Lemma 6

Die Eckenmenge V definiert einen Teilbaum T in H, dessen Blätter L den Ecken in V entsprechen.Eine Ecke v aus H gehört genau dann zu T , wenn sie auf einem Pfadzwischen zwei Ecken aus L liegt.Sei

H H H = V ,E nun die durch T induzierte Hierarchie.

Für H lässt sich nun analog zum Beweis von Lemma 5 zeigen, dassE 2V 3. Dabei ist zu beachten, dass für H nur noch schwächere Versionen der vier R

SH-Regeln gelten.

Für einen ausführlichen Beweis, siehe [2].

Page 32: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Folgerung aus Lemma 5,6:

Graphen, für die eine RSH existiert sindLaman-Graphen.

Page 33: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 7:

2

Sei G= V,E ein Laman-Graph.

Dann existiert für G eine RSH und diese

kann in O n Zeit konstruiert werden.

Page 34: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Theorem 7

Der Beweis wird hier nicht geführt.

Nur soviel:Die RSH wird konstruiert, indem der Graph G in eine3tree2-Partition zerlegt wird und aus dieser rekursiv dieUnterbäume der Knoten in H sowie die Querkanten erzeugtwerden.

Für einen ausführlichen Beweis, siehe [2].

Page 35: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Laufzeit:

Die 3tree2-Zerlegung kann in O(n²) Zeitkonstruiert werden (siehe [3]).

Die Knoten in H der selben Tiefe werden inO(n) Schritten bearbeitet.

Da die Höhe der RSH O(n) beträgt, folgt eineLaufzeit von O(n²).

Page 36: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Folgerung:

Ein Graph ist genau dann ein Laman-Graph,wenn für ihn eine RSH existiert.

Damit ist die RSH eine weitereCharakterisierung von Laman-Graphen nebender 3tree2-Partitionierung z.B. .

Page 37: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Lemma 8 (Validierung der RSH):Sei H eine Hierarchie für den Graph G.Es kann in O(n) Schritten überprüft werden, obH eine Rot-Schwarz-Hierarchie ist.

Page 38: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 8

Sei H G,T, , die Hierarchie für G V,E .

Als Erstes wird geprüft, ob m 2n - 3.Ansonsten existiert für G keine RSH nach Lemma 5.

Page 39: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 8

Nun wird überprüft, ob H allen 4 Regeln fürRSH genügt.

Page 40: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 8

Die Wurzel-Regel kann in O(1) Zeit überprüftwerden.

Page 41: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 8

Die Blatt-Regel kann für jedes Blatt undjeden inneren Knoten von H überprüft werden.Dafür sind O(n) Schritte notwendig.

Page 42: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 8

1 2

Die Querkanten-Regel kann in O m Zeit

überprüft werden, indem die Großelternknotenvon e und e für jede Kante e aus G

verglichen werden.

Page 43: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Lemma 8

Die Baum-Regel kann in O(m+n) Zeit überprüftwerden.

Es folgt eine Gesamtlaufzeit von O(n).

Page 44: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

4. Berechnung der Henneberg-Konstruktion mittels der RSH in O(n²)

Page 45: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Henneberg-Operationen:

a

b

a

b

v

Henneberg-Einfüge-Operation vom Typ I

Page 46: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Henneberg-Operationen:

Henneberg-Einfüge-Operation vom Typ II

a

b

a

b

v

Page 47: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Henneberg-Operationen:

Die inversen Operationen werden Henneberg-Lösch-Operationen vom Typ I bzw. Typ II genannt.

Page 48: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 9:

Sei G V,E ein Laman-Graph mit mindestens 3Ecken und sei H eine RSH für G. Durch Ausführung einer Henneberg LöschOperation wird G in G V ,E überführt. Für G kann eine RSH aus H konstruiert werden, in

dem höchstens konstant viele Ecken und Kanten aus H gelöscht bzw. zu H hinzugefügtwerden.

Page 49: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis(Vorbemerkungen): Theorem 9

x

Sei H G,T, , eine RSH.

Sei der Teilbaum von T mit Wurzel x T.

Sei die Menge der Enkel eines Knotens x T und der Baum, der durch die GC in H induziert wird, sei .

x

x

x

T

GC

GT

Page 50: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis(Vorbemerkungen): Theorem 9Nach [1] enthält G eine Ecke vom Grad 2 oder 3.

Page 51: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Theorem 9

Der Beweis unterscheidet 4 Fälle.

Fall 1 und Fall 3 werden ausführlich bewiesen,um die Vorgehensweise aufzuzeigen.

Fall 1, 2 entsprechen einer Typ I Lösch-Operation,Fall 3, 4 einer Typ II Lösch-Operation.

Page 52: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 1, 2:

Sei v eine Ecke vom Grad 2 und seien a, b die zwei zu v adjazenten Ecken.

a

b

v

Page 53: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 1:

Nach

Sei

Definition der RSH besitzt v einenGroßelternknoten . Sei der Elternknoten von v.Nach der Querkanten-Regel ist weder w noch u adjazentzu einer Querkante in H.

w nun die Wurzel von T.

w u

w

u

v

Ausschnitt aus H:

Page 54: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 1:

v

Nach

ist nun inzident zu genau 2 Querkanten v,a und v,b ,

welche den Kanten v,a und v,b in G entsprechen.

Sei nun der zweite Kindknoten von w.(er existiert nach der Wurzel-Regel)

der Querkanten-Reg

s

el ist u nicht der Elternknotenvon a und b . Dieser kann also nur s sein.

Page 55: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 1:

b

w

u

v

s

a

aT bT

a b

Page 56: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 1:

Durch eine Henneberg-Lösch-Operation vom Typ I wirddie Ecke v sowie die Kanten v,a und v,b aus G

gelöscht.

In H entspricht das dem Löschen der Knoten u,v und w sowie der zu ihnen inzidenten Kanten.

Die resultierende RSH H erfüllt danach immer noch alle 4 Regeln.

Page 57: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 1:

b

w

u

v

s

a

aT bT

a b

b

s

a

aT bT

a b

a

b

v

a

b

Page 58: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 2:

w ist nicht die Wurzel von T.Für einen Beweis siehe [2].

Page 59: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3,4:

Sei v eine Ecke vom Grad 3 und seien a, b, c die drei zu v adjazenten Ecken.

a

b

vc

Page 60: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3,4:

Es wird nun immer die Kante e ermittelt, die bei der Lösch-Operation vom Typ II hinzugefügt werden soll:

a

b

a

b

v ce c

Page 61: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3:

w (der Großelternknoten von v) hat zwei Kinder.

Page 62: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3:

Seien im Folgenden die Knoten a , b und c aus T Vorfahren der Ecken a,b und c aus G.

V habe einen Ur-Ur-Großelternknoten .

Sei v ,c die Querkante in H, die der Kante v,c

in G entspricht.Nach der Bau

x

m-Regel ist a inzident zu mindestens

einer Querkante. Sei diese v,a .

Page 63: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3:

Es werden ansonsten die selben Bezeichnungen wie in Fall 1 benutzt.

Nach der Baum-Regel ist u(Elternknoten von v) inzident zumindestens einer Querkante, z.B. u,b in T, welche der

Kante u,b in G entspr

icht.

Page 64: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3:

3 Spezialfälle werden unterschieden:

3a: s habe zwei Kinder a und c .

3b: s habe ein Kind a und v = u.

3c: s habe ein Kind a und v ist ein anderer Vorfahr von v.

Page 65: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3a:

S habe nun 2 Kinder: a und c .Daraus folgt, dass v auch inzident zur Querkante v,c in T sein muss.

x

bT

w

u

v=v‘

s

a‘ c‘

b‘

aT cT

Ausschnitt aus H für Fall 3:

Page 66: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3a:

cT

x

a c

a

c

Sei nun der Pfad von s nach b in GT .

Sei s,y die erste Kante auf diesem Pfad und

(z,y) die zugehörige Kante in G.y liegt nun entweder in T oder T .

Liegt y in T , so ist e a,b .

Liegt y in T ,

so ist e b,c .

x

w

u

v

s

a‘ c‘

b‘

aT

cT

yT

y‘

y

Page 67: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3a:

Diese Prozedur wird als„Vervollständigung des Baumes vom Typ I“genannt.

Page 68: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3a:

2. u und v und alle zu ihnen inzidenten Kanten werden entfernt.3. a‘ und c‘ werden zu Kindern von w.

x

bT

w

u

v

s

a‘ c‘

b‘

aT cT

x

bT

w

a‘ c‘ b‘

aT cT

Page 69: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3:

4. Für jede Querkante s,y und zugehörige Kante z,y

in G wird eine neue Querkante, entweder a ,y

oder c ,y erstellt.

Um zu entscheiden, welche von beiden, wird das Blatt z in einen de

a cr beiden Bäume T oder T gesucht.

Page 70: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3a:

5.Füge e in G und die zugehörige Querkante e

in H ein.

Ist e a,b , dann e a ,b ,

sonst e b ,c .

Page 71: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3b:

s habe ein Kind a und v = u.

x

bT

w

u=v‘

v

s

a‘=a

c‘b‘

cT

Page 72: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3b:

1. u und v und alle zu ihnen inzidenten Kanten werden entfernt.2. s wird durch das Blatt a ersetzt.

Page 73: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3b:

x b c

b c

3. u wird aus GT entfernt. Durch Entfernen von u zerfällt GT in zwei Bäume und , so dass b in und c in enthalten sind. s muss in einer dieser Bäume enthalten sein.

bT

w

u=v‘s c‘b‘

cT

cb

v a=a‘

Page 74: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3b:

bIst s dann wird e auf a,c gesetzt. Sonst auf a,b .

Diese Prozedur wird "Vervollständigung des Baumes vom Typ II" genannt.

x

bT

w

u

v

s

a

c‘b‘

cT

x

bT

w

a c‘b‘

cT

Page 75: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3c:

s habe ein Kind a und v sei ein Vorfahr von v u.

x

bT

w=v‘

u

v

s

a‘=a

c‘

b‘

cT

Page 76: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3c:

1. u und v und alle zu ihnen inzidenten Kanten werden entfernt.2. s wird durch das Blatt a ersetzt.

Page 77: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3c:

3. Die Kante e a,c wird in G eingefügt, welche der

Kante v ,c in T entspricht.

x

bT

w=v‘

u

v

s

a‘=a

c‘

b‘

cT

x

bT

w

a

c‘

b‘

cT

Page 78: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 3:

In den Fällen 3a, 3b und 3c genügt dieresultierende RSH wieder allen 4 Regeln.

Page 79: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Fall 4:

w hat mehr als zwei Kinder.Für einen Beweis siehe [2].

Page 80: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 9:

Die vorherigen 4 Fälle reichen aus.

Page 81: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 9:

Denn angenommen, keiner der vorherigen 4 Fälle kann angewendetwerden.Dann beträgt der Grad jeder Ecke aus G mindestens 3.

Da es 2n-3 Kanten gibt, existieren mind. 6 Ecken in H mit Grad 3.(sieht man durch Konstruktion eines solchen Graphen).

Nach der Wurzel-Regel existiert ein Kindknoten u der Wurzel von T, sodass mind. 3 Ecken vom Grad 3 Nachfahren von u sind.

Der Großelternknoten kann nach der Blatt-Regel nicht die Wurzel sein.Also greift hier Fall 3 oder 4.

Page 82: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Theorem 10:

Die Henneberg-Konstruktion eines Laman-Graphen mit n Ecken kann in O(n²) ZeitBerechnet werden.

Page 83: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Beweis: Theorem 10

Es wird eine RSH für den Graphen mit dem Algorithmus aus Theorem 7 in O(n²) Zeit konstruiert.

Mit dem Algorithmus aus Theorem 9 kann eine Lösch-Operation inO(n) Zeit berechnet werden.

Da O(n) Lösch-Operationen nötig sind,folgt daraus die Behauptung.

Page 84: Henneberg-Konstruktion in O(n²) Konstruktion von Laman-Graphen mittels Rot-Schwarz-Hierarchien Marko Walther WS 07/08

Quellen: [1]

R. Haas, D. Orden, G. Rote, F. Santos, B. Servatius, H. Servatius, I. Streinu, D. Souvaine and W. Whiteley. Planar minimally rigid graphs and pseudo-triangulations. Comput. Geom. Theory Appl., 31(1-2):31-61, 2005, http://dx.doi.org/10.1016/j.comgeo.2004.07.003.

[2]Henneberg-Aufbau in O(n²) Schritten:S. Bereg. Certifying and constructing minimally rigid graphs in the plane. In Proc. 21st Annu. Sympos. Comput. Geom., pages 73-80, 2005.

[3]A.R.Berg und T.Jordan. Algorithms for graph rigidity and scene analysis. In 11th European Symp. on Algorithms, LNCS 2832, pp. 78-89. Springer-Verlag, 2003.