Algorithmische Graphentheorie

Ein wichtiges Anwendungsgebiet der Graphentheorie ist die Darstellung von Verkehrs- und Kommunikationsnetzen sowie die Bestimmung optimaler Wege in diesen. Dabei wird ein Weg als optimal betrachtet, wenn er der kürzeste, der billigste oder der sicherste ist. Die dargestellten Algorithmen bestimmen Wege, für welche die Summe der Bewertungen der Kanten minimal ist. Die Interpretation der Bewertungen bleibt der eigentlichen Anwendung überlassen. Es werden drei Varianten betrachtet: der kürzeste Weg zwischen zwei vorgegebenen Ecken, kürzeste Wege zwischen einer und allen anderen Ecken und kürzeste Wege zwischen allen Paaren von Ecken. Die Verfahren lassen sich sowohl auf gerichtete als auch auf ungerichtete Graphen anwenden. Dieses Kapitel stützt sich wesentlich auf die Entwurfsmethode der dynamischen Programmierung. Neben allgemeinen Verfahren werden im vierten Abschnitt auch solche diskutiert, welche nur auf Graphen mit speziellen Eigenschaften anwendbar sind. Der fünfte Abschnitt stellt Algorithmen zur Analyse sozialer Netzwerke vor. Danach werden Algorithmen zur Bestimmung von kürzesten Wegen diskutiert, wie sie in der künstlichen Intelligenz angewendet werden. Im Mittelpunkt des letzten Abschnitts dieses Kapitels steht ein Algorithmus zur Bestimmung eines minimalen Steinerbaumes.

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
10. Kürzeste Wege
    1. Einleitung
    2. Das Optimalitätsprinzip
    3. Der Algorithmus von Moore und Ford
    4. Anwendungen auf spezielle Graphen
    5. Bestimmung von Zentralitätsmaßen
    6. Routingverfahren in Kommunikationsnetzen
    7. Kürzeste-Wege-Probleme in der künstlichen Intelligenz
    8. Kürzeste Wege zwischen allen Paaren von Ecken
    9. Der Algorithmus von Floyd
    10. Steinerbäume
    11. Literatur
    12. Aufgaben
11. Approximative Algorithmen