Graphen und Netzwerke

Die Graphentheorie beschäftigt sich mit Graphen und Netzwerken, sie ist ein Teilgebiet der diskreten Mathematik. Eine ganze Reihe von Optimierungsproblemen lässt sich mithilfe von Graphen und Netzwerken anschaulich modellieren. Außerdem stehen für viele dieser Probleme leistungsfähige Algorithmen zur Verfügung, die es erlauben, mit vergleichsweise geringem Aufwand Lösungen zu finden.

In den ersten Kapiteln dieses Teils erfolgt eine kurze Einführung grundlegender Begriffe der Graphentheorie (1. Kapitel) und eine exemplarischer Vorstellung von klassischen Fragestellungen (2. Kapitel). Im 3. Kapitel werden Bäume im Sinne der Graphentheorie vorgestellt.

In den darauffolgenden Kapiteln geht es dann um Algorithmen, die für die Lösung typischer Fragestellung aus Logistik, Verkehrswesen und Produktion eine besondere Relevanz haben. Die Algorithmen sind allerdings sehr grundlegend und ihr Anwendungsbereich beschränkt sich nicht auf die vorgenannten Bereiche.

So befasst sich das 4. Kapitel mit kürzesten Wegen, das 5. Kapitel mit längsten Wegen und schließlich geht es im 6. Kapitel um Flussmaximierung. Dabei wird jeweils die Idee der Algorithmen vorgestellt, ein Beispiel vorgerechnet und an einigen Stellen auch der Bezug zur Linearen Optimierung hergestellt.

Zu Beginn noch ein Hinweis zur Rechtschreibung. In diesem Text wird die altmodische Schreibung Graph verwendet. Die Schreibung „Graf“ ist ebenso korrekt und eigentlich logischer, sie hat sich aber nicht durchsetzen können.