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:


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

Farbe Rot Pink Blau Magenta
Knoten angeklickt ausgewählt Quelle Senke
Kante Wert wurde gerade berechnet ausgewählt Wert ist schon berechnet Wert hat sich verändert

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