Netzwerkoptimierung

In der Netzwerkoptimierung werden graphentheoretische Probleme behandelt, welche häufig einfach zu beschreiben sind, jedoch äußerst schwierig zu lösen. Teilweise kommen hier bekannte Methoden etwa der ganzzahligen Optimierung zum Einsatz, oder aber es werden spezielle Verfahren angewandt. Zudem besteht aus didaktischer Sicht eine Herausforderung in der großen Anzahl an Definitionen und Bezeichnungen: Die Ideen und Verfahren sind zum Teil vergleichsweise simpel, allerdings aufgrund der ganzen Bezeichnungen und Schreibweisen schwer zu verstehen. Wir untersuchen in diesem Kapitel daher nur eine kleine Auswahl an graphentheoretischen Problemen, um die Anzahl der Definitionen und Notationen auf ein Minimum zu reduzieren, aber dennoch einen guten Einblick in die Grundlagen der Netzwerkoptimierung geben zu können. Wir beginnen in Abschn. 8.1 mit den wichtigsten Definitionen im Zusammenhang mit gerichteten sowie ungerichteten Graphen. Darauf aufbauend werden in den folgenden Abschnitten vier ausgewählte Probleme behandelt: Wir untersuchen spannende Bäume und lernen ein Verfahren kennen, wie diese effizient bestimmt werden können (Abschn. 8.2). Anschließend definieren wir Wege in gerichteten Graphen und stellen ein Verfahren vor, um kürzeste Wege zu bestimmen (Abschn. 8.3). Darauf aufbauend führen wir Flüsse ein, wobei das Problem darin besteht, maximale Flüsse unter Berücksichtigung von Kapazitätsschranken zu finden (Abschn. 8.4). Schließlich formulieren wir das Knotenfärbungsproblem, welches im Allgemeinen äußerst schwer zu lösen ist (Abschn. 8.5). Für spezielle Klassen von Graphen gibt es jedoch sehr effiziente Algorithmen. Genauer definieren wir chordale Graphen und zeigen, wie das Knotenfärbungsproblem dank eines perfekten Eliminationsschemas chordaler Graphen effizient gelöst werden kann.