Graphen und Netzwerke

    Grundlagen der Graphentheorie

    Definitionen und Begriffe

    Repräsentation von Graphen

    Ausgewählte Fragestellungen der Graphentheorie

    Bäume

    Wegeprobleme

    Wegeprobleme – Kürzeste Wege

    Dijkstra-Algorithmus

    Schema Dijkstra-Algorithmus

    Überlegungen zur Komplexität des Dijkstra-Algorithmus

    Kürzeste Wege und Lineare Optimierung

    Längste Wege

    Schema Längste Wege Algorithmus

    Flussprobleme

    Flussprobleme

    Maximaler Fluss, Minimaler Schnitt ( Min-Cut / Max-Flow)

    Ford-Fulkerson-Algorithmus anhand eines Beispiels

    Schema Ford-Fulkerson_Algorithmus

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.