Algorithmische Graphentheorie

In diesem Kapitel werden Suchstrategien für Graphen behandelt. Sie bilden die Grundlage für viele graphentheoretische Algorithmen, in denen die Ecken oder Kanten systematisch durchlaufen werden müssen. In Kapitel 3 wurde dies bereits für Suchbäume abgehandelt. Die vorgestellten Suchstrategien Tiefensuche und Breitensuche verallgemeinern diese Techniken, so dass sie auf beliebige Graphen anwendbar sind. Es wird zunächst das Grundprinzip der Tiefensuche vorgestellt. Danach werden Anwendungen der Tiefensuche auf gerichtete Graphen diskutiert: Topologische Sortierungen, Bestimmung der starken Zusammenhangskomponenten und Bestimmung des transitiven Abschluss und der transitiven Reduktion. Daran schließen sich Anwendungen auf ungerichtete Graphen an: Bestimmung der Zusammenhangskomponenten und der Blöcke. Im Folgenden wird die Breitensuche eingeführt. Im vorletzten Abschnitt wird eine Variante der Tiefensuche behandelt, welche nur wenig Speicherplatz verbraucht und auf implizite Graphen anwendbar ist. Das Kapitel endet mit einem Abschnitt über Eulersche Graphen.

Kapitelübersicht

1. Einleitung
2. Einführung
3. Bäume
4. Suchverfahren in Graphen
   1. Einleitung
   2. Tiefensuche
   3. Anwendung der Tiefensuche auf gerichtete Graphen
   4. Kreisfreie Graphen und topologische Sortierung
   5. Starke Zusammenhangskomponenten
   6. Transitiver Abschluss und transitive Reduktion
   7. Anwendung der Tiefensuche auf ungerichtete Graphen
   8. Breitensuche
   9. Lexikographische Breitensuche
   10. Beschränkte Tiefensuche
   11. Eulersche Graphen
   12. Literatur
   13. Aufgaben
5. Entwurfsmethoden für die algorithmische Graphentheorie
6. Färbung von Graphen
7. Perfekte Graphen
8. Flüsse in Netzwerken
9. Anwendungen von Netzwerkalgorithmen
10. Kürzeste Wege
11. Approximative Algorithmen