Eine solide und gute Einführung in die algorithmische Graphentheorie für Studierende der Informatik und Mathematik.
Der Schwerpunkt dieser Einführung in die algorithmische Graphentheorie liegt in der praktischen Anwendung der Algorithmen auf aktuelle Probleme innerhalb der Informatik. Die Algorithmen sind in kompakter Form in programmiersprachennaher Notation dargestellt, die eine leichte Übertragung in objektorientierte Programmiersprachen erlaubt. Das Buch enthält Übungsaufgaben in verschiedenen Schwierigkeitsgraden für das Bachelor- und das Masterstudium.
/ AUS DEM INHALT: / / /
Vorwort v
1 Einleitung 1
1.1 Verletzlichkeit von Kommunikationsnetzen
1.2 Wegplanung für Roboter 3
1.3 Optimale Umrlistzeiten für Fertigungszellen
1.4 Objektorientierte Programmiersprachen 7
1.5 Suchmaschinen 10
1.6 Analyse sozialer Netze 13
1.7 Literatur 16
1.8 Aufgaben 16
2 Einführung 19
2.1 Grundlegende Definitionen 19
2.2 Spezielle Graphen 24
2.3 Graphalgorithmen 28
2.4 Datenstrukturen für Graphen 29
2.4.1 Adjazenzmatrix 30
2.4.2 Adjazenzliste 30
2.4.3 Kantenliste 32
2.4.4 Bewertete Graphen 32
2.4.5 Implizite Darstellung 33
2.5 Der transitive Abschluss eines Graphen 34
2.6 Vergleichskriterien für Algorithmen 38
2.7 Implementierung von Graphalgorithmen 44
2.8 Testen von Graph-Algorithmen 50
2.9 Literatur 52
2.10 Aufgaben 52
3 Bäume 57
3.1 Einführung 57
3.2 Anwendungen 59
3.2.1 Hierarchische Dateisysteme 59
3.2.2 Ableitungsbäume 60
3.2.3 Suchbäume 61
3.2.4 Datenkompression 64
3.3 Datenstrukturen für Bäume 68
3.3.1 Darstellung mit Feldern 68
3.3.2 Darstellung mit Adjazenzlisten 69
3.4 Sortieren mit Bäumen 71
3.5 Vorrang-Warteschlangen 76
3.6 Minimal aufspannende Bäume 78
3.6.1 Der Algorithmus von Kruskal 79
3.6.2 Der Algorithmus von Prim 83
3.7 Literatur 85
3.8 Aufgaben 85
4 Suchverfahren In Graphen 89
4.1 Einleitung 89
4.2 Tiefensuche 90
4.3 Anwendung der Tiefensuche aufgerichtete Graphen 94
4.4 Kreisfreie Graphen und topologische Sortierung 95
4.4.1 Rekursion in Programmiersprachen 97
4.4.2 Topologische Sortierung 97
4.5 Starke Zusammenhangskomponenten 99
4.6 Transitiver Abschluss und transitive Reduktion 104
4.7 Anwendung der Tiefensuche auf ungerichtete Graphen 107
4.7.1 Bestimmung der Zusammenhangskomponenten 107
4.7.2 Durchsatz und Querschnitt 108
4.7.3 Anwendung in der Bildverarbeitung 109
4.7.4 Blöcke eines ungerichteten Graphen HO
4.8 Breitensuche 116
4.9 Lexikographische Breitensuche 120
4.10 Beschränkte Tiefensuche 123
4.11 Eulersche Graphen 126
4.12 Literatur 130
4.13 Aufgaben 131
5 Entwurfsmethoden fDr die algorithmische Graphentheorie 135
5.1 Problemarten 135
5.2 Greedy-Technik 136
5.3 Backtracking 141
5.4 Branch & Bound 148
5.5 Teile & Herrsche 151
5.6 Dynamische Programmierung 155
5.7 Lineare Programmierung 159
5.8 Literatur 163
5.9 Aufgaben 164
6 Färbung von Graphen 167
6.1 Einführung 167
6.2 Anwendungen von Färbungen 173
6.2.1 Maschinenbelegungen 173
6.2.2 Registerzuordnung in Compilern 174
6.2.3 Public-Key Kryptosysteme 175
6.2.4 Sudoku 176
6.3 Exakte Bestimmung der chromatischen Zahl
6.3.1 Backtracking-Verfahren 178
6.3.2 Teile & Herrsche 178
6.3.3 Dynamische Programmierung 179
6.3.4 Lineare Programmierung 180
6.4 Heuristiken zur Bestimmung von Färbungen
6.5 Das Vier-Farben-Problem 186
6.6 Kantenfärbungen 190
6.7 Literatur 192
6.8 Aufgaben 193
7 Perfekte Graphen 197
7.1 Einführung 197
7.2 Kreisfreie Orientierungen 199
7.3 Transitiv orientierbare Graphen 200
7.3.1 Charakterisierung von transitiv orientierbaren Graphen 201
7.3.2 Färbungen von transitiv orientierbaren Graphen 202
7.4 Permutationsgraphen 203
7.4.1 Charakterisierung von Permutationsgraphen 204
7.4.2 Färbungen von Permutationsgraphen 205
7.5 Chordale Graphen 207
7.5.1 Charakterisierung von chordalen Graphen 208
7.5.2 Färbungen von chordalen Graphen 210
7.6 Intervallgraphen 213
7.6.1 Gewichtete unabhängige Mengen in Intervallgraphen 215
7.7 Literatur 218
7.8 Aufgaben 218
8 Flüsse in Netzwerken 219
8.1 Einleitung 219
8.2 Schnitte und Erweiterungswege 222
8.3 Der Satz von Ford-Fulkerson 225
8.4 Bestimmung von Erweiterungswegen 227
8.5 Der Algorithmus von Dinic 233
8.6 O-l-Netzwerke 243
8.7 Kostenminimale Flüsse 246
8.8 Literatur 249
8.9 Aufgaben 249
9 Anwendungen von Netzwerkalgorithmen 255
9.1 Maximale Zuordnungen 255
9.2 Netzwerke mit oberen und unteren Kapazitäten 261
9.3 Eckenzusammenhang in ungerichteten Graphen 266
9.4 Kantenzusammenhang in ungerichteten Graphen 273
9.5 Minimale Schnitte 277
9.6 Eckenüberdeckungen 284
9.7 Literatur 285
9.8 Aufgaben 286
10 Kürzeste Wege 293
10.1 Einleitung 294
10.2 Das Optimalitätsprinzip 296
10.3 Der Algorithmus von Moore und Ford 300
10.4 Anwendungen auf spezielle Graphen 304
10.4.1 Graphen mit konstanter Kantenbewertung 304
10.4.2 Graphen ohne geschlossene Wege 304
10.4.3 Graphen mit nichtnegativen Kantenbewertungen 304
10.4.4 Graphen mit ganzzahligen nichtnegativen Kantenbewertungen 308
10.5 Bestimmung von Zentralitätsmaßen 309
10.6 Routingverfahren in Kommunikationsnetzen 313
10.7 Kürzeste-Wege-Probleme in der künstlichen Intelligenz 315
10.7.1 Der A*-Algorithmus 316
10.7.2 Der iterative A*-Algorithmus 319
10.7.3 Umkreissuche 323
10.8 Kürzeste Wege zwischen allen Paaren von Ecken 329
10.9 Der Algorithmus von Floyd 332
10.10 Steinerbäume 335
10.11 Literatur 338
10.12 Aufgaben 339
11 Approximative Algorithmen 345
11.1 Die Komplexitätsklassen T, NCP und XPC 345
11.2 Einführung in approximative Algorithmen 351
11.3 Absolute Qualitätsgarantien 353
11.4 Relative Qualitätsgarantien 355
11.5 Approximative Algorithmen 356
11.5.1 Minimale Färbungen 356
11.5.2 Minimale Eckenüberdeckungen 358
11.5.3 Minimale dominierende Mengen 362
11.5.4 Maximale unabhängige Mengen 364
11.5.5 Minimale Steinerbäume 366
11.6 Das Problem des Handlungsreisenden 368
11.7 Literatur 376
11.8 Aufgaben 377
Die Graphen an den Kapitelanfängen 385
Literatur 389
Index 395