Definieren wir sowohl verbleibende Netzwerke und Augmenting-Pfade, insbesondere im Kontext von Netzwerkflussalgorithmen wie der Ford-Fulkerson-Methode.
1. Restnetzwerk:
Stellen Sie sich vor, Sie haben ein Netzwerk mit einer Quelle (n), einer Spüle (T) und Kanten mit Kapazitäten, die den maximalen Fluss darstellen, der durch jede Kante zulässig ist. Ein * Restnetzwerk * ist eine Darstellung der verbleibenden Kapazität im Netzwerk * Nach * wurde bereits ein bestimmter Durchfluss durchgedrückt.
So funktioniert es:
* Vorwärtskanten: Für jede Kante (u, v) im ursprünglichen Netzwerk mit Kapazität C (U, V) und Stromfluss F (U, V) enthält das Restnetzwerk eine entsprechende * Vorwärtskante * (u, v) mit Kapazität C f (u, v) =c (u, v) - f (u, v). Dies stellt die verbleibende Kapazität an, die am Rand verfügbar ist.
* Rückwärtskanten: Der entscheidende Teil ist, dass das Restnetz *auch * *Rückwärtskanten *enthält. Für jede Kante (u, v) im ursprünglichen Netzwerk mit dem Stromfluss F (U, V) enthält das Restnetz eine Rückwärtskante (v, u) mit Kapazität c f (v, u) =f (u, v). Dies stellt die Möglichkeit dar, den Fluss nach hinten * entlang der Kante zurückzudrängen und einen Teil des bereits gesendeten Flusses effektiv abzubrechen. Die Kapazität der Rückwärtskante entspricht dem derzeitigen Fluss am Vorwärtskante, da Sie nur die bereits vorhandene Flussmenge zurückschieben können.
Im Wesentlichen zeigt das Restnetz die verfügbare Kapazität für Änderungen des Flusses. Es passt dynamisch an, wenn der Fluss durch das Netzwerk gedrückt wird. Wenn Sie einen Augmenting -Pfad finden (unten erklärt) im Restnetzwerk, besteht immer noch das Potenzial, den Gesamtfluss von der Quelle zur Senke zu erhöhen.
2. Erweiterungspfad:
Ein * Augmenting -Pfad * ist ein einfacher Pfad (keine wiederholten Eckpunkte) im Restnetzwerk, das von der Quelle (n) zur Senke (t) führt. Entscheidend ist, dass es eine Möglichkeit darstellt, den Gesamtfluss durch das Netzwerk zu erhöhen.
Die Menge, durch die der Fluss entlang des Augmenting -Pfades erhöht werden kann, wird durch die *Engpasskapazität *bestimmt. Dies ist die minimale Restkapazität unter allen Kanten im Augmenting -Pfad.
Zum Beispiel:
Wenn ein Augmenting -Pfad Kanten mit Restkapazitäten von 5, 3 und 7 aufweist, beträgt die Engpasskapazität 3. Wir können den Fluss entlang dieses Pfades um 3 Einheiten erhöhen. Dieser Prozess aktualisiert den Fluss im ursprünglichen Netzwerk und verändert anschließend das Restnetzwerk.
Beziehung zwischen Restnetzwerken und Augmenting -Pfaden:
Der Kern vieler Max-Flow-Algorithmen (wie Ford-Fulkerson) ist iterativ:
1. einen Augmenting -Pfad finden im aktuellen Restnetz.
2. den Fluss erweitern Auf diesem Weg durch die Engpasskapazität.
3. Aktualisieren Sie das Restnetz die Änderung des Flusses widerspiegeln.
Dieser Prozess wird fortgesetzt, bis im Restnetz nicht mehr Augmenting -Pfade gefunden werden können. An diesem Punkt wurde der maximale Fluss erreicht. Der Max-Flow Min-Cut-Theorem garantiert dies.
