X
  GO
Ihre Mediensuche
Suche
Zweigstelle
Medienart


2 von 52
Algorithmische Graphentheorie
Verfasserangabe: Volker Turau ; Christoph Weyer
Jahr: 2015
Verlag: Berlin ; Boston, Mass., De Gruyter Saur
Mediengruppe: Buch
verfügbar (wo?)verfügbar (wo?)
Exemplare
 ZweigstelleStandorteStatusFristVorbestellungen
 Vorbestellen Zweigstelle: 07., Urban-Loritz-Pl. 2a Standorte: NN.MG Tura / College 6a - Naturwissenschaften Status: Verfügbar Frist: Vorbestellungen: 0
Inhalt
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
 
Details
VerfasserInnenangabe: Volker Turau ; Christoph Weyer
Jahr: 2015
Verlag: Berlin ; Boston, Mass., De Gruyter Saur
Systematik: NN.MG
ISBN: 978-3-11-041727-2
2. ISBN: 3-11-041727-8
Beschreibung: 4., erw. und überarb. Aufl., XIII, 401 S. : graph. Darst
Fußnote: Literaturverzeichnis: Seiten [389]-394. -
Mediengruppe: Buch