Jedes System, das aus diskreten Zuständen oder Objekten und Beziehungen zwischen diesen besteht, kann als Graph modelliert werden. Viele Anwendungen erfordern effiziente Algorithmen zur Verarbeitung derartiger Systeme. Der Schwerpunkt dieser Einführung in die algorithmische Graphentheorie liegt in der praktischen Anwendung der Algorithmen innerhalb der Informatik. Die Algorithmen sind in kompakter Form in einer programmiersprachennahen Notation dargestellt, die eine Übertragung in eine objektorientierte Programmiersprache wie Java oder C# leicht macht. Die praktische Relevanz der behandelten Algorithmen wird in vielen Anwendungen aus Gebieten wie Compilerbau, Künstlicher Intelligenz, Betriebssystemen, Computernetzwerken, World Wide Web, Analyse sozialer Netzwerke und Operations Research demonstriert. Neun Kapitel decken die wichtigsten Teilgebiete der algorithmischen Graphentheorie ab. Das Buch enthält rund 300 Übungsaufgaben in verschiedenen Schwierigkeitsgraden, für das Bachelor- und das Masterstudium. Die ausführlichen Lösungen befinden sich in einem Anhang.
Author(s): Volker Turau
Publisher: Oldenbourg Wissenschaftsverlag
Year: 2009
Language: German
Pages: 458
Inhaltsverzeichnis......Page 9
1 Einleitung......Page 14
1.1 Verletzlichkeit von Kommunikationsnetzen......Page 15
1.2 Wegplanung für Roboter......Page 16
1.3 Optimale Umrüstzeiten für Fertigungszellen......Page 18
1.4 Objektorientierte Programmiersprachen......Page 19
1.5 Suchmaschinen......Page 23
1.6 Analyse sozialer Netze......Page 26
1.8 Aufgaben......Page 29
2 Einführung......Page 32
2.1 Grundlegende Definitionen......Page 33
2.2 Spezielle Graphen......Page 37
2.4 Datenstrukturen für Graphen......Page 39
2.4.1 Adjazenzmatrix......Page 40
2.4.2 Adjazenzliste......Page 41
2.4.3 Kantenliste......Page 42
2.4.4 Bewertete Graphen......Page 43
2.5 Der transitive Abschluß eines Graphen......Page 44
2.6 Vergleichskriterien für Algorithmen......Page 48
2.7 Implementierung von Graphalgorithmen......Page 54
2.8 Greedy-Algorithmen......Page 60
2.9 Zufällige Graphen......Page 63
2.11 Aufgaben......Page 64
3.1 Einführung......Page 70
3.2.2 Ableitungsbäume......Page 73
3.2.3 Suchbäume......Page 75
3.2.4 Datenkompression......Page 79
3.3.1 Darstellung mit Feldern......Page 83
3.3.2 Darstellung mit Adjazenzlisten......Page 84
3.4 Sortieren mit Bäumen......Page 85
3.5 Vorrang-Warteschlangen......Page 91
3.6 Minimal aufspannende Bäume......Page 93
3.6.1 Der Algorithmus von Kruskal......Page 94
3.6.2 Der Algorithmus von Prim......Page 98
3.7 Literatur......Page 100
3.8 Aufgaben......Page 101
4 Suchverfahren in Graphen......Page 106
4.2 Tiefensuche......Page 107
4.3 Anwendung der Tiefensuche auf gerichtete Graphen......Page 111
4.4 Kreisfreie Graphen und topologische Sortierung......Page 113
4.4.1 Rekursion in Programmiersprachen......Page 114
4.4.2 Topologische Sortierung......Page 115
4.5 Starke Zusammenhangskomponenten......Page 117
4.6 Transitiver Abschluß und transitive Reduktion......Page 120
4.7 Anwendung der Tiefensuche auf ungerichtete Graphen......Page 125
4.8 Anwendung der Tiefensuche in der Bildverarbeitung......Page 127
4.9 Blöcke eines ungerichteten Graphen......Page 128
4.10 Breitensuche......Page 134
4.11 Beschränkte Tiefensuche......Page 139
4.12 Eulersche Graphen......Page 142
4.13 Literatur......Page 145
4.14 Aufgaben......Page 146
5 Färbung von Graphen......Page 152
5.1 Einführung......Page 153
5.2.1 Maschinenbelegungen......Page 159
5.2.2 Registerzuordnung in Compilern......Page 160
5.2.3 Public-Key Kryptosysteme......Page 161
5.3 Backtracking-Verfahren......Page 162
5.4 Das Vier-Farben-Problem......Page 165
5.5 Transitiv orientierbare Graphen......Page 170
5.6 Literatur......Page 177
5.7 Aufgaben......Page 178
6.1 Einleitung......Page 186
6.2 Der Satz von Ford und Fulkerson......Page 191
6.3 Bestimmung von Erweiterungswegen......Page 193
6.4 Der Algorithmus von Dinic......Page 201
6.5 0-1-Netzwerke......Page 211
6.6 Kostenminimale Flüsse......Page 214
6.7 Literatur......Page 216
6.8 Aufgaben......Page 217
7 Anwendungen von Netzwerkalgorithmen......Page 222
7.1 Maximale Zuordnungen......Page 223
7.2 Netzwerke mit oberen und unteren Kapazitäten......Page 228
7.3 Eckenzusammenhang in ungerichteten Graphen......Page 233
7.4 Kantenzusammenhang in ungerichteten Graphen......Page 241
7.5 Minimale Schnitte......Page 244
7.7 Aufgaben......Page 252
8 Kürzeste Wege......Page 260
8.1 Einleitung......Page 261
8.2 Das Optimalitätsprinzip......Page 263
8.3 Der Algorithmus von Moore und Ford......Page 267
8.4.2 Graphen ohne geschlossene Wege......Page 271
8.4.3 Graphen mit nichtnegativen Kantenbewertungen......Page 272
8.4.4 Graphen mit ganzzahligen nichtnegativen Kantenbewertungen......Page 275
8.5 Bestimmung von Zentralitätsmaßen......Page 277
8.6 Routingverfahren in Kommunikationsnetzen......Page 281
8.7 Kürzeste-Wege-Probleme in der künstlichen Intelligenz......Page 283
8.7.1 Der iterative A*-Algorithmus......Page 287
8.7.2 Umkreissuche......Page 292
8.8 Kürzeste Wege zwischen allen Paaren von Ecken......Page 297
8.9 Der Algorithmus von Floyd......Page 300
8.10 Steiner Bäume......Page 302
8.11 Literatur......Page 306
8.12 Aufgaben......Page 307
9 Approximative Algorithmen......Page 314
9.1 Die Komplexitätsklassen V, MV und MVC......Page 315
9.2 Einführung in approximative Algorithmen......Page 319
9.3 Absolute Qualitätsgarantien......Page 322
9.4 Relative Qualitätsgarantien......Page 324
9.5 Approximative Färbungsalgorithmen......Page 330
9.6 Das Problem des Handlungsreisenden......Page 339
9.7 Literatur......Page 348
9.8 Aufgaben......Page 349
A Angaben zu den Graphen an den Kapitelanföngen......Page 360
B.1 Kapitel 1......Page 364
B.2 Kapitel 2......Page 366
B.3 Kapitel 3......Page 373
B.4 Kapitel 4......Page 382
B.5 Kapitel 5......Page 390
B.6 Kapitel 6......Page 398
B.7 Kapitel 7......Page 406
B.8 Kapitel 8......Page 417
B.9 Kapitel 9......Page 426
Literaturverzeichnis......Page 444
Index......Page 452
