Transportnetze

Transportnetz

Ein zusammenhängender gerichteter Graph heißt Transportnetz, wenn in ihm zwei Knoten als Quelle Q bzw. Senke S ausgezeichnet sind und folgende Eigenschaften gelten:

1. Es existiert ein Bogen u₁ von S nach Q, wobei u₁ der einzige Bogen mit dem Startknoten S und der einzige Bogen mit dem Zielknoten Q ist.
2. Jedem von u₁ verschiedenen Bogen u_i ist eine reelle Zahl seine Kapazität, zugeordnet. Der Bogen u₁ hat die Kapazität

Eine Funktion die jedem Bogen eine reelle Zahl zuordnet, heißt Strom auf G, wenn für jeden Knoten v die Gleichung

gilt. Die Summe

heißt Stromstärke. Ein Strom heißt mit den Kapazitäten verträglich, wenn für jeden Bogen u_i von G gilt:

Beispiel

Transportnetz.

2. Maximalstrom-Algorithmus von Ford und Fulkerson

Mit dem Maximalstrom-Algorithmus ist feststellbar, ob ein vorgegebener Strom maximal ist.
Es sei G ein Transportnetz und ein mit den Kapazitäten verträglicher Strom der Stärke v₁. Der Algorithmus beinhaltet die folgenden Schritte zur Markierung von Knoten, nach deren Ausführung man ablesen kann, um welchen Betrag die Stromstärke in Abhängigkeit von den ausgewählten Markierungsschritten verbessert werden kann.

1. Man markiere Q und setze
2. Existiert ein Bogen e_i=(x,y) mit markiertem x, nichtmarkiertem y und dann markiere man y und setze und wiederhole Schritt b), anderenfalls folgt Schritt c).
3. Existiert ein Bogen e_i=(x,y) mit nichtmarkiertem x, markiertem und dann markiere man x und (x,y), setze und führe, falls möglich, Schritt b) aus. Anderenfalls beende man den Algorithmus.

Wird die Senke S von G markiert, dann läßt sich der Strom in G um verbessern. Wird die Senke nicht markiert, dann ist der Strom maximal.

Beispiel Maximalstrom

Im Graphen der oberen Abbildung geben die Bewertungen der Kanten die Kapazitäten der Kanten an. Im bewerteten Graphen der unteren Abbildung ist ein mit diesen Kapazitäten verträglicher Strom der Stärke 13 dargestellt. Es handelt sich dabei um einen Maximalstrom.

Beispiel Transportnetz

Ein Produkt wird von p Firmen hergestellt. Es gibt q Verbraucher In einem bestimmten Zeitraum werden s_i Einheiten von F_i produziert und t_j Einheiten von V_j benötigt.
In der vorgegebenen Zeit können c_ij Einheiten von F_i nach V_j transportiert werden. Können in diesem Zeitraum alle Bedarfswünsche erfüllt werden? Den zugehörigen Graphen zeigt die folgende Abbildung.