Graphenalgorithmen

Dieses Programm wurde als Begleitung zur Vorlesung Informatik 1b (Datenstrukturen) erstellt. Es stellt einen der dort behandelten Graphenalgorithmen dar.

Was ist ein Graph ?

Wozu werden Graphenalgorithmen gebraucht ?

Das Flußproblem

Was ist ein Graph ? (Kurzbeschreibung)

Ein Graph wird als 2-Tupel bestehend aus einer Knotenmenge V und einer Kantemenge E definiert: G = (V,E)

Die Knoten symbolisieren Objekte und die Kanten modellieren Beziehungen zwischen diesen Objekten.

Man unterscheidet zwischen gerichteten und ungerichteten Graphen. Im gerichteten Fall ist die Kantenmenge E eine Teilmenge des kartesischen Produkts der Knotenmenge mit sich selbst: E ist Teilmenge von VxV.

In einigen Fällen werden den Kanten Gewichtungen c: E->R zugeordnet, die z.B. die Kosten einer Verbindung modellieren.

Wozu werden Graphenalgorithmen gebraucht ?

In der Praxis dienen Graphenalgorithmen zur Lösung von kombinatorischen Problemen.

Vorgehensweise:

1. Ein Problem wird als Graph modelliert
2. Es werden die Zielfunktion und Eigenschaften die Graphen formuliert
3. Das Problem wird mit Hilfe eines Graphenalgorithmus gelöst

Beispiele für Graphenalgorithmen sind:

• Kürzeste Wege Probleme
• Maximum Flow: Ziel ist es möglichst viele Einheiten (z.B. Güter) unter Einhaltung von Kantenkapazitäten von der Quelle zur Senke fließen zu lassen.
• Minimum Cost Flow: Mit minimalen Kosten bestimmte Nachfragen in Knoten durch Angebote in anderen Knoten über einen Fluß zu befriedigen.
• Bäume, insbesondere Suchbäume
• Travelling Salesman: Jeden Knoten besuchen
• Chinese Postman: Jede Kante besuchen

Das Flußproblem

Als einen Spezialfall von gewichteten, gerichteten Graphen betrachten wir Flüsse in Netzwerken. Das Gewicht einer Kante wird als Kapazität einer Rohrleitung interpretiert.
Analog läßt sich auch der Vehrkehrsfluß auf Straßen oder der Materialfluß in Produktionsprozessen modellieren.

Gegeben: G=(V,E) gerichtet und gewichtet mit c: E-> N. Die Gewichte c(i,j) werden hier als Kantenkapazitäten interpretiert. Zwei Knoten werden besonders ausgezeichnet, die Quelle s (Startknoten) und die Senke z (Zielknoten).

Fluß

Ein Fluß ist dann eine Funktion f: E-> R mit:

Erweiternder Weg

Ein erweiternder Weg in G ist eine Folge von Knoten, beginnend bei s und endend bei z, wobei für zwei aufeinanderfolgende Knoten i und j gilt:

Nach der Definition des erweiternden Weges ist es nun möglich den Fluß zu vergrößern, indem man ihn entlang der Vorwärtskanten erhöht, oder entlang der Rückwärtskanten verringert.

Der Fluß ist maximal, wenn es in G keine erweiternden Wege mehr gibt und alle Rückwärtskanten den Fluß 0 haben.

Der Algorithmus von Ford-Fulkerson (1962)

Finde einen zulässigen Fluß f in G

REPEAT

erhöhe diesen Fluß

UNTIL eine Erhöhung ist nicht mehr Möglich

Es gibt eine große Anzahl von Varianten und Verbesserungen zum Algorithmus von Ford-Fulkerson.

Das Applet

In der Textarea unten soll folgendes stehen:
1. Zeile Steuermeldungen und Erklärung des Algorithmus
2. Zeile Informationen über den Zustand der Graphen
3. Zeile Informationen zur aktuell berechneten Kante