Robert Sedgewick: Algorithmen

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


33. Fluß in einem Netzwerk



Das Verfahren von Ford-Fulkerson

Der klassische Ansatz für das Problem des Flusses in einem Netzwerk wurde 1962 von L. R. Ford und D. R. Fulkerson entwickelt. Sie gaben ein Verfahren an, wie ein beliebiger zulässiger Fluß (natürlich mit Ausnahme des maximalen) erhöht werden kann. Mit einem Null-Fluß beginnend, wenden wir das Verfahren wiederholt an. Solange das Verfahren angewandt werden kann, erzeugt es einen größeren Fluß; wenn es nicht mehr angewandt werden kann, liegt bereits der maximale Fluß vor. Der Fluß in Abbildung 33.1 wurde tatsächlich unter Anwendung dieses Verfahrens ermittelt; wir betrachten ihn nun nochmals unter Benutzung der in Abbildung 33.2 gezeigten Darstellung mittels eines Graphen.

Abbildung 33.2
Abbildung 33.2 Bestimmung des maximalen Flusses in einem Netzwerk.

Zur Vereinfachung verzichten wir auf die Pfeile, da sie alle nach unten zeigen. Die Verfahren, die wir betrachten, sind nicht auf Graphen beschränkt, deren Kanten alle in eine Richtung zeigen. Wir verwenden solche Graphen, da sie das Verständnis des Flusses in einem Netzwerk durch die Veranschaulichung mit Hilfe von in Leitungen fließenden Flüssigkeiten erleichtern.

Betrachten wir einen (nach unten) gerichteten Pfad durch das Netzwerk (von der Quelle zur Senke). Es ist klar, daß der Fluß wenigstens um den kleinsten Betrag der ungenutzten Kapazität jeder Kante des Pfades erhöht werden kann, indem der Fluß in allen Kanten des Pfades um diesen Betrag vergrößert wird. Bei der linken Skizze in Abbildung 33.2 wird diese Regel längs des Pfades ABDF angewandt; bei der mittleren Skizze wird sie dann längs des Pfades ACEF angewandt.

Wie bereits erwähnt wurde, könnten wir dann die Regel längs des Pfades ACDF anwenden, womit eine Situation geschaffen würde, in der alle gerichteten Pfade durch das Netzwerk wenigstens eine Kante aufweisen, die ihrer Kapazität entsprechend gefüllt ist. Es gibt jedoch noch einen anderen Weg, den Fluß zu erhöhen: Wir können beliebige Pfade durch das Netzwerk betrachten, die Kanten enthalten können, die in die »falsche Richtung« zeigen (von der Senke zur Quelle längs des Pfades). Der Fluß längs eines solchen Pfades kann erhöht werden, indem der Fluß in von der Quelle zur Senke zeigenden Kanten erhöht und in von der Senke zur Quelle zeigenden Kanten um den gleichen Betrag verringert wird. In unserem Beispiel kann der Fluß durch das Netzwerk längs des Pfades ACDBEF um 3 erhöht werden, wie die dritte Skizze in Abbildung 33.2 zeigt. Wie oben beschrieben wurde, entspricht dies dem Hinzufügen von 3 Einheiten zum Fluß durch AC und CD und dem anschließenden Umleiten von 3 Einheiten am Schieber B von BD nach BE und EF. Der Fluß in DF verringert sich nicht, da 3 Einheiten, die zuvor von BD kamen, nun von CD kommen.

Um die Terminologie zu vereinfachen, wollen wir Kanten, die längs eines Pfades von der Quelle zur Senke zeigen, Vorwärts-Kanten nennen, und Kanten, die von der Senke zur Quelle gerichtet sind, Rückwärts-Kanten. Wir bemerken, daß der Betrag, um den der Fluß erhöht werden kann, durch das Minimum der ungenutzten Kapazitäten in den Vorwärts-Kanten und das Minimum der Flüsse in den Rückwärts-Kanten begrenzt ist. Mit anderen Worten, in dem neuen Fluß wird wenigstens eine der Vorwärts-Kanten längs des Pfades voll, oder es wird wenigstens eine der Rückwärts-Kanten leer. Weiterhin kann der Fluß auf keinem Pfad erhöht werden, der eine volle Vorwärts-Kante oder eine leere Rückwärts-Kante enthält.

Aus dem obigen Absatz ergibt sich ein Verfahren, wie der Fluß in einem beliebigen Netzwerk erhöht werden kann, vorausgesetzt, daß ein Pfad ohne volle Vorwärts-Kanten oder leere Rückwärts-Kanten gefunden werden kann. Die entscheidende Tatsache für das Verfahren von Ford-Fulkerson ist die Bemerkung, daß, wenn kein solcher Pfad gefunden werden kann, der Fluß maximal ist.

Eigenschaft 33.1 Falls jeder von der Quelle zur Senke führende Pfad in einem Netzwerk eine volle Vorwärts-Kante oder eine leere Rückwärts-Kante aufweist, ist der Fluß maximal.

Um diese Tatsache zu beweisen, gehen wir zuerst durch den Graph und identifizieren auf jedem Pfad die erste volle Vorwärts-Kante oder leere Rückwärts-Kante. Diese Menge von Kanten zerschneidet den Graph in zwei Teile. (In unserem Beispiel bilden die Kanten AB, CD und CE einen solchen Schnitt.) Für jeden Schnitt, der das Netzwerk in zwei Teile zerlegt, können wir den Fluß »durch« den Schnitt messen: die Summe der Werte des Flusses in den Kanten, die von der Quelle zur Senke zeigen. Im allgemeinen können Kanten in beiden Richtungen durch den Schnitt verlaufen; um den Fluß durch den Schnitt zu erhalten, muß die Summe der Werte des Flusses in den Kanten, die in der anderen Richtung verlaufen, subtrahiert werden. Für unser Beispiel eines Schnittes beträgt der Wert 12, was gleich dem gesamten Fluß für das Netzwerk ist. Es zeigt sich, daß wir immer dann, wenn der Fluß durch einen Schnitt gleich dem Gesamtfluß ist, nicht nur wissen, daß der Fluß maximal ist, sondern auch, daß der Schnitt minimal ist (das heißt, jeder andere Schnitt hat einen wenigstens ebenso großen »Durchfluß«). Dies wird der Satz über den maximalen Fluß und den minimalen Schnitt (maxflow-mincut theorem) genannt: Der Fluß könnte nicht mehr größer werden (andernfalls müßte auch der Schnitt größer sein), und es existieren keine kleineren Schnitte (andernfalls müßte auch der Fluß kleiner sein). Wir verzichten auf Einzelheiten dieses Beweises. w.z.b.w.


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