Zurückblättern Weiterblättern Übergeordnetes Thema Sachgebiet Hauptinhaltsverzeichnis Stichwortverzeichnis Hilfeseiten        


Transportnetze


Transportnetz Ein zusammenhängender gerichteter Graph heißt Transportnetz , wenn in ihm zwei Knoten als Quelle bzw. Senke ausgezeichnet sind und folgende Eigenschaften gelten:
a) Es existiert ein Bogen von nach wobei der einzige Bogen mit dem Startknoten und der einzige Bogen mit dem Zielknoten ist.
b) Jedem von verschiedenen Bogen ist eine reelle Zahl seine Kapazität , zugeordnet. Der Bogen hat die Kapazität
Eine Funktion die jedem Bogen eine reelle Zahl zuordnet, heißt Strom auf , wenn für jeden Knoten die Gleichung
(5.340a)

gilt. Die Summe

(5.340b)

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

Beispiel Transportnetz

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



2. Maximalstrom-Algorithmus von Ford und Fulkerson Mit dem Maximalstrom-Algorithmus ist feststellbar, ob ein vorgegebener Strom maximal ist.
Es sei ein Transportnetz und ein mit den Kapazitäten verträglicher Strom der Stärke 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.
a) Man markiere und setze
b) Existiert ein Bogen mit markiertem , nichtmarkiertem und dann markiere man und setze und wiederhole Schritt b), anderenfalls folgt Schritt c).
c) Existiert ein Bogen mit nichtmarkiertem markiertem und dann markiere man und setze und führe, falls möglich, Schritt b) aus. Anderenfalls beende man den Algorithmus.
Wird die Senke von markiert, dann läßt sich der Strom in 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.