Algorithmische Graphentheorie

In vielen praktischen und theoretischen Anwendungen treten Situationen auf, die durch ein System von Objekten und Beziehungen zwischen diesen Objekten charakterisiert werden können. Die Graphentheorie stellt zur Beschreibung von solchen Systemen ein Modell zur Verfügung: den Graphen. Die problemunabhängige Beschreibung mittels eines Graphen lässt die Gemeinsamkeit von Problemen aus den verschiedensten Anwendungsgebieten erkennen. Die Graphentheorie ermöglicht somit die Lösung vieler Aufgaben, welche aus dem Blickwinkel der Anwendung keine Gemeinsamkeiten haben. Die algorithmische Graphentheorie stellt zu diesem Zweck Verfahren zur Verfügung, die problemunabhängig formuliert werden können. Ferner erlauben Graphen eine anschauliche Darstellung, welche die Lösung von Problemen häufig erleichtert.

Im Folgenden werden sechs verschiedene Anwendungen diskutiert. Eine genaue Betrachtung der Aufgabenstellungen führt ganz natürlich auf eine graphische Beschreibung und damit auch auf den Begriff des Graphen; eine Definition wird bewusst erst im nächsten Kapitel vorgenommen. Die Beispiele dienen als Motivation für die Definition eines Graphen; sie sollen ferner einen Eindruck von der Vielfalt der zu lösenden Aufgaben geben und die Notwendigkeit von effizienten Algorithmen vor Augen führen.

Kapitelübersicht

1. Einleitung
   1. Verletzlichkeit von Kommunikationsnetzen
   2. Wegplanung für Roboter
   3. Optimale Umrüstzeiten für Fertigungszellen
   4. Objektorientierte Programmiersprachen
   5. Suchmaschinen
   6. Analyse sozialer Netze
   7. Literatur
   8. Aufgaben
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
10. Kürzeste Wege
11. Approximative Algorithmen