Graphen spielen in der Welt der Algorithmen eine zentrale Rolle. Beispielsweise verwenden Navigationsgeräte zur Beantwortung einer Routenanfrage einen Algorithmus zur Berechnung kürzester Wege in einem Graphen. Auch viele Planungs- und Zuweisungsprobleme lassen sich leicht als Probleme auf Graphen modellieren. Im Prinzip gilt, dass man sehr viele Probleme als Graphenprobleme auffassen kann, weshalb der Entwurf effizienter Algorithmen für solche Probleme ein wichtiges Teilgebiet der theoretischen Informatik darstellt.
In dieser Vorlesung begeben wir uns in die Welt der Graphenalgorithmen. Dabei werden wir einerseits wichtige algorithmische Problemklassen auf Graphen und effiziente Algorithmen zu deren Lösung kennenlernen. Unter anderem werden wir uns mit dem Finden von kürzesten Wegen, Flüssen, Schnitten, Separatoren und Matchings in Graphen befassen. Algorithmen für diese Probleme haben vielfältigste Anwendungsmöglichkeiten und sind somit ein wichtiges und nützliches Werkzeug für jeden Algorithmiker. Andererseits werden wir auch untersuchen, inwiefern sich Einschränkungen an die vorliegenden Graphen auf die Komplexität der Probleme und deren algorithmische Lösung auswirkt. Beispielsweise sind viele algorithmische Probleme auf Bäumen und planaren Graphen (d.h. Graphen die kreuzungsfrei in die Ebene eingebettet werden können) effizienter lösbar, als auf allgemeinen Graphen. Außerdem werden wir einige Eigenschaften von Graphen untersuchen, die wir gezielt für den Entwurf von effizienten Algorithmen ausnutzen können. Beispielsweise haben Bäume und planare Graphen kleine Separatoren (Knotenmengen, deren Entfernung die Graphen in mehrere Zusammenhangskomponenten zerfallen lassen), was dabei hilft effiziente Divide & Conquer Algorithmen zu entwerfen.
Ziel der Vorlesung ist die Entwicklung und Schulung einer strukturierten Herangehensweise an algorithmische Probleme auf Graphen. Wir entwickeln dabei gemeinsam effiziente Graphenalgorithmen mit passenden Datenstrukturen, beweisen deren Korrektheit und analysieren deren Ressourcenbedarf (Laufzeit und Speicherplatz). Außerdem wird die Vorlesung spezielle Graphklassen und andere wichtige Konzepte der Graphentheorie und deren Auswirkung auf die Welt der Algorithmen beleuchten.
