Algorithmische Graphentheorie · 4. Auflage by Turau, Volker -- Read -- Imperial Library of Trantor

Index

Cover Titel Impressum Inhalt 1 Einleitung

1.1 Verletzlichkeit von Kommunikationsnetzen 1.2 Wegplanung für Roboter 1.3 Optimale Umrüstzeiten für Fertigungszellen 1.4 Objektorientierte Programmiersprachen 1.5 Suchmaschinen 1.6 Analyse sozialer Netze 1.7 Literatur 1.8 Aufgaben

2 Einführung

2.1 Grundlegende Definitionen 2.2 Spezielle Graphen 2.3 Graphalgorithmen 2.4 Datenstrukturen für Graphen

2.4.1 Adjazenzmatrix 2.4.2 Adjazenzliste 2.4.3 Kantenliste 2.4.4 Bewertete Graphen 2.4.5 Implizite Darstellung

2.5 Der transitive Abschluss eines Graphen 2.6 Vergleichskriterien für Algorithmen 2.7 Implementierung von Graphalgorithmen 2.8 Testen von Graph-Algorithmen 2.9 Literatur 2.10 Aufgaben

3 Bäume

3.1 Einführung 3.2 Anwendungen

3.2.1 Hierarchische Dateisysteme 3.2.2 Ableitungsbäume 3.2.3 Suchbäume 3.2.4 Datenkompression

3.3 Datenstrukturen für Bäume

3.3.1 Darstellung mit Feldern 3.3.2 Darstellung mit Adjazenzlisten

3.4 Sortieren mit Bäumen 3.5 Vorrang-Warteschlangen 3.6 Minimal aufspannende Bäume

3.6.1 Der Algorithmus von Kruskal 3.6.2 Der Algorithmus von Prim

3.7 Literatur 3.8 Aufgaben

4 Suchverfahren in Graphen

4.1 Einleitung 4.2 Tiefensuche 4.3 Anwendung der Tiefensuche auf gerichtete Graphen 4.4 Kreisfreie Graphen und topologische Sortierung

4.4.1 Rekursion in Programmiersprachen 4.4.2 Topologische Sortierung

4.5 Starke Zusammenhangskomponenten 4.6 Transitiver Abschluss und transitive Reduktion 4.7 Anwendung der Tiefensuche auf ungerichtete Graphen

4.7.1 Bestimmung der Zusammenhangskomponenten 4.7.2 Durchsatz und Querschnitt 4.7.3 Anwendung in der Bildverarbeitung 4.7.4 Blöcke eines ungerichteten Graphen

4.8 Breitensuche 4.9 Lexikographische Breitensuche 4.10 Beschränkte Tiefensuche 4.11 Eulersche Graphen 4.12 Literatur 4.13 Aufgaben

5 Entwurfsmethoden für die algorithmische Graphentheorie

5.1 Problemarten 5.2 Greedy-Technik 5.3 Backtracking 5.4 Branch & Bound 5.5 Teile & Herrsche 5.6 Dynamische Programmierung 5.7 Lineare Programmierung 5.8 Literatur 5.9 Aufgaben

6 Färbung von Graphen

6.1 Einführung 6.2 Anwendungen von Färbungen

6.2.1 Maschinenbelegungen 6.2.2 Registerzuordnung in Compilern 6.2.3 Public-Key Kryptosysteme 6.2.4 Sudoku

6.3 Exakte Bestimmung der chromatischen Zahl

6.3.1 Backtracking-Verfahren 6.3.2 Teile & Herrsche 6.3.3 Dynamische Programmierung 6.3.4 Lineare Programmierung

6.4 Heuristiken zur Bestimmung von Färbungen 6.5 Das Vier-Farben-Problem 6.6 Kantenfärbungen 6.7 Literatur 6.8 Aufgaben

7 Perfekte Graphen

7.1 Einführung 7.2 Kreisfreie Orientierungen 7.3 Transitiv orientierbare Graphen

7.3.1 Charakterisierung von transitiv orientierbaren Graphen 7.3.2 Färbungen von transitiv orientierbaren Graphen

7.4 Permutationsgraphen

7.4.1 Charakterisierung von Permutationsgraphen 7.4.2 Färbungen von Permutationsgraphen

7.5 Chordale Graphen

7.5.1 Charakterisierung von chordalen Graphen 7.5.2 Färbungen von chordalen Graphen

7.6 Intervallgraphen

7.6.1 Gewichtete unabhängige Mengen in Intervallgraphen

7.7 Literatur 7.8 Aufgaben

8 Flüsse in Netzwerken

8.1 Einleitung 8.2 Schnitte und Erweiterungswege 8.3 Der Satz von Ford-Fulkerson 8.4 Bestimmung von Erweiterungswegen 8.5 Der Algorithmus von Dinic 8.6 0-1-Netzwerke 8.7 Kostenminimale Flüsse 8.8 Literatur 8.9 Aufgaben

9 Anwendungen von Netzwerkalgorithmen

9.1 Maximale Zuordnungen 9.2 Netzwerke mit oberen und unteren Kapazitäten 9.3 Eckenzusammenhang in ungerichteten Graphen 9.4 Kantenzusammenhang in ungerichteten Graphen 9.5 Minimale Schnitte 9.6 Eckenüberdeckungen 9.7 Literatur 9.8 Aufgaben

10 Kürzeste Wege

10.1 Einleitung 10.2 Das Optimalitätsprinzip 10.3 Der Algorithmus von Moore und Ford 10.4 Anwendungen auf spezielle Graphen

10.4.1 Graphen mit konstanter Kantenbewertung 10.4.2 Graphen ohne geschlossene Wege 10.4.3 Graphen mit nichtnegativen Kantenbewertungen 10.4.4 Graphen mit ganzzahligen nichtnegativen Kantenbewertungen

10.5 Bestimmung von Zentralitätsmaßen 10.6 Routingverfahren in Kommunikationsnetzen 10.7 Kürzeste-Wege-Probleme in der künstlichen Intelligenz

10.7.1 Der A⋆-Algorithmus 10.7.2 Der iterative A⋆-Algorithmus 10.7.3 Umkreissuche

10.8 Kürzeste Wege zwischen allen Paaren von Ecken 10.9 Der Algorithmus von Floyd 10.10 Steinerbäume 10.11 Literatur 10.12 Aufgaben

11 Approximative Algorithmen

11.1 Die Komplexitätsklassen P, NP und NPC 11.2 Einführung in approximative Algorithmen 11.3 Absolute Qualitätsgarantien 11.4 Relative Qualitätsgarantien 11.5 Approximative Algorithmen

11.5.1 Minimale Färbungen 11.5.2 Minimale Eckenüberdeckungen 11.5.3 Minimale dominierende Mengen 11.5.4 Maximale unabhängige Mengen 11.5.5 Minimale Steinerbäume

11.6 Das Problem des Handlungsreisenden 11.7 Literatur 11.8 Aufgaben

Die Graphen an den Kapitelanfängen Literatur Index

← Prev
Back
Next →

← Prev
Back
Next →