Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


33. Fluß in einem Netzwerk



Das Problem des Flusses in einem Netzwerk

Betrachten wir die idealisierte Skizze eines kleinen Netzwerks von Ölleitungen in Abbildung 33.1. Die Leitungen besitzen eine feste Kapazität, die zu ihrer Größe proportional ist, und Öl kann nur bergab fließen (von oben nach unten). Weiterhin wird mit Hilfe von Schiebern an jeder Verzweigungsstelle gesteuert, wieviel Öl in jede Richtung fließt. Unabhängig von der Stellung der Schieber erreicht das System einen Gleichgewichtszustand, wenn die Ölmenge, die oben in das System hineinfließt, gleich der Ölmenge ist, die unten hinausfließt (dies ist die Menge, die wir maximieren wollen), und wenn die Ölmenge, die in jede Verzweigungsstelle hineinfließt, gleich der hinausfließenden Ölmenge ist. Wir messen sowohl die Durchflußmenge als auch die Kapazität der Leitungen in ganzzahligen Einheiten (zum Beispiel in Litern pro Sekunde).

Abbildung 33.1
Abbildung 33.1 Maximaler Fluß in einem einfachen Netzwerk.

Es ist nicht unmittelbar ersichtlich, daß die Schieberstellungen tatsächlich die maximale Gesamt-Durchflußmenge beeinflussen können; Abbildung 33.1 veranschaulicht, daß dies möglich ist. Nehmen wir zuerst an, daß der die Leitung AB steuernde Schieber geöffnet ist, wobei er diese Leitung füllt, Leitung BD füllt und DF beinahe füllt, wie es die linke Skizze in der Abbildung zeigt. Nehmen wir dann an, daß Leitung AC geöffnet ist, und daß Schieber C so eingestellt ist, daß er Leitung CD schließt und Leitung CE öffnet (vielleicht hat der Bediener von Schieber D den Bediener von Schieber C darüber informiert, daß bei ihm aufgrund des von B kommenden Stroms nicht mehr viel zusätzliches Öl passieren kann). Den resultierenden Fluß zeigt die mittlere Skizze der Abbildung: Die Leitungen BD und CE sind voll. Die Durchflußmenge könnte nun noch etwas vergrößert werden, indem über den Pfad ACDF eine Ölmenge geleitet wird, die ausreicht, um Leitung DF zu füllen; es existiert jedoch eine bessere Lösung, wie die dritte Skizze zeigt. Durch Umstellung des Schiebers B in der Weise, daß eine Ölmenge umgeleitet wird, die ausreicht, um BE zu füllen, wird in Leitung DF eine genügend große Kapazität frei, die es gestattet, mit Hilfe des Schiebers C Leitung CD vollständig zu öffnen. Die Gesamtmenge, die in das Netzwerk hinein und aus ihm hinaus fließt, läßt sich also erhöhen, indem man die geeigneten Schieberstellungen ermittelt.

Unsere Aufgabe besteht darin, einen Algorithmus zu entwickeln, der für jedes beliebige Netzwerk die »richtigen« Schieberstellungen finden kann. Weiterhin möchten wir die Gewißheit haben, daß keine andere Schieberstellung eine höhere Durchflußmenge ergeben würde.

Diese Situation kann offenbar mit Hilfe eines gerichteten Graphen modelliert werden, und es zeigt sich, daß die von uns untersuchten Programme zur Anwendung kommen können. Wir definieren ein Netzwerk als einen gewichteten gerichteten Graph mit zwei hervorgehobenen Knoten: einem Knoten, auf den keine Kanten zeigen (der Quelle), und einem Knoten, von dem keine Kanten wegführen (der Senke). Die Gewichte an den Kanten, die wir als nichtnegativ voraussetzen, werden Kapazitäten der Kanten genannt. Ein Fluß ist dann als eine weitere Menge von Gewichten an den Kanten definiert, wobei der Fluß in jeder Kante kleiner oder gleich der Kapazität ist, und der Fluß in jeden Knoten hinein gleich dem Fluß aus dem Knoten hinaus ist. Der Wert des Flusses ist der Fluß in die Quelle hinein (oder aus der Senke hinaus). Das Problem des Flusses in einem Netzwerk besteht darin, für ein gegebenes Netzwerk einen Fluß mit maximalem Wert zu finden.

Für Netzwerke können offensichtlich die Darstellungen mittels Adjazenzmatrix oder Adjazenzliste verwendet werden, die wir in den vorangegangenen Kapiteln für Graphen benutzt haben. Anstelle eines einzigen Gewichts sind mit jeder Kante zwei Gewichte verknüpft, Kapazität und Fluß. Diese können als zwei Felder in einem Knoten der Adjazenzliste dargestellt werden, als zwei Matrizen bei der Darstellung mittels Adjazenzmatrix oder als zwei Felder innerhalb eines einzigen Datensatzes bei jeder der beiden Darstellungsarten. Obwohl Netzwerke gerichtete Graphen sind, müssen bei den Algorithmen, die wir betrachten wollen, Kanten in der »falschen« Richtung durchlaufen werden, weshalb wir eine Darstellung mit Hilfe eines ungerichteten Graphen verwenden: Falls eine Kante von x nach y mit Kapazität s und Fluß f existiert, führen wir auch eine Kante von y nach x mit Kapazität -s und Fluß -f ein. Bei einer Darstellung mittels Adjazenzliste ist es erforderlich, die beiden die jeweilige Kante repräsentierenden Listenknoten zu verbinden, so daß wir, wenn wir den Fluß in einem Knoten ändern, ihn in dem anderen aktualisieren können.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]