Algorithmische Graphentheorie

Viele kombinatorische Probleme lassen sich auf die Bestimmung eines maximalen Flusses auf einem geeigneten Netzwerk zurückführen. Die in diesem Kapitel behandelten Anwendungen zeigen, dass die Netzwerktheorie ein mächtiges Werkzeug zur Lösung von Problemen ist, welche auf den ersten Blick nichts mit Netzwerken zu tun haben. Der erste Schritt besteht aus der Definition eines äquivalenten Netzwerkproblems. Danach können die im letzten Kapitel diskutierten Algorithmen verwendet werden. Mittels einer Rücktransformation kommt man dann zur Lösung des Ausgangsproblems. Zu Beginn dieses Kapitels wird die Bestimmung von maximalen Zuordnungen in bipartiten Graphen diskutiert. Im zweiten Abschnitt werden Netzwerke mit unteren und oberen Kapazitätsgrenzen betrachtet. Danach stehen Algorithmen zur Bestimmung der Kanten- und Eckenzusammenhangszahl eines ungerichteten Graphen im Mittelpunkt. Im Anschluss wird ein Algorithmus zur Bestimmung eines minimalen Schnittes vorgestellt. Der letzte Abschnitt behandelt Eckenüberdeckungen.

Kapitelübersicht

1. Einleitung
2. Einführung
3. Bäume
4. Suchverfahren in Graphen
5. Entwurfsmethoden für die algorithmische Graphentheorie
6. Färbung von Graphen
7. Perfekte Graphen
8. Flüsse in Netzwerken
9. Anwendungen von Netzwerkalgorithmen
   1. Maximale Zuordnungen
   2. Netzwerke mit oberen und unteren Kapazitäten
   3. Eckenzusammenhang in ungerichteten Graphen
   4. Kantenzusammenhang in ungerichteten Graphen
   5. Minimale Schnitte
   6. Eckenüberdeckungen
   7. Literatur
   8. Aufgaben
10. Kürzeste Wege
11. Approximative Algorithmen