Algorithmen und Komplexitätstheorie

Vorwort

Allgemeines

Dieses Dokument, erstellt mit L ^A T E X, hat das Ziel, den Leser bei der Vorbereitung f¨ ur die Informatik-Diplompr¨ ufung, Bereich Theorie (A), bei Prof. Dr. T. Lengauer zu unterst¨ utzen.

Wir haben sowohl die Vorlesung als auch die angegebene Literatur um von uns erarbeitete Gedanken erweitert. Diese sind beidseitig einger¨ uckt und daher leicht vom restlichen Text zu unterscheiden. Wir ubernehmen nat¨ urlich keine Garantie f¨ ur die Richtigkeit oder Vollst¨ andigkeit unserer ¨ Uberlegungen oder ¨

des aufgef¨ uhrten Stoffes. Wir empfehlen außerdem den Besuch der Vorlesungen Prof. Lengauers, d.h. es ist unserer Meinung nach nicht ratsam, dieses Skript als alleinige Pr¨ ufungsvorbereitung zu verwenden. Trotz des hohen Schwierigkeitsgrades halten wir die Vorlesungen f¨ ur eine gute Wahl, was den A-Bereich anbetrifft, da die Vorlesungen von Prof. Lengauer meist sehr praxisorientiert sind (f¨ ur eine A-Vorlesung). Die vorgestellten Konzepte finden durchaus auch in der Praxis Verwendung.

Prof. Lengauer selber ist in keinster Weise an der Erstellung dieses Skriptes beteiligt. Ihn auf eventuelle Fehler hinzuweisen ist unn¨ otig und sinnlos. Alle noch vorhandenen Fehler sind uns zuzuschreiben.

Zu den Vorlesungen

Dieses Skript basiert zum einen auf der Literatur zu ” Algorithmen“ und dieser Vorlesung selber sowie den Literaturangaben zu der Vorlesung ” Komplexit¨ atstheorie“ und dieser Vorlesung selber. Die Vorlesung ” Algorithmen“ wurde im SS 1999 gehalten. Die Basis f¨ ur den gr¨ oßten Teil der Vorlesung bildete dabei ein neues Werk von Mehlhorn und N¨ aher. Diese haben eine Bibliothek (LEDA) ins Leben gerufen, die umfangreiche und effiziente Algorithmen bereith¨ alt. Ausgiebige Hinweise, Links und Ressourcen finden sich auf der Homepage von Prof. Lengauer ¹ . Die Vorlesung ” Komplexit¨ atstheorie“ wurde von Prof. Lengauer im SS 2000 wieder gelesen; er hat dazu die benutzte Literatur modifiziert, die Vorlesung basiert nun nicht mehr ausschließlich auf dem Reischuk sondern mehr auf Papadimitriou. Die Vorlesung, und damit auch unsere Ausarbeitung, ist also nicht mehr kompatibel und vergleichbar in Hinsicht zu fr¨ uheren Pr¨ ufungen! Auch zu dieser Vorlesung finden sich reichliche Ressourcen auf der Homepage von Prof. Lengauer. Prof. Lengauer hat dabei die Vorlesung so konzipiert, daß sie als ” roter Faden“ f¨ ur eine Lekt¨ ure des Buches dient. Die Konsequenz hierbei ist, daß f¨ ur eine Pr¨ ufung eine Absch¨ atzung erfolgen muß, welche Teile des Buches wichtig bzw. relevant sind und welche eben nicht. Auch wir haben uns hier zu einigen K¨ urzungen entschlossen, insbesondere im Bereich der Logik ² .

Bei der Nutzung des Skriptes sollte man sich diese Tatsachen stets vor Augen halten!

¹ http://www.cs.bonn.edu/fgl

² Im Papadimitriou wird die Logik umfassend aber daf¨ ur recht kurz behandelt. Will man den angeschnittenen Stoff in seinem ganzen Umfang verstehen, ist der Besuch einer dedizierten Logik-Vorlesung zu empfehlen.

Gliederung

Die Gliederung dieses Dokuments richtet sich in erster Linie nach der Vorlesung bzw. der Literatur. Dies erleichtert es, die entsprechenden Stellen aufzufinden und nachzulesen. Wir haben jedoch an einigen Stellen den Stoff innerhalb eines Abschnittes neu gegliedert, um ein leichteres Verst¨ andnis zu erm¨ oglichen. Einige Aspekte des behandelten Stoffes haben wir in einen Appendix verschoben, es handelt sich hier um Stoff, der als Basis f¨ ur eine gewisse Thematik dient und nicht explizit in der Vorlesung behandelt wurde. Dies ist jedoch die Ausnahme und bezieht sich nicht auf Relevantes sondern auf Definitionen, die als Basis f¨ ur z.B. eine Datenstruktur dienen.

Vorbereitung

Wir halten die A-Pr¨ ufung bei Prof. Lengauer f¨ ur eine der anspruchsvollsten Pr¨ ufungen ¨ uberhaupt! Man

sollte keinesfalls den Fehler begehen und diese Pr¨ ufung untersch¨ atzen. Selbst eine mehrmonatige intensive Vorbereitung ist keine Garantie f¨ ur eine gute Note. Vielmehr ist eine optimale Vorbereitung das, was Prof. Lengauer erwartet. Dementsprechend ist es nahezu nicht m¨ oglich, eine 1.0 bei ihm zu erreichen; er setzt dazu einiges an Wissen voraus, das ¨ uber den Stoff der Vorlesung hinausgeht.

Dieses Skript soll deshalb nicht als ” Lerntext“ verstanden werden, der es erm¨ oglicht, ohne Vorkenntnisse

den Stoff auswendig zu lernen und die Pr¨ ufung (gut) zu bestehen. Es entstand aus der Motivation, die Erkenntnisse, die sich nach einem intensiven Durcharbeiten des Stoffes ergaben, festzuhalten und sie zu konservieren. Das Ziel war es, f¨ ur den Zeitpunkt des Auswendiglernens eine optimale St¨ utze zu haben, damit es nicht n¨ otig ist, sich alle Zusammenh¨ ange erneut herleiten zu m¨ ussen.

Nutzung

Um zuk¨ unftigen Generationen etwas ” Wertvolles“ zu hinterlassen, haben wir uns entschlossen dieses Skript zu ver¨ offentlichen. Dazu m¨ ochten wir aber auch noch einige Aspekte betonen:

1. Die Nutzung erfolgt auf eigene Gefahr. Wir ¨ ubernehmen keinerlei Garantie f¨ ur die Vollst¨ andigkeit

des Stoffes oder gar die Korrektheit des vorhandenen Stoffes. Tritt eine inhaltliche Diskrepanz zwischen Literatur oder ¨ ahnlich guten Quellen und unserem Skript auf, ist in der Regel das Skript zu bem¨ angeln.

2. Wir w¨ unschen uns eine freie Nutzung des Skripts. Das heißt im Speziellen, daß wir keine Anspr¨ uche irgendeiner Art erheben. Im Generellen w¨ unschen wir uns außerdem, daß auch nachfolgende Nutzer dieses Skripts keinen kommerziellen Nutzen irgendeiner Art aus diesem Skript ziehen.

3. Wir w¨ aren erfreut dar¨ uber, w¨ urde sich jemand finden, der dieses Skript perfektioniert. Insbesondere suboptimal“. F¨ ur eine eventuelle ¨ der Komplexit¨ atstheorie-Teil ist ” Uberarbeitung haben wir noch einige Vorschl¨ age:

(a) Es sollte klargemacht werden, worin eventuelle ¨ Anderungen bestehen; z.B. durch geeignete

Kommentare in einem Vorwort. Dies soll es Nutzern gestatten, sich ¨ uber den Stand des Skriptes

zu informieren und zu sehen, welche Version vorliegt.

(b) Die ¨ uberarbeitete Version sollte wieder frei und kostenlos zug¨ anglich f¨ ur alle Interessenten sein, also den hier geschilderten Punkten sinngem¨ ass folgen.

(c) Wir m¨ ochten nicht, daß zu diesem Skript beitragende Autoren in ihrer Erw¨ ahnung ¨ ubergangen werden.

(d) Der L ^A T E X– Sourcecode“ ist von uns, unter den angegebenen Email-Adressen, erh¨ altlich. Nach-”

folgende Autoren sollten ihn ebenfalls verf¨ ugbar halten. (e) Zuk¨ unftige Coautoren m¨ ochten wir bitten, uns nach einer ¨ Uberarbeitung eine Version des Skriptes zukommen zu lassen.

Danksagung

Wir m¨ ochten allen, die uns bei Erstellung dieses Skripts unterst¨ utzt haben ” Danke“ sagen. Dies betrifft

insbesondere Nicolas Andree, der uns beim T E Xen des Stoffes und Ka Lok To, der uns bei der Besprechung tatkr¨ aftig zu Seite stand.

Letzte Worte

Wir w¨ unschen jedem, der sich auf eine Pr¨ ufung bei Prof. Lengauer vorbereitet, viel Erfolg und eine geh¨ orige Portion Gl¨ uck. Wir hoffen, daß dieses Dokument seinen Teil dazu beitr¨ agt, die Schwierigkeiten auf dem Weg dorthin zu ¨ uberwinden.

Inhaltsverzeichnis

  I Algorithmen  1

1  Graphen  3

1.1  Grundlegende Notationen  3

1.2  Speicherung von Graphen  4

1.2.1  Adjazenzmatrix  4

1.2.2  Knoten-Kanten Inzidenzmatrix  5

1.2.3  Adjazenzliste  5

1.3  Graphenisomorphie  5

1.4  Planarit at  5

1.5  B aume  6

1.6  Zusammenhang  6

1.6.1  Schwacher Zusammenhang  6

1.6.2  Starker Zusammenhang  7

1.6.3  Zweifacher Zusammenhang  7

1.6.4  k -facher Zusammenhang  8

1.7  Depth-First Search  8

1.7.1  Laufzeit  10

1.7.2  Struktur des DFS  10

1.7.3  Anwendung des DFS  11

1.8  k urzeste Wege in Graphen  14

1.8.1  Historie  14

1.8.2  Beschreibung des Problems  14

1.8.3  Ein generischer Algorithmus  16

1.8.4  Single-Pair  21

1.8.5  Bellmann-Ford Algorithmus  21

1.8.6  All Pairs  23

1.8.7  K urzeste Wege mit Adjazenzmatrizen  24

1.9  Minimale Spannb aume  27

1.9.1  Generischer Algorithmus  28

1.9.2  Algorithmus von Borˆ uvka  29

1.9.3  Algorithmus von Prim  29

1.9.4  Algorithmus von Kruskal  29

1.10  Matching in Graphen  30

1.10.1  Bipartite Graphen  33

1.10.2  Ein Checker“ f ur Maximum Matchings  35

1.11  Netzwerkfl usse  36

1.11.1  Residuales Netzwerk  38

i

2  Geometrie  44

2.1  Konvexe H ulle  44

2.1.1  Deterministische Konstruktion (per SweepLine)  44

2.1.2  Zuf allige inkrementelle Konstruktion  46

2.1.3  Breite einer Punktemenge  46

2.2  Triangulierungen  47

2.2.1  Einige Grundbegriffe  47

2.2.2  Triangulierung per Plane Sweep  48

2.3  Die Delaunay-Triangulierung  48

2.3.1  Der Flipping Algorithmus  48

2.3.2  Voronoi-Diagramme  48

2.4  Segmentschnitte  49

2.4.1  Problembeschreibung  49

2.4.2  Test auf Linienschnitte  50

2.4.3  SweepLine Algorithmus zu Segmentschnitten  50

  II Komplexit atstheorie  51

3  Einleitung  53

3.1  Historie Motivation  53

3.1.1  Messen von Ressourcen  54

4  Turingmaschinen  56

4.1  Allgemeines  56

4.2  Turingmaschinen als Algorithmen  57

4.3  Linearer Speedup  59

4.4  Aufwand beim Akzeptieren der Palindromsprachen  59

4.4.1  Zeitabsch atzung f ur 1 String Akzeptoren  59

4.4.2  Speicherplatz der Palindromsprache  61

4.5  Die Registermaschine (Random Access Machine)  61

4.5.1  Einf uhrung der RAM  61

4.5.2  M achtigkeit der RAM  62

4.6  Nichtdeterminismus  63

4.6.1  Intuition  64

5  Unentscheidbarkeit  66

5.1  Halteproblem  66

5.2  Abgeschlossenheit  67

5.3  Rekursive Trennbarkeit  68

6  Aussagenlogik  69

6.1  Erf ullbarkeit Wahrheit  70

6.2  Logik Funktionen  70

7  Logik erster Stufe  72

7.1  Syntax  72

7.2  Semantik  73

7.3  Modelle f ur die Zahlentheorie  73

7.4  G ultige S atze  73

7.5  Konsistenz der Logik erster Ordnung  74

7.5.1  Mechanisierte Beweistechniken  74

7.5.2  G odelscher Vollst andigkeitssatz  75

7.5.3  Konsequenzen aus G odels Vollst andigkeitssatz  76

7.5.4  Verbindung zwischen Logik Komplexit at bei Graphen  76

ii

7.5.5  Logik 2. Ordnung  77

8  Unentscheidbarkeit in der Logik  79

8.1  Berechnung als zahlentheoretisches Konzept  79

9  Beziehungen zwischen Komplexit atsklassen  81

9.1  Komplexit atsklassen  81

9.1.1  Komplexit atsklassen  82

9.1.2  Komplemente nichtdeterministischer Klassen  82

9.2  Hierarchies atze  82

9.3  Erreichbarkeitsmethode  83

9.3.1  Nichtdeterministischer Platz  84

10  Reduktion und Vollst andigkeit  86

10.1  Reduktion  86

10.2  Vollst andigkeit  88

10.2.1  Die Tabellenmethode  88

10.3  Charakterisierung mittels Logik  90

11  N P-vollst andige Probleme  91

11.1  Varianten von SAT  91

11.1.1  Komplexit at von 2SAT  92

11.2  Varianten von 2SAT  93

11.3  Graphenprobleme  94

11.4  Zahlenprobleme  95

11.4.1  Das KNAPSACK-Problem  96

12  coN P und Funktionsprobleme  98

12.1  PRIMES  99

12.2  Function Problems  99

13  Randomisierte Berechnungen  102

13.1  Randomisierte Algorithmen  102

13.1.1  Symbolische Determinanten  102

13.1.2  Random Walks  103

13.2  Randomisierte Komplexit atsklassen  104

13.2.1  Die Klasse ZPP  105

13.2.2  Die Klasse PP  106

13.2.3  Die Klasse BPP  106

13.3  Zufallsgeneratoren  107

13.3.1  Eingeschr ankte Zufallsgeneratoren  108

13.4  Schaltkreiskomplexit at  109

14  Kryptographie  112

14.1  Public Key-Kryptographie  113

14.1.1  Kandidaten f ur One-Way Funktionen  114

14.2  Kryptographie und Komplexit at  114

14.3  Interaktives Beweisen  115

14.3.1  Einf uhrung  115

14.3.2  Klassifikation  115

14.4  Zero Knowledge  117

14.4.1  Das Zero Knowledge Protokoll  117

iii

15  Approximierbarkeit  119

15.1  Approximationsalgorithmen  119

15.1.1  Beispiele  120

15.2  Polyzeit Approximationsschema  126

15.3  Vollst andigkeit bei Approximationsalgorithmen  126

15.3.1  Die L-Reduktion  127

15.3.2  Die Klasse MAX SN P  128

15.3.3  Vollst andigkeit in MAX SN P  129

16  P vs. N P  130

16.1  Was ist zwischen P und N PC?  130

16.2  Beweise f ur P N P?  130

17  Parallelit at  132

17.1  Beispiel-Algorithmen  132

17.1.1  Matrizenmultiplikation  132

17.1.2  Graph Reachability  133

17.2  Pr afix-Summen Berechnung  134

17.2.1  Determinanten  134

17.2.2  Max Flow  134

17.3  Parallele Maschinenmodelle  134

17.3.1  Boolesche Schaltkreise  134

17.3.2  Parallele RAMs  135

17.3.3  Uniforme PRAM’s  135

17.3.4  Kritik  136

17.4  Die Klasse N C  137

17.4.1  P Vollst andigkeit  137

17.4.2  RN C  140

18  Logarithmischer Platzverbrauch  141

  ?  

18.1  L N L  141

18.2  Alternierung  142

18.2.1  Die Klasse DP  144

19  Polynomielle Hierarchie  146

  III Anhang  149

  A Datenstrukturen  151

  A 1 Heaps  151

  A 2 Union-Find  151

  A 3 Rot-Schwarz und 2 3 4 B aume  152

  A 3 1 2 3 4 B aume  152

  A 3 2 RS-B aume  152

  B Sonstiges  153

  B 1 Ackermann-Funktion  153

  B 2 Steinerbaum-Problem  153

iv

C Beweis-Ideen 155

C.1 Reduktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 C.2 N L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 C.3 N L-Vollst¨ andigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 C.4 P-Vollst¨ andigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 C.5 N P-Vollst¨ andigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 C.6 Approximationsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

Verzeichnisse 162

Abbildungsverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 Listingverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

v

Algorithmen

Kapitel 1

Graphen

1.1 Grundlegende Notationen

Sprechweisen:

Definition. Ein Graph G = (V, E) ist ein 2-Tupel aus eine Menge V von Knoten, ¨ uber der eine zweistellige Relation, die Kantenmenge E ⊆ (V × V ), definiert ist.

• Ein Weg zwischen zwei Knoten v und w ist eine Folge von Kanten, sodaß der Endknoten einer Kante mit dem Anfangsknoten der nachfolgenden identisch ist.

• Ein Pfad ist ein Weg, bei dem alle Knoten unterschiedlich sind.

• Ein Kreis ist ein Pfad, bei dem Anfangs- und Endpunkt identisch sind.

• Ein Graph heißt azyklisch, wenn er er keine Kreise positiver L¨ ange besitzt.

• Der Abstand d(v, w) zweier Knoten v, w ist die L¨ ange eines k¨ urzesten Pfades, der beide verbindet. Der Durchmesser eines Graphen ist max { d(v, w) | v, w ∈ V }.

• Der Grad eines Knoten v, δ grad (v), ist bei ungerichteten Graphen die Anzahl der Kanten, mit denen v inzidiert. In gerichteten Graphen ist der Ingrad δ in (v) von v definiert als die Anzahl der Kanten mit Endpunkt v. Entsprechendes gilt f¨ ur den Ausgrad δ aus (v) mit Endpunkt v.

• In einem ungerichteten Graphen G ist der Grad des Graphen δ grad (G) das Maximum der Grade seiner Knoten, in gerichteten ist analog sein Ingrad sowie Ausgrad definiert.

Definition. Die Vielfachheit einer Kante e = (v, w) ist die Anzahl der Kanten von v nach w. Ein Graph ohne Vielfachkanten heißt simpel ; meistens schließt das im ungerichteten Fall auch Schleifen aus.

Definition. Zwei Graphen G 1 , G 2 sind hom¨ oomorph, wenn eine Abbildung existiert, die die Kanten o.B.d.A. aus Graph G 1 auf Wege aus G 2 abbildet. Dabei muß die Abbildung voneinander verschiedener Kanten disjunkte Wege ergeben.

3

4 KAPITEL 1. GRAPHEN

Definition (Teilgraph). Ein Graph G = (V , E ) heißt Teilgraph des Graphen G, G ⊆ G, wenn gilt: V ⊆ V , E ⊆ E ∩ (V × V )

. Definition. Sei V ⊆ V . Der von V induzierte Teilgraph G G heißt echter Teilgraph von G, wenn gilt: V V . V von G ist der Graph G = (V , E ) mit E ∩ (V × V ) E =

. Definition (Eulergraph). Gibt es in G einen geschlossener Kantenzug C, der alle Kanten aus E genau einmal enth¨ alt, so heißt C Eulerweg und G ist ein Eulergraph.

¨ Aquivalente Bedingung ist, daß G (bis auf isolierte Knoten) zusammenh¨ angend ist und jeder Knoten des Eulergraphen geraden Grad besitzt. Definition (Hamiltongraph). Gibt es in G einen Kreis Kreis C, der alle Knoten aus V genau einmal enth¨ alt, so heißt C Hamiltonscher Kreis und G ist ein Hamiltonscher Graph. Definition (Bipartition). Ein Graph G = (V, E) heißt bipartit, wenn sich die Knotenmenge zerlegen

l¨ aßt in zwei Teilmengen V 1 , V 2 , sodaß gilt: V = V 1 ˙

∪ V 2 und keine Kante verbindet zwei Knoten aus der

selben Partitionsmenge, d.h. E ⊆ (V 1 × V 2 ) ∪ (V 2 × V 1 ). 1.2 Speicherung von Graphen A = (a ij ) 1≤i,j≤n ∈ B ^n×n , mit Definition. Eine Adjazenzmatrix zur Speicherung eines Graphen mit n Kanten ist eine Boolesche Matrix 1.2.1 Adjazenzmatrix 1 (i, j) ∈ E a ij :=

0 (i, j) / ∈ E Bei Mehrfachkanten ist A ∈ N ^n×n , und a ij wird der Wert der Vielfachheit der Kante zugeordnet. Satz 1. Sei π eine Eigenschaft auf Graphen mit n Knoten. Sei f¨ ur einen Graphen G π(G) ∈ {0, 1} mit: (v, ∅) vollst¨ andige Graph. Somit ist diese Kodierungsart f¨ ur leichte Probleme ausgesprochen ungeeignet. Bei einem Graph mit n Knoten besitzt die Adjazenzmatrix n ² Eintr¨ age, also stets genauso viel wie der 1. π

3. 2. π(K n ) = 1. = 0.

π(G) = 1 ∧ G Obergraph von G

⇒ π(G ) = 1.

4. (1)–(3) gelten nur, wenn die Nummerierung der Knoten irrelevant ist.

Dann muß jeder Algorithmus, der π auf der Adjazenzmatrix von G entscheidet, einen festen Teil der Matrix anschauen. Ein Beispiel f¨ ur solch ein π ist:

• G ist nicht planar (f¨ ur n ≥ 4)

1.3. GRAPHENISOMORPHIE 5

1.2.2 Knoten-Kanten–Inzidenzmatrix

Definition. In einer Knoten-Kanten–Inzidenzmatrix A der Gr¨ oße n×m bei einem Graphen mit n Knoten

und m Kanten ist a ij = ±1 gdw. die Kante j inzident zu Knoten i ist.

• Bei gerichteten Graphen erh¨ alt die Quelle den Eintrag 1, das Ziel −1. Die Spaltensummen sind also stets Null (Schleifen sind auf diese Weise somit nicht darstellbar.)

• Bei ungerichteten Graphen ist die Matrix bin¨ ar, in jeder Spalte befinden sich genau zwei Einsen (bzw. ganzzahlige Vielfache bei nicht-simplen Graphen).

Daraus ergibt sich f¨ ur (sehr) leichte Probleme ein Vorteil, ebenso aus o.g. Informationen, die die Matrix

implizit enth¨ alt.

1.2.3 Adjazenzliste

Definition. Eine Adjazenzliste ¹ ist eine Liste, in der f¨ ur jeden der Knoten eine Liste der mit ihm ver-

bundenen Knoten gespeichert ist. Somit besitzt diese Kodierungsart mit O |V | + |E|

i.a. den geringsten

Speicherbedarf.

Eine exaktere Absch¨ atzung des Speicherbedarfs ergibt eine obere Schranke von genau |V |+|E| f¨ ur ungerichtete und |V | + 2|E| f¨ ur gerichtete Graphen.

Viele Probleme lassen sich mit Hilfe von Adjazenzlisten in linearer Zeit l¨ osen.

1.3 Graphenisomorphie

Definition. Zwei Graphen G 1 = (V 1 , E 1 ) und G 2 = (V 2 , E 2 ) heißen isomorph, wenn es bijektive Abbildungen ϕ V : V 1 → V 2

ϕ E : E 1 → E 2

gibt, sodaß ϕ E (e) inzident zu ϕ V (v) ist gdw. e inzident zu v ist.

Aktuelle Algorithmen l¨ osen dieses Problem in O(n log ⁿ ). Bis heute ist aber kein Beweis f¨ ur die N P- Vollst¨andigkeit bekannt. Man nimmt an, daß der Isomorphietest in N P aber nicht in N PC liegt.

F¨ ur Definitionen von N P, N PC siehe Abschnitt 4.6.1 (Seite 64) bzw. Abschnitt 10.2 (Seite 88).

1.4 Planarit¨ at

Definition (Planarit¨ at). Ein Graph ist planar, wenn er in der Ebene (R ² ) kreuzungsfrei gezeichnet

werden kann.

Satz 2 (Kuratowski-Kriterium). Ein Graph ist genau dann nicht planar, wenn er mindestens einen

Abbildung 1.1: Die Graphen K5 und K3,3

¹ Turing Award (1986) der ACM f¨ ur Hopcroft & Tarjan

6 KAPITEL 1. GRAPHEN

1.5 B¨ aume

Definition. Ein Wald ist ein ungerichteter, azyklischer Graph. Ist er dar¨ uber hinaus noch zusammenh¨ angend, wird er als Baum bezeichnet.

Eigenschaften eines Baumes X = (V, E):

• Je zwei Knoten sind durch genau einen Weg verbunden

• X ist zusammenh¨ angend und jede Kante ist eine Br¨ ucke, d.h. f¨ ur eine beliebe Kante e ist X {e} nicht mehr zusammenh¨ angend.

• X besitzt keine Kreise, aber durch Hinzuf¨ ugen einer beliebigen neuen Kante erh¨ alt man genau einen Kreis.

• X ist zusammenh¨ angend und |E| = |V | − 1. ( zu jedem Knoten f¨ uhrt eine Kante hin — außer zur Wurzel“)

”

Definition. Ein gerichteter Baum ist ein Baum, bei dem alle Kanten gleichf¨ ormig in eine Richtung hin orientiert sind. Sind die Kanten in Richtung der Bl¨ atter orientiert, so definiert man die H¨ ohe eines Knotens v als den maximalen Abstand von v zu einem Blatt.

Definition (DAG). Gerichtete azyklische Graphen bezeichnet man als DAGs (directed acyclic graph). Im Unterschied zu gerichteten B¨ aumen oder W¨ aldern sind nur die DAGs selber notwendigerweise azyklisch, w¨ ahrend bei einem gerichteten Baum trivialerweise auch der korrespondierende ungerichtete Graph der Bedingung der Azyklit¨ at gen¨ ugen muß.

Definition. Ein bin¨ arer Baum heißt balanciert, wenn f¨ ur jeden inneren Knoten gilt, daß sich die H¨ ohe des linken Teilbaumes von der des rechten um h¨ ochstens 1 unterscheidet.

1.6 Zusammenhang

1.6.1 Schwacher Zusammenhang

uber eine ¨ Definition. Der (schwache) Zusammenhang auf ungerichteten Graphen ist definiert ¨ Aquivalenzrelation ² P auf Knoten:

P ⊆ V × V, vP w :⇔ ∃ Weg von v nach w.

Die ¨ Aquivalenzklassen sind die (schwachen) Zusammenhangskomponenten (ZHKs). Ein Graph G ist zusammenh¨ angend, wenn er nur eine ZHK besitzt.

Ein ungerichteter Graph G ist (schwach) zusammenh¨ angend, wenn der zugeh¨ orige gerichtete Graph G stark zusammenh¨ angend ist.

² P ist also reflexiv, symmetrisch & transitiv.

— Algorithmen & Komplexit¨ atstheorie —

1.6. ZUSAMMENHANG 7

1.6.2 Starker Zusammenhang uber eine ¨ Definition. Starker Zusammenhang auf gerichteten ³ Graphen ist definiert ¨ Aquivalenzrelation P auf Knoten: P ⊆ V × V, vP w :⇔ ∃ Weg von v ¨ uber w nach v. Die ¨ Aquivalenzklassen sind entsprechend die starken Zusammenhangskomponenten.

1.6.3 Zweifacher Zusammenhang uber eine ¨ Definition. Zweifacher Zusammenhang auf ungerichteten Graphen ist definiert ¨ Aquivalenzrelation P auf Kanten: P ⊆ E × E, e 1 P e 2 :⇔ (e 1 = e 2 ∨ e 1 ,e 2 liegen auf einem gemeinsamen Kreis.) Die ¨ Aquivalenzklassen von P sind die zweifachen ZHKs. Die von ihnen induzierten ¨ Aquivalenzklassen heißen Bl¨ ocke.

Der Graph G ist zweifach zusammenh¨ angend, wenn er nur eine 2-fache ZHK besitzt. Die Zweifach-Zusammenhangsstruktur eines Graphen wird repr¨ asentiert durch seinen Zweifach-Zusammenhangsbaum; dies ist ein bipartiter Graph aus Bl¨ ocken und Teilungspunkten.

Definition. Ein Knoten v aus G heißt Teilungspunkt (Artikulationspunkt), wenn er zu mehreren Bl¨ ocken geh¨ ort. D.h. es gibt Knoten x, y, sodaß jeder Weg zwischen x und y ¨ uber v f¨ uhrt. v fungiert als Verbindung von zwei 2-fache–ZHKs.

Abbildung 1.3: Graph (mit f¨ unf 2-fach–ZHKs) und sein 2-facher Zusammenhangsbaum Einsatz des 2-fachen Zusammenhangs:

• Gibt es zwischen allen zwei Knoten zwei unterschiedliche Wege? (Y ” Ausfallsicherheit“, z.B. in Netzwerken)

• Gibt es einen Weg zwischen Knoten v und w, der nicht ¨ uber den Knoten x f¨ uhrt? (nein, wenn x Artikulationspunkt zw. zwei ZHKs, die v bzw. w enthalten)

Satz 3. Ein Graph ist genau dann zweifach zusammenh¨ angend, wenn er durch Herausnahme eines beliebigen Knotens nicht in unterschiedliche ZHKs (nicht notwendigerweise 2-fach–ZHKs) zerf¨ allt.

³ starker Zusammenhang ist auf ungerichteten Graphen identisch mit schwachem Zusammenhang

— Algorithmen & Komplexit¨ atstheorie —

8 KAPITEL 1. GRAPHEN

1.6.4 k -facher Zusammenhang

Definition. G ist genau dann k-fach (knoten)zusammenh¨ angend, wenn die Herausnahme von k − 1 beliebigen Knoten ihn nicht zerfallen l¨ aßt.

k = 1: Die von den Komponenten induzierten Graphen sind die gr¨ oßten zusammenh¨ angenden Teilgraphen.

k = 2: Maximal 2-facher Zusammenhang ist notwendig (jedoch auch hinreichend), um jegliche topologische Modifikationen auf planaren Graphen zu beschreiben, die durchf¨ uhrbar sind, ohne die Planarit¨ at zu zerst¨ oren.

Am Beispiel von Abbildung 1.4 wird offensichtlich, daß Kugelgelenke und Scharniere die einzigen Stellen sind, an denen planare Graphen modifiziert werden k¨ onnen.

k = 3: Dreifache Zusammenhangskomponenten sind die gr¨ oßten 3-fach zusammenh¨ angenden Teilgraphen. Das bedeutet, daß es keine gr¨ oßeren Teilgraphen von G gibt, die dreifach zusammenh¨ angend sind.

¤

© §

^{§ § ©} Abbildung 1.4: Modifikationen am planaren Graph

Genauer: Der Zusammenhang ist sehr wichtig bei der Frage nach Planarit¨ at von Graphen: Die Planarit¨ at, also die Kreuzungsfreiheit der Kanten, h¨ angt immer von einer Einbettung ab. Betrachtet man nun die Teilungspunkte eines Graphen, sieht man leicht, daß alle Wege des Graphen (von einem adjazenten Block des Teilungspunktes zu einem anderen) durch diese Kanten laufen m¨ ussen. Man kann also die einzelnen Zusammenhangskomponenten eines Graphen getrennt auf Planarit¨ at untersuchen. Hat man jeweils eine geeignete Einbettung ge-

funden, so kann man die Einbettungen der einzelnen Zusammenhangskomponenten an den

Teilungspunkten wieder ” zusammenflicken“ und erh¨ alt so einen planaren Gesamtgraphen. Im Falle des 2-fachen und des 3-fachen Zusammenhangs bleiben dabei sogar gewisse Freiheiten ¨ ubrig: Der Teilungspunkt eines 1-fach zusammenh¨ angenden Graphen bildet ein Gelenk,

an dem man die Teilgraphen rotieren lassen kann. Die Teilungspunkte eines 2-fach zusammen-

h¨ angenden Graphen bilden paarweise Scharniere, an dessen L¨ angsachse man die Teilgraphen

1.7. DEPTH-FIRST-SEARCH 9

Dabei sind folgende Pfeilarten zu unterscheiden:

Wird der DFS auf Abbildung 1.5(a) bzw. 1.5(b) losgelassen, so ergeben sich die Graphen aus Abbildung 1.6. Dabei gilt folgende Interpretation der unterschiedlichen Kantenarten:

Der Algorithmus ist relativ simpel. Schwierig wird er erst durch die ” Plug-Ins“, die sp¨ ater bei anderen Algorithmen aufgef¨ ullt werden.

Nicht explizit aufgef¨ uhrt wurde die M¨ oglichkeit, zur Laufzeit die Kantenarten bzw. -klassen festzustellen. Die Charakterisierung durch den Zustand eines Knoten (Weiß, Grau, Schwarz) finden sich etwas weiter unten. Diese erm¨ oglichen dann die ¨ Uberpr¨ ufung zur Laufzeit.

— Algorithmen & Komplexit¨ atstheorie —

10 KAPITEL 1. GRAPHEN

Man beachte, daß die Kantenarten nur durch geeignete Benennung der vorhandenen Kanten entstehen.

f o r each v e r t e x v∈V do

od

time← 0 ; f o r each v e r t e x v∈V do

od

1.7.1 Laufzeit

Man betrachte das Listing 1.1. Die ersten beiden for-Schleifen, also der Main-Teil des Algorithmus, werden |V |-mal durchlaufen; nicht ber¨ ucksichtigt ist hierbei noch der Aufruf von dfs_visit. Diese Funktion wird f¨ ur jeden Knoten v ∈ V genau einmal aufgerufen, da sie ausschließlich auf weißen Knoten operiert und ihre erste Aktion auf einem weißen Knoten ist, diesen grau zu setzen.

Die for-Schleife innerhalb dieser Funktion wird f¨ ur den Knoten v |Adj(v)|-mal ausgef¨ uhrt. Da gilt: Adj(v) = O(|E|), ergibt sich eine Gesamt-Laufzeit von O(|V | + |E|), also ^v∈V O(m + n).

1.7.2 Struktur des DFS

Die beiden Werte d(v), f (v) f¨ ur einen Knoten v werden w¨ ahrend der Abarbeitung des Algorithmus gesetzt. = Farbe ” Dabei speichert d(v) den Zeitpunkt, an dem v zum ersten Mal besucht worden ist ( grau“), f (v) den Zeitpunkt, an dem v zum letzten Mal besucht (= abgeschlossen) wird ( = Farbe ”

schwarz“).

1.7. DEPTH-FIRST-SEARCH 11

Satz 4 (Klammertheorem). Genau eine der drei folgenden Bedingungen gilt f¨ ur u, v ∈ V : d[v], f [v] ∩ 1. 2. d[u], f [u] = ∅ d[u], f [u] d[v], f [v]

= ∅

3.

d[v], f [v]

d[u], f [u] (daß also u vor v das erste Mal besucht und auch fr¨ uher abgeschlossen wird) = ∅ Es geht jedoch nicht, daß d[u] < d[v] < f [u] < f [v].

Korollar 1. Der Knoten v ist echter Nachfolger von u im DFS-Baum genau dann, wenn Bedingung (2) des Klammertheorems gilt. Satz 5 (Weißes Wegelemma). v ist Nachfolger von u im DFS-Baum gdw. es zur Zeit, da u grau

gef¨ arbt wird, einen Weg von u nach v ¨

uber ausschließlich weiße Knoten gibt. Die Knotenzust¨ ande und Kantenarten lassen sich allein aus den Nummern d[v] und f [v] ableiten:

weiß: d[v] = 0

grau: d[v] = 0 ∧ f [v] = 0 schwarz: f [v] = 0

Die Kantenklassen f¨ ur eine Kante e = (v, w) ergeben sich zum Zeitpunkt ihrer Exploration im DFS:

Baumkante: d[w] = 0 Tritt auf, wenn dfs_visit(w) aus der Funktion dfs_visit(v) heraus aufgerufen

worden ist. v ist Vater von w, π(w) = v. Die Baumkanten ergeben den DFS-Baum. Vorw¨ artskante: f [w] > 0 ∧ d[w] > d[v]

Wenn e parallel zu einer (Folge von) Baumkante(n) – aber selber keine – ist. R¨ uckw¨ artskante: d[w] > 0 ∧ f [w] = 0

Wenn e antiparallel zu einer (Folge von) Baumkante(n) – aber selber keine – ist. Kreuzkante:

f [w] > 0 ∧ d[v] > d[w]

Sonst.

1.7.3 Anwendung des DFS

Die ”

12 KAPITEL 1. GRAPHEN

Die obigen Punkte 1 bis 3 werden durch den Struktursatz, lowpoint sowie lowpoint ausgef¨ ullt. Die Schritte 4 und 5 schließlich werden durch die Codierung des 2-fachen Zusammenhangs und des Starken Zusammenhangs belebt.

Satz 6 (Teilungspunkt). t ∈ V ist Teilungspunkt :⇔

1. t ist Wurzel des DFS-Baums und hat mindestens 2 S¨ ohne oder

2. t ist nicht Wurzel eines DFS-Baums und es existiert ein Sohn s von t, so daß es keine R¨ uckw¨ artskante von einem Nachfolger von s (einschließlich s) zu einem echten Vorg¨ anger von t gibt. Beweis.

1. ¨ uber Fallunterscheidung:

(a) Wenn t mehr als 1 Sohn hat, zerf¨ allt der Graph durch Herausnahme von t in alle Teilb¨ aume von S¨ ohnen von t.

(b) Wenn t nur einen Sohn hat, zerf¨ allt der Graph durch Herausnahme von t nicht. ⇒“ Durch L¨ oschen von t wird jeder solcher Teilbaum unter s abgeschnitten. 2. ”

⇐“ Durch L¨ oschen von t wird kein Teilbaum an S¨ ohnen von t abgeschnitten, da die R¨ uckw¨ arts”

kanten als ” Kleber“ dienen.

Definition (Lowpoint). Der Lowpoint eines Knoten v ist definiert als lowpoint[v] := min d[v], min { d[w] | erreichbar v (w) } mit , erreichbar v (w) = true

: ⇔ w von v aus ¨

uber eine Folge von Baumkanten und eine R¨ uckw¨ artskante erreichbar ist.

Der Lowpoint eines Knotens v kann also sein: • Der Er¨ offnungszeitstempel des Knotens selber, oder • Der minimale Er¨ offnungszeitstempel der Knoten, die von v aus per R¨ uckw¨ artskante erreicht werden k¨ onnen, oder

• Der Lowpoint eines Sohnes von v.

Die S¨ ohne eines Knoten kann man immer ¨

Berechnung des Lowpoints:

lowpoint[v] = min

1.7. DEPTH-FIRST-SEARCH 13

2-facher Zusammenhang

previsit A: l o w p o i n t [ u ] ←d [ u ] previsit B: push { u , v } onto s t a c k ;

newvisit: l o w p o i n t [ u ] = min{ l o w p o i n t [ v ] , l o w p o i n t [ u ] } ;

revisit: i f d [ u ] > d [ v ] ∧ v = π [ u ] then

postvisit: %

Starker Zusammenhang

Bevor man den Code f¨ ur die ” Visits“ angeben kann, m¨ ussen erstmal folgende beiden Lemmata gezeigt

werden:

Lemma 1. Alle Knoten einer starken Zusammenhangskomponente sind in dem selbem DFS-Baum. Sie

bilden sogar einen zusammenh¨ angenden Teilbaum in diesem DFS-Baum. Der Knoten einer ZHK, den der

DFS als erstes sieht, heißt Wurzel der Komponente. Zur besseren Lesbarkeit diene folgende Definition: Definition. Sei A(v, w) := ” Es gibt einen Weg von v nach w ¨ uber Baumkanten, gefolgt von h¨ ochstens

einer Kreuz- oder R¨ uckw¨ artskante, und die Wurzel der starken ZHK von w ist Vorfahre von v.“ Damit gilt: lowlink[v] = min { d[w] | A(v, w) }

Somit erh¨ alt man folgendes Lemma:

Lemma 2. v ist Wurzel einer starken ZHK ⇔ lowlink[v] ≥ d[v]. Mit diesen Voraussetzungen kann man nun die ” Visits“ angehen:

previsit A: l o w p o i n t [ v ] ←d [ u ] ; push v onto s t a c k ; previsit B: %

newvisit: l o w l i n k [ u ] = min{ l o w l i n k [ u ] , l o w l i n k [ v ] } ; revisit: i f v i s on s t a c k then

l o w l i n k [ v ] = min{ l o w l i n k [ u ] , d [ v ] } ; f i

postvisit: i f l o w l i n k [ u ] = d [ u ] then pop a l l nodes upto an i n c l u d i n g u from s t a c k ;

f i

v ist nicht Wurzel der Zusammenhangskomponente, weil r gemeinsamer Vorfahre von v und

w ist. Dadurch kommt man von w nach r und von dort nach v, von wo aus man wieder per

Kreuzkante nach w reisen kann.

F¨ ur das Verst¨ andnis des Algorithmus ist Lemma 1 sehr wichtig:

Wenn man eine Wurzel einer Zusammenhangskomponente findet, die Wurzel des gesamten

DFS-Baums ist, so ist der bearbeitete Graph stark zusammenh¨ angend.

Essentiell hierf¨ ur ist die Bedingung, die in Postvisit gepr¨ uft wird: Gilt lowlink[u]=d[u] und

ist außerdem u die Wurzel des gesamten DFS-Baumes, so ist der entsprechende Graph stark

zusammenh¨ angend.

— Algorithmen & Komplexit¨ atstheorie —

14 KAPITEL 1. GRAPHEN

Depth-First-Searchs versus Breadth-First-Searchs

Dieser Abschnitt ist fast sinnlos und leer. Der Titel soll auch als Sprech¨ ubung verstanden werden. Wer es schafft, ihn auszusprechen ohne seine Umgebung unter Wasser zu setzen, ist in unseren Augen f¨ ur eine

Info-A Pr¨ ufung bei Prof. Lengauer bestens vorbereitet. Prof. Lengauer hat den BFS nicht in seiner Vorlesung durchgenommen. Wir hielten es aber dennoch f¨ ur wissenswert, wie er funktioniert. Zumal er sehr simpel und leicht zu verstehen ist. Vergleiche dazu den

Code f¨ ur DFS auf Seite 10.

π [ v ] ←NIL

od c o l o r [ s ] ←gray ; d [ s ] ← 0 ; π [ s ] ←NIL ; v←head (Q) ;

c o l o r [ v ] ← b l a c k ;

Listing 1.2: Code f¨ ur BFS

1.8 k¨ urzeste Wege in Graphen

1.8.1 Historie 1956

Ford : erster Algorithmus, nicht effizient 1958 Bellman: effizienter Algorithmus behandelt auch negative Kantenkosten. Negative Kreise f¨ uh-

1959 ren zum Programmabbruch. Hintergrund Lineare Programmierung (Mathematik)

Dijkstra: bes. effizienter Algorithmus bei positiven Kosten; Dijkstra dachte: O(n ² ); [1960er:

1961 O(m log n); 1980er: O(m + n log n)]

Lee: Version von Dijkstra–Algorithmus auf Platinen O(m + n) f¨ ur positive Kantenkosten 1970

Needleman/Wunsch: effizienter Algorithmus auf azyklischen Graphen f¨ ur Sequenzvergleich

1.8.2 Beschreibung des Problems

Gegeben: Ein gerichteter Graph G = (V, E) und eine Kantengewichtungsfunktion c : E → R

1. Single–Pair :

1.8. K ¨ URZESTE WEGE IN GRAPHEN 15

• Gegeben s, t ∈ V

• Was ist der k¨ urzeste Weg von s nach t ¨ uber Kanten in G? Was ist seine L¨ ange µ(s, t)?

2. Single–Source:

• Gegeben s ∈ V

• Finde µ(s, v) ∀ v ∈ V und gib k¨ urzeste Wege an

3. All-Pairs:

• Finde µ(s, v) ∀ s, v ∈ V und gib k¨ urzeste Wege an Lemma 3. (Grundaussagen ¨ uber Wege)

1. Falls w von v nicht erreichbar ist, gilt: µ(v, w) = +∞

2. Falls es einen Weg von v nach w gibt, der einen negativen Zyklus enth¨ alt, gilt: µ(v, w) = −∞

3. Existenz eines k¨ urzesten Weges:

Falls w von v erreichbar und auf keinem Weg ein negativer Zyklus enth¨ alt, ist µ(v, w) endlich, −∞ < µ(v, w) < ∞.

4. Falls µ(v, w) = −∞, dann gibt es einen Weg von v nach w, der einen negativen Kreis enth¨ alt. Beweis (Fall 3 ). Sei p ein Weg von v nach w. Durch sukzessives Herausnehmen von positiven Kreisen

erh¨ alt man einen Weg p mit c(p ) ≤ c(p). Dieses Verfahren f¨ uhrt zu einem einfachen Weg. Die Anzahl der einfachen Wege ist endlich, daher ist µ(v, w) = c(p) f¨ ur einen Weg p.

Lemma 4.

Bezeichnung: µ(v) := µ(s, v) ist die L¨ ange eines k¨ urzesten Weges von s nach v. 1. Es gilt: µ(s) = min { 0, µ(u) + c(e) | e = (u, s) ∈ E } ∈ {0, −∞}, sowie

µ(v) = min { µ(u) + c(e) | e = (u, v) ∈ E } ∈

R ∪ {−∞, ∞}

2. Wenn d eine Kostenfunktion d : V → R ∪ {−∞, ∞} ist, f¨ ur die gilt: (a) d(v) ≥ µ(v), v ∈ V (b) d(s) ≤ 0

(c) d(v) ≤ d(u) + c(e), falls e = (u, v) ∈ E

dann ist d ≡ µ. Beweis. (Aussage 2):

Nach Voraussetzung ist d(v) ≥ µ(v). Angenommen, d(v) > µ(v) (und somit d ≡ µ). Sei [s = v 0 , v 1 , . . . , v k =

v] ein k¨ urzester Weg von s nach v. Es gilt µ(s) = 0 = d(s), nat¨ urlich auch µ(v i ) = µ(v i−1 ) + c (v i−1 , v i ) f¨ ur i > 0, sowie µ(v) < d(v). Sei i > 0 nun die kleinste Zahl f¨ ur die gilt: µ(v i ) < d(v i ). Damit haben wir

d(v i ) > µ(v i )

= µ(v i−1 ) + c

16 KAPITEL 1. GRAPHEN

Welche Stuktur erzeugen die π-Pointer auf einem Graphen?

(a) ” normaler“ K¨ urzeste-Wege-Baum; ”

Richtung der π-Pointer

Abbildung 1.8: K¨ urzeste-Wege-B¨ aume

Definition. Ausgabe eines k¨ urzesten-Wege-Algorithmus:

1. Zerlegung von V in drei Mengen: (a) V ⁻ := { v ∈ V | µ(v) = −∞ } (b) V ^f := { v ∈ V | −∞ < µ(v) < ∞ } (c) V ⁺ := { v ∈ V | µ(v) = +∞ }

; 2. Der Algorithmus gibt f¨ ur jeden Knoten ein Paar (dist (= µ), pred ( π)) aus mit:

• dist(v) ∈ V ist offensichtlich die k¨ urzeste Distanz von s nach v, pred(v) ∈ E ist ein Pointer auf eine inzidente Kante, ¨ uber die ein k¨ urzester Weg von s nach v f¨ uhrt.

• s ∈ V ^f ⇔ pred[s] = nil; sonst: s ∈ V ⁻ .

• v = s: v ∈ V ⁺ ⇔ pred[v] = nil.

• v ∈ V ^f ⇔ v erreichbar von s durch einen P -Pfad ⁴ , s ∈ V ^f , mit

P := { (pred[v], v) | v ∈ V, pred[v] = nil }

P | V f formt einen K¨ urzeste-Wege-Baum mit Wurzel s.

• Alle P -Zyklen sind negative Kreise. v ∈ V ⁻ , falls v von einem P -Zyklus erreichbar ist.

1.8.3 Ein generischer Algorithmus

Die Grundidee besteht darin, daß zu Beginn alle Knoten außer s mit dem Wert ∞ gelabelt werden. Nun werden sukzessive alle Kanten e = (u, v), die die Dreiecksungleichung d(v) ≤ d(u) + c(e) nicht erf¨ ullen, korrigiert, bis der Graph ausschließlich aus ” korrekt“ gelabelten Knoten besteht.

Definition.

TE := { e = (u, v) ∈ E | e wurde bereits von dem Algorithmus getestet }

T E := e 1 e 2 . . . e i eine Folge von Kanten, die bereits getestet worden sind (in T E kann eine Kante mehrfach auftreten! ) P := { e | e = π(v) f¨ ur ein v ∈ V } , P ⊆ TE

⁴ Ein P -Pfad ist also ein Pfad, f¨ ur den gilt: ist ein Knoten v Vorg¨ anger eines Knoten w in dem P -Pfad, so ist auch in dem Graphen w mit v ¨ uber einen π-Pointer verbunden

— Algorithmen & Komplexit¨ atstheorie —

1.8. K ¨ URZESTE WEGE IN GRAPHEN 17

d ( s ) = 0 ;

d ( v ) = ∞ fo r a l l v = s ; π ( v ) = n i l fo r a l l v∈V;

while t h e r e i s an edge e=(u , v ) ∈ E with d ( v ) > d ( u)+c ( e ) do

od

Anmerkungen:

Die Menge TE enth¨ alt somit (sp¨ atestens) nach Terminierung des Algorithmus alle Kanten, da w¨ ahrend der Laufzeit jede Kante mindestens einmal getestet wird. Die Reihenfolge des Testens spiegelt sich somit in der Folge T E wieder; da T E keine Menge ist, sind i.a. Kanten aus E mehrfach vorhanden.

All jene Kanten, die nun tats¨ achlich auf einem k¨ urzesten Weg von s zu einem beliebigen Knoten v ∈ V liegen, werden in P gespeichert.

Lemma 5. W¨ ahrend jeder Zeit der Ausf¨ uhrung des generischen Algorithmus gilt:

a) d(s) = 0 gdw. π(s) = nil, und d(v) < ∞ gdw. π(v) = nil, (v = s). Die erste ¨ Aquivalenz ist genau dann gegeben, wenn s auf einem negativen Zyklus liegt, also s ∈ V ^f .

b) Falls π(v) = e = (u, v), dann gilt d(v) ≥ d(u)+c(e) nach jeder Beendigung eines Schleifendurchlaufs. Wenn ein π-Pointer f¨ ur einen Knoten v gesetzt worden ist, so wird sein Wert d(v) nicht mehr ver¨ andert (da er ab nun die Dreiecksungleichung erf¨ ullt). Einzig der Wert von u kann im Laufe des Algorithmus noch verringert werden.

c) Falls π(v) = nil, dann liegt v entweder auf einem P -Zyklus oder kann von s aus erreicht werden. Falls π(s) = nil, dann liegt s auf einem P -Zyklus (vgl. (a)).

Der Startknoten s kann keinen P -Vorg¨ anger haben, es sei denn, er liegt auf einem negativen Zyklus, und damit auf einem P -Zyklus.

d) P -Zyklen haben negative Kosten.

Klar, da nur Zyklen negativer L¨ ange P -Zyklen im zugeh¨ origen K¨ urzeste-Wege-Graph ergeben.

e) Falls v auf einem P -Zyklus liegt oder von ihm aus erreichbar ist, gilt: µ(v) = −∞. Gilt direkt nach (d) und Definition von µ.

f) Nach dem Testen der Kantenfolge e 1 . . . e i hat d(v) den Wert des k¨ urzesten Weges von s nach v, der eine Teilfolge von e 1 . . . e i ist. Dabei m¨ ussen die Kanten der Folge nicht benachbart sein. F¨ ur v = s ist die Behauptung trivial. F¨ ur Knoten v = s gilt sie ebenfalls, da der Weg zu v schon exploriert ist, wenn er eine Teilfolge von e 1 . . . e i ist. In diesem Fall ist auch d(v) schon optimal. Offenbar kann der Algorithmus beendet werden, wenn TE alle k¨ urzesten Wege von s aus enth¨ alt. Dies ist genau dann der Fall, wenn T E alle einfachen Wege aus G enth¨ alt, denn k¨ urzeste Wege sind o.B.d.A. einfach. =: {e 1 , . . . , e m } Wir setzen nun: E

18 KAPITEL 1. GRAPHEN

Damit gilt:

T E univ = E ⁿ ist eine geeignete Kantenfolge

|T E univ | = m · (n − 1)

Der Algorithmus testet jede Kante aus T E univ . Danach reicht es aus, jede Kante noch einmal daraufhin zu ¨ uberpr¨ ufen, ob sie nach Terminierung des Algorithmus die Dreiecksungleichung erf¨ ullt. Falls es eine Kante gibt, die diese verletzt, so existiert ein negativer Zyklus in G.

Die erste Kante des k¨ urzesten Wegs ist trivialerweise eine Kante, muß also ∈ E sein, also eine der ersten e 1 , . . . , e m aus T E univ . Die restlichen Kanten ebenso, sodaß wir nach ” Abarbeitung“

von T E univ sicher jede Kante des k¨ urzesten Weges (in der korrekten Reihenfolge) gecheckt haben.

Die Laufzeit betr¨ agt somit O(m · n). Also liefert bereits dieser simple Algorithmus im Worst-Case bestm¨ ogliche asymptotische Laufzeit.

d ( s ) ← 0 ;

f o r a l l nodes v = s do d ( v ) ← ∞ ; od U : = { s } ; while U = ∅ do

od

Listing 1.4: Halb-generische Umsetzung von Algorithmus 1.3

Lemma 6 (Existenssatz f¨ ur beste Wahlen von u). Sei U die Menge der Knoten, die gerade ” bearbeitet“ werden – vergleiche Algorithmus 1.4. Genauer:

U ⊆ { u | d(u) < ∞ ∧ ∃(u, v) ∈ E : d(u) + c(u, v) < d(v) } .

Wurde ein Knoten v soeben gecheckt (& ggf. korrigiert), werden seine S¨ ohne in U gespeichert, um sp¨ ater bearbeitet zu werden. Vergleiche dazu auch die Tabelle weiter unten.

a) Solange d(v) > µ(v) f¨ ur irgend ein v ∈ V ^f , gibt es einen Knoten u ∈ U mit d(u) = µ(u) und u liegt auf einem k¨ urzesten Weg von s nach v.

b) Wenn ein Knoten u ∈ U entnommen wird, f¨ ur den gilt d(u) = µ(u), dann wird u nie wieder nach U hereingesetzt.

Beweis.

a) Sei [s = v 0 , v 1 , . . . , v k = v] ein k¨ urzester Weg von s nach v. Also gilt µ(s) = 0 = d(s) sowie d(v k ) ≥ µ(v k ). Sei i minimal mit d(v i ) > µ(v i ). Somit ist i > 0, d(v i−1 ) = µ(v i−1 ) und

d(v i ) > µ(v i )

1.8. K ¨ URZESTE WEGE IN GRAPHEN 19

b) Es gilt immer: d(u) ≥ µ(u). Wenn u zu U hinzugef¨ ugt wird, wird d(u) auf µ(u) gesetzt (nach Lemma 4, da d(u) nun der Dreiecksungleichung gen¨ ugt). Somit gilt, daß, wenn ein Knoten u mit d(u) = µ(u) aus U herausgenommen, er nie wieder in U hineingef¨ ugt wird.

Lemma 7. Das vorherige Lemma kann in einen konstruktiven Algorithmus (1.4) umgesetzt werden. Auf diese Weise ist die Terminierung gew¨ ahrleistet. Was noch bleibt, ist die Notwendigkeit, den Nichtdeterminismus in der Wahl eines Knotens u ∈ U zu beseitigen. Zu diesem Zweck betrachte man folgende zwei

Ford F¨ alle:

Falls G azyklisch und u 0 , u 1 , . . . , u n−1 eine topologische Sortierung ⁵ der Knoten, dann gilt

d(u) = µ(u) f¨ ur den Knoten u i ∈ U mit dem kleinsten i. Dijkstra Falls G ausschließlich positive Kantenkosten besitzt, also c(e) ≥ 0 ∀ e ∈ E, dann gilt

d(u) = µ(u) f¨ ur den Knoten u ∈ U mit kleinstem d(u). Nach Lemma 6 existiert in jedem Fall ein u ∈ U mit d(u) = µ(u); solch einen Knoten gilt es nun zu

finden. Daß eine topologische Sortierung bei Ford tats¨ achlich hinreichend ist, um einen solchen Knoten

Abbildung 1.9: Topologische Sortierung

In der Abbildung sind die Knoten 1,2,3 und 5 bereits exploriert worden, die Menge U besteht somit aus den Knoten {5, 4}. Durch die topologische Sortierung ist

nun der Knoten u = 4 derjenige, der als n¨ achstes ausgew¨ ahlt wird (d.h. die Kante (2, 4)). F¨ ur dieses u gilt offensichtlich die Bedingung: d(u) = µ(u). Diese Gleichheit ist jedoch f¨ ur Knoten u = 5 (noch) nicht erf¨ ullt, da – {4, 5} ¨ (3, 5)

uber Knoten 4: die Kosten des ¨ uber diesen Knoten f¨ uhrende Weg sind geringer als die des

bisher gefundenen . Also w¨ are die oben angenommene Wahl von u = 4, die die topologische Sortierung außer Acht lassen w¨ urde, fehlerhaft! Der Dijkstra–Algorithmus mit potentiell vorhandenen (positiven) Zyklen ist interessanter, da hier auch Knoten u ∈ U vorhanden sein k¨ onnen, f¨ ur die obige Gleichheit nicht gilt, also

d(u ) > µ(u ). Nach Lemma 6 existiert jedoch sicher ein ” korrektes“ u ∈ U . Um solch ein u m¨ oglichst effizient zu finden, ist die Menge U mittels einer Warteschlangenstruktur (priority queue), sortiert nach d(u), zu implementieren. Dabei wird der Graph in

Form der Breitensuche traversiert, da mit Hilfe der priority queue und aufsteigender Sortierung eine FIFO-Struktur entsteht. Diese Vorgehensweise entspricht der eines Greedy–Algorithmus, da in jedem Schritt der Kno-

ten u mit dem kleinsten Wert d(u) gew¨ ahlt wird. Es ist jedoch m¨ oglich zu zeigen, daß der

Dijkstra-Algorithmus immer eine optimale L¨ osung, also wirlich k¨ urzeste Wege, liefert.

20 KAPITEL 1. GRAPHEN

Aus Lemma 7 resultieren folgende beiden Spezialf¨ alle:

Azyklischer Graph: Wie oben besprochen, muß in diesem Fall lediglich eine (topologi- Ford

Dijkstra positive Kantenkosten: Beim Dijkstra-Algorithmus muß U folgende Operationen unter-

normaler“ Heaps) realisieren jedoch decrease key amortisiert in

Zeit O(1). Somit reduziert sich die Gesamtlaufzeit zu O(m + n log n). Anmerkung zur Umsetzung der priority Queue mittels einer Heapstruktur : Wie auch im Appendix A.1 beschrieben, ist ein Heap ein bin¨ arer Baum, das (bzgl. eines Sortierungsschl¨ ussels) gr¨ oßte Element bildet die Wurzel. Somit ben¨ otigt das Einf¨ ugen eines neuen Elementes O(log n) Zeit. Die selbe asymptotische Laufzeit wird f¨ ur das Finden des kleinsten Elementes ben¨ otigt, da der Baum bis zu einem Blatt traversiert werden muß.

Da das ¨ Andern eines Wertes d(u) aus dem Auslesen und nachfolgigem Einf¨ ugen eines Knotens Im Vergleich dazu betr¨ agt bei einer naiv als zeigerverkettete Liste implementierten Priority-Queue das Auslesen des kleinsten Elementes o.B.d.A. O(1), das Suchen eines beliebigen Eledes Heaps besteht, ergibt sich hierf¨ ur eine die Laufzeit von O(2 log n) = O(log n). mentes (

Y decrease key) jedoch O(n). Daraus w¨ urde sich eine gesamt-Laufzeit des Algorithmus von O(m · n) ergeben.

⁶ W¨ ahle in jedem Schritt genau einen Knoten aus – den mit dem kleinsten d(·)-Wert; dieser Wert ist nach Lemma 6

korrekt, der Knoten wird nie wieder in U eingef¨ ugt.

1.8. K ¨ URZESTE WEGE IN GRAPHEN 21

1.8.4 Single-Pair (Single Source – Single Sink)

Die Suche nach den k¨ urzesten Wegen von a nach b ist offensichtlich trivial auf Single-Source reduzierbar. Dies ist jedoch recht ineffizient, da unn¨ otigerweise der gesamte Graph durchsucht wird. Wie l¨ aßt sich dies vermeiden?

L¨ osung 1: F¨ uhre von den Knoten a und b parallel zwei Instanzen des Dijkstra-Algorithmus aus. Eine

L¨ osung 2: Im folgenden Szenario ist eine besondere Strategie m¨ oglich:

1.8.5 Bellmann-Ford-Algorithmus

Bisher haben wir in dieser Sektion lediglich azyklische Graphen (Ford) oder Graphen mit ausschließlich positiven Kantenkosten (Dijkstra) betrachtet. Bei dem ¨ Uberganz zu allgemeinen Graphen, potentiell mit

negativen Zyklen, stellt sich das Problem, daß die Gr¨ oße d(u) pl¨ otzlich irrelevant geworden ist, da sie sich i.a. beliebig verkleinern l¨ aßt. Als Hilfsmittel ist nun die zeitliche Reihenfolge der Knoten zu betrachten.

Definition. F¨ ur die Realisierung definieren wir nun zu einem Knoten v neben dem Wert µ(v) (= k¨ urzeste Wegl¨ ange von s nach v) den Wert µ k (v):

µ k (v) := k¨ urzeste L¨ ange eines Weges mit h¨ ochstens k Kanten

⁹ Sei u = (u 1 , . . . , u k ) ein Weg, dann muß gelten: λ(u i , t) ≥ λ(u j , t) ∀ i, j, i < j

— Algorithmen & Komplexit¨ atstheorie —

22 KAPITEL 1. GRAPHEN

Idee:

Der Ablauf des Algorithmus verl¨ auft wie bisher, jedoch werden nun die Phasen (auch P¨ asse genannt) mitprotokolliert. Nach einer bestimmten Anzahl Phasen (n − 1) kann man den Algorithmus stoppen und sicher alle negativen Zyklen detektieren.

Der Ablauf des Algorithmus wird nun in unterschiedliche Phasen eingeteilt (vgl. Abbildung 1.11): Phase 0: Das Zeitintervall w¨ ahrend des Bellmann-Ford-Algorithmus, bei dem die Kanten aus s bearbeitet werden.

Phase i: Das Zeitintervall, bei dem die Kanten von allen Knoten bearbeitet werden, die am Ende von Phase i − 1 in U sind. (i > 0)

Es werden n − 1 Phasen durchlaufen, in jeder Phase k¨ onnen maximal m Kanten ausgehen, also m Knoten bearbeitet werden m¨ ussen. Daraus ergibt sich eine Laufzeit von

9

@

A

B C

D E

^F Abbildung 1.11: Phasendiagramm zu Bellmann-Ford Lemma 8. Nach Phase n − 1 (also nach der letzten Phase) gilt:

a) d(v) ≤ µ n (v), und wenn v ∈ U : d(v) < µ n−1 (v) (falls negative Wege auftreten). b) s ∈ V ^f ⇔ π(s) = nil. c) Jeder Knoten u ∈ U liegt auf einem P -Zyklus oder auf einem P -Pfad, der von einem P -Zyklus

erreichbar ist.

Nach n − 1 Phasen hat man insgesamt n Knoten erreicht. Wenn dann noch ein Knoten in U liegt,

1.8. K ¨ URZESTE WEGE IN GRAPHEN 23

Fall 1: Wenn π(s) = nil, dann sind wir fertig.

⇒ s liegt nicht auf einem negativen Zyklus.

Fall 2: Wenn π(s) = nil, m¨ ussen wir noch Knoten mit V ⁻ labeln, die bisher noch von s ¨ uber

Mehlhorn/N¨ aher haben nun folgende Stategie eingef¨ ugt, um alle Knoten, die auf einem negativen Zyklus liegen, oder von einem erreichbar sind, als solche zu identifizieren: Es wird jeweils von allen Knoten in U aus ein DFS durchgef¨ uhrt, die erreichbaren Knoten werden mit V ⁻ gelabelt.

Aus jedem negativen Zyklus muß ein Knoten in U enthalten sein. Man labelt nun die Knoten, zu denen es keine k¨ urzesten Wege gibt, mit V ⁻ , um den restlichen Graphen zu ” retten“.

Tarjan hat gezeigt, daß eine Verbesserung des Bellmann-Ford-Algorithmus m¨ oglich ist, indem sog. ” Downstream-Regionen“ hinter einem gerade verbesserten Knoten aus U gel¨ oscht werden. Dieser Ansatz ist jedoch in der Vorlesung nicht besprochen worden.

1.8.6 All Pairs

Das All-Pairs–Problem auf allgemeinen Graphen ist trivialerweise reduzierbar auf n Single-Source Probleme, also n-mal Bellmann-Ford. Daraus ergibt sich eine naive Laufzeit von O(m · n ² ). Eine deutliche Verbesserung ist m¨ oglich, indem Informationen, die bei dem ersten Durchlauf gewonnen worden sind, dazu genutzt werden, die restlichen Durchl¨ aufe zu verschnellern.

Prinzipielle Idee:

Zu Beginn wird ein neuer Knoten s, eine Quelle, eingef¨ ugt und mit allen Knoten aus G ¨ uber Kanten ver-bunden, die mit 0 gewichtet sind. Man mache sich an einem einfachen Beispiel klar, daß das nachfolgende Reweighting nur negative Kanten ver¨ andert.

1. Elimination von negativen Zyklen: 1× Bellmann-Ford: f¨ uhrt zu einer Belegung der µ(s, v).

Die Ausf¨ uhrung ergibt keine neuen Zyklen, insbesondere keine negativen. Da durch diesen ersten Schritt alle Zyklen negativer L¨ ange identifiziert worden sind, wird im folgenden angenommen, daß G keine negativen Zyklen besitze. Somit ist in den folgenden Schritten der Dijkstra-Algorithmus anwendbar.

2. F¨ uhre ein Reweighting im Originalgraph durch: f¨ ur eine Kante e = (v, w) ver¨ andere

c(e) ← c(e) + µ(s, v) − µ(s, w).

Dies ¨ andert die Gewichtsstruktur in G nicht: Betrachte einen beliebigen Pfad v 1 , . . . , v k .

• Urspr¨ ungliche Kosten: c(v 1 , v 2 ) + c(v 2 , v 3 ) + · · · + c(v k−1 , v k ).

• nach Reweighting: µ(s, v 1 ) + c(v 1 , v 2 ) −

24 KAPITEL 1. GRAPHEN

Somit bleibt die partielle Ordnung auf den Kanten bzgl. ihrer Kosten erhalten, nur ” angehoben“ um µ(·).

Die Kantenkosten von e = (v, w) nach dem Reweighting betragen µ(s, v) + c(e) − µ(s, w) ≥ 0, da nach

dem erstem Durchlauf des Bellmann-Ford–Algorithmus alle Kanten die Dreiecksungleichung erf¨ ullen, d.h.

µ(s, v) + c(e) ≥ µ(s, w). Also kann im folgenden Dijkstra auf den Graphen angewendet werden. Sei das Ergebnis der n Dijsktra-Duchl¨ aufe eine Distanzmatrix D = d(u, v)

. Auf D f¨ uhren wir nun eine

Art Re-Reweighting durch, die obige Anhebung der Kantenkosten wird also wieder r¨ uckg¨ angig gemacht

mittels

d(u, v) ← d(u, v) + µ(s, v) − µ(s, u). Ergebnis: £ 1× Bellmann-Ford auf dem durch eine Quelle erweiterten Graphen: O(m · n). £ Reweighting zur Positivierung aller Kantenkosten. £ n× Dijkstra nach Reweighting: O(m + n log n). £ Re-Reweighting.

Als Gesamt-Laufzeit ergibt sich somit:

O(m · n + n ² log n).

1.8.7 K¨ urzeste Wege mit Adjazenzmatrizen

Motivation:

• Beispiel f¨ ur die Anwendbarkeit von Adjazenzmatrizen :-)

• Erweiterbarkeit auf andere Kantenbewertungssysteme ( = R) Beispiele: Transitive H¨ ulle ¹⁰ , Regul¨ are Mengen, Matrizeninversion, Markovkettenanalyse

• Vergleiche außerdem Sektion 17.1.2 aus dem Teil ”

Komplexit¨ atstheorie“, Parallelisierung.

Gegeben sei ein Graph G = (V, E) und seine Adjazenzmatrix W = (w ij ), also w ij die Kosten der Kante

von Knoten i nach Knoten j. Uns interessieren Matrizen D ^(k) = (k) Im folgenden gelte die Annahme, daß der Graph simpel ist, also w ii = 0, und keine negativen Zyklen enth¨ alt. Die letzte Einschr¨ ankung wird jedoch sp¨ ater aufgehoben. d ij

, mit d

^(k) nen D ⁽ⁿ⁾ = D ⁽ⁿ⁻¹⁾ , wobei nat¨ urlich auch gilt: D ⁽ⁿ⁾ = D ⁽ⁿ⁺¹⁾ = D ⁽ⁿ⁺²⁾ = . . . , da unter dieser Annahme h¨ ochstens k Kanten. Angenommen, es existieren keine negativen Zyklen im Graphen. Wir wollen berech-

ij dieL¨ ange eines k¨ urzesten Weges von i nach j mit

⁰ . . . ∞

∞ uber die L¨ ange der Wege“ ): ⁰ ” Rekursion ¨ ^(k) = min (k−1)

£ D ^(k) kann rekursiv aus D ^(k−1) berechnet werden ( d d ij

alle Wege ¨ uber eine Kante l