Strukturen • Motivation• Definition von Theta-Graph• Beispiel nach der Definition• Eingenschafen von Theta-Graph• Implemetierungsalgorithmus von Theta-Graph • Beispiel nach des Algorithmus• Definition des Spanners• Theta-Graph ist Spanner• Beweis• Folgerung
Motivation
•Realisierung Spanner (approximativ vollständiger Graph)
•Entwicklung der Approximationsalgorithmen oder in der Heuristik
Definition von Theta-Graph• Theta-Graph In Fläche um jeden Knote in Sektoren von
Koordinatesystem mit dem örtlichfestgelegten Winkel und schließen den Knote an den nächsten Nachbar in jedem Sektor
Eingenschafen von Theta-Graph
• = ,wobei k ist eine Ganzzahl(k > 8) • Jeder Knoten hat höchsten k Kanten • Im allgemeinen hat ein Knoten Typ i Kanten wobei 1<=i<=k und
der winkel von eine kante und x-coordinate ist.
2k
2 ( 1) 2i ik k
Implemetierungsalgorithmus von Theta-Graph
• Methode Man findet alle Kanten nach Typ i (zuerste ist
Typ1 , dann ist Typ2 , usw.) für jede Knote.• Defintion Drei Ordnungen : In jeder Ordnung
werden die Knoten durch die Einrichtung ihrer Projektionen auf die orientierte Linie georgernet,die durch den Nullpunkt einen Winkel von mit der X-Achse bildet.
, ,
• ImplemetierungsAlgrorithmus 1) Insert point p into table T. 2) If p has a predecessor q in T then report that pq is a type i edge. 3) Repeat Forver If p has a successor r in T then If (r) > (p) then delete r from T else exit loop
Bemerkung: 1) Abtastung in unaufsteigender Ordnung 2) Am Anfang ist Tablle T leer 3) Nach Ordnung stecketet die neue Knote ein
Implemetierungsalgorithmus von Theta-Graph
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
a
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
a
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
a
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
c a
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
c a
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
c a
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
c b a
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
c b a bc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
c b (a) bc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
c d b (a) bc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
c d b (a) bc,dc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
c d b (a) bc,dc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
g c d b (a) bc,dc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
g c d b (a) bc,dc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
g c d b (a) bc,dc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
g c d e b (a) bc,dc,
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
g c d e b (a) bc,dc,ed
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
g c d e (b) (a) bc,dc,ed
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
g c f d e (b) (a) bc,dc,ed
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
g c f d e (b) (a) bc,dc,ed,fc
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
g c f d e (b) (a) bc,dc,ed,fc
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
g h c f d e (b) (a) bc,dc,ed,fc
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
g h c f d e (b) (a) bc,dc,ed,fc,hg
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
g h (c) f d e (b) (a) bc,dc,ed,fc,hg
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
i g h (c) f d e (b) (a) bc,dc,ed,fc,hg
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
i g h (c) f d e (b) (a) bc,dc,ed,fc,hg
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Beispiel Nach Implemetierungsalgorithmus
Knoten Kanten(Typ 1)
i (g) h (c) f d e (b) (a) bc,dc,ed,fc,hg
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
i (g) h j (c) f d e (b) (a) bc,dc,ed,fc,hg
Beispiel Nach Implemetierungsalgorithmus
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
i (g) h j (c) f d e (b) (a) bc,dc,ed,fc,hg,jh
= {e,b,a,j,d,f,h,c,i,g} = {a,c,b,d,g,e,f,h,i,j} = {i,g,h,j,c,f,d,e,b,a}
Knoten Kanten(Typ 1)
i (g) h j (c) (f) (d) e (b) (a) bc,dc,ed,fc,hg,jh
Beispiel Nach Implemetierungsalgorithmus
Definition des Spanners
• Difintion p,q= zwei beliebige konten in graph G d(p,q)=euklidische distanz G(p,q)=länge eines kürzesten wegs in graph G• Spanner Spanner ist ein Subgraph von G und im Spanner ist
der Maximalwert des Verhältnisse G(p,q) / d(p,q) in konstantem Rahmen.
Theta-Graph ist Spanner
• Definiton : Länge eines kürzesten Wegs von p bis q in theta-
graph m: die Anzahl von Knoten in d(p,q) : euklidische distanz• Lemma Wenn es ein kürzesten Weg von p bis q in Theta-graph ,
(k ist eine Ganzzahl und k > 8 ) gibt, und der
Weg fährt über m Knoten durch,dann
( , )p q
2k
( , )p q
( , ) 1 tan 1 tan( , ) cos tan 1
mmp q
d p q
Beweis des Lemmas
• Methode durch Induktionsbeweis• Definition : n-te Knoten im Weg von p bis q in theta-
graph ( 0<=i<=m ),davon : Länge eines kürzesten Wegs von p bis
q in theta-graph
: Länge eines Wegs p bis q in theta-graph mit solche Beschränkung:
ns
( , )p q0s p
/ ( , )p q
Beschränkung für : Wenn der Winkel von und x-achse ist d.h ist ein Kanten von Typ i ,dann ist die Kanten von auch Typ i
Offenbar:
Beweis des Lemmas
/ ( , )p q
ns q 2 ( 1) 2i i
k k
ns q
1n ns s
/( , ) ( , )q qp p
/ ( , )p q( , )p q
( , )d p q
Falls wir
bewiesen haben , dann gilt auch
Beweis des Lemmas
( , ) 1 tan 1 tan( , ) cos tan 1
mmp q
d p q
/ ( , )p q( , )p q
( , )d p q
/ ( , ) 1 tan 1 tan( , ) cos tan 1
mmp q
d p q
1) Wenn m=0 ist , dann ist ;
2)Annahme: ist richtig
Claim: Verhältnis hat Maximumswert,genau
dann wenn (a) q im x-achse ist (b) der Winkel von und x-achse maximal ( ) hat
Beweis des Lemmas
/ ( , ) ( , )p q d p q
/ 11( , ) 1 tan 1 tan
( , ) cos tan 1
mmp q
d p q
/ ( , )( , )p q
d p q
1ps
20k
Setzt in p ein =>
=> und
=>
Beweis des Claims
1/ 1
1 11 tan 1( , ) ( , ) tan
cos tan 1
mms q d s q
/ 11( , ) 1 tan 1 tan
( , ) cos tan 1
mmp q
d p q
/ 111
1
( , ) 1 tan 1 tan( , ) cos tan 1
mms q
d s q
1s
/ / /1 1( , ) ( , ) ( , )p q p s s q /
1 1( , ) ( , )p s d p s
1/ 1
1 11 tan 1( , ) ( , ) ( , ) tan
cos tan 1
mmp q d p s d s q
( , )p q/ ( , )p q( , )d p q
q und werden sich im beschränkte Rahmen
( )beweget,aber die Verhältnis wird nicht weniger ,d.h. und werden nicht weniger ,und
wird sich nicht erhöht.
Beweis des Claims1
/ 11 1
1 tan 1( , ) ( , ) ( , ) tancos tan 1
mmp q d p s d s q
1s/ ( , )( , )p q
d p q
1( , )d p s 1( , )d s q
20k
( , )d p q
Falls < ist ,dann müssen wir und umtauschen ,dann werden und nicht weniger ,und wird sich nicht erhöht,wenn q sich um ins x-achse dreht.
=>
Beweis des Claims
1( , )d p s 1( , )d s q( , )d p q
1s
1( , )d s q
/ ( , )p q
( , )d p q
1( , )neu d s q1( , )alt d s q
1( , )neu d p s1( , )alt d p s
( , )neu d p q( , )alt d p q
(a) q ist im x-achse
Beweis des Claims
wenn q sich um ins x-achse dreht, ändern und nicht,und > => wird sich nicht erhöht. D.h wenn q im x-achse ist,dann ist minimal .
1( , )d p s
1( , )d s q
( , )d p q
( , )d p q
1s1( , )neu d s q
1( , )alt d s q1( , )neu d p s
1( , )alt d p s( , )neu d p q
( , )alt d p q
(b) der Winkel von und x-achse maximal ( ) hat
Beweis des Claims
20k
Wenn sich entlang y-coordinate beweget ,dann wird vergrössert
aber , und werden sich erhöht,aber ändert nicht D.h.wenn ist ,dann ist
maximal.
1s
20k
( , )d p q1( , )d s q
1( , )d p s
2k
1( , )d p s
1( , )neu d s q1( , )alt d s q
1( , )neu d p s1( , )alt d p s
( , )neu d p q( , )alt d p q
=>
Nach Claim,ist und ist
minimal und ist maximal.=>
Beweis des Lemmas
1( , )0 ( , )cosd p qd p s
( , )d p q
1( , )d p s
1( , ) ( , ) tand s q d p q
1( , )neu d s q1( , )alt d s q
1( , )neu d p s1( , )alt d p s
( , )neu d p q( , )alt d p q
1( , )neu d s q1( , )alt d s q
1( , )neu d p s1( , )alt d p s
( , )neu d p q( , )alt d p q
3)
Setzt und ein
=>
=>
=>
Beweis des Lemmas1
/ 11 1
1 tan 1( , ) ( , ) ( , ) tancos tan 1
mmp q d p s d s q
1( , )0 ( , )cosd p qd p s
1( , ) ( , ) tand s q d p q
1/ 1( , ) 1 tan 1( , ) ( , ) tan tan
cos cos tan 1
mmd p qp q d p q
/ 11( , ) 1 1 tan 1tan tan
( , ) cos cos tan 1
mmp q
d p q
/ 1
1( , ) 1 1 tan 1tan tan( , ) cos cos tan 1
mmp q
d p q
=>
=>=>
=>
=>
Beweis des Lemmas/ ( , ) 1 tan tan tan( , ) cos cos (tan 1)
mmp q
d p q
/ ( , ) (tan 1) tan tan tan( , ) cos (tan 1) cos (tan 1)
mmp q
d p q
/ ( , ) tan 1 tan tan tan( , ) cos (tan 1)
mmp q
d p q
/ ( , ) tan 1 tan( , ) cos (tan 1)
mmp q
d p q
/ ( , ) 1 tan 1 tan( , ) cos tan 1
mmp q
d p q
Folgerung
Wenn im theta-graph ist und k>8 , dann ist
,deshalb ist Verhältnisse
=B
( , ) 1 1( , ) cos 1 tanp q
d p q
m
tan 1
k B10 4.52
15 1.97
20 1.56
25 1.39
30 1.30
35 1.24
40 1.20