Kurs:Algorithmen und Datenstrukturen/Vorlesung/Flussproblem

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Flussproblem[Bearbeiten]

Auf dieser Seite wird das Flussproblem behandelt. Die Bestimmung des maximalen Flusses muss in vielen logischen Aufgaben angewandt werden. Beispielsweise bei Verteilungsnetzen mit Kapazitäten wie Wasserrohren, Förderbändern oder Paketvermittlungen mit Rechnernetzen. Die Quellen liefert beliebig viele Objekte pro Zeiteinheit und die Senke verbraucht diese. Jede Verbindung hat eine maximale Kapazität c und einen aktuellen Fluss f. Wie hoch ist nun die Übertragungskapazität?

Definition Fluss[Bearbeiten]

Ein Fluss f von nach ist eine Funktion . Für diese Funktion gelten folgende zwei Bedingungen:

  1. Die Kapazitäten werden eingehalten:
  2. Was in einen Knoten hereinfließt, muss wieder herausfließen, mit Ausnahme von q und z: , wobei der Vorgänger von v ist und der Nachfolger von v ist.

Einschränkungen der Kapazität der Kanten werden eingehalten, auch bei negativem Fluss:


Außerdem ist der Fluss konsistent. Bei in beiden Richtungen nutzbaren Verbindungen wird als Nettoeffekt nur in eine Richtung gesendet und der entstehende negative Fluss nimmt den korrekten Wert an:


Der Fluss wird für jeden Knoten mit Ausnahme der Quelle q und des Ziels z bewahrt:


Der Wert eines Flusses beträgt:


Gesucht wird der maximale Fluss:

 f ist korrekter Fluss von q nach z}


Beispiel[Bearbeiten]

Definiere durch

.

Daraus folgt, dass der Wert des Flusses 6 ist: .

BeispielMaximalerFluss1.png

Definiere durch

.

Daraus folgt, dass kein Fluss ist.

BeispielMaximalerFluss2.png

Definiere durch

.

Daraus folgt, dass der Wert des Flusses 14 ist: . Damit ist der Fluss maximal.

BeispielMaximalerFluss3.png


Vorheriges Kapitel.jpg Discussion Nächstes Thema.jpg