Kurs:Algorithmen und Datenstrukturen/Vorlesung/Flussproblem




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:  .

 

Definiere   durch

 .

Daraus folgt, dass   kein Fluss ist.

 

Definiere   durch

 .

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