|
Als Residualgraph oder Residual-Netzwerk eines Graphen  wird ein Graph  bezeichnet, der die übrigen Kantenkapazitäten anzeigt, nachdem ein Fluß angelegt wurde. Zwischen den Knoten  von befinden sich nun Residualkanten, die die noch nicht genutzte Kantenkapazität anzeigen und entgegengesetzt gerichtete Kanten, die die bereits genutzte Kantenkapazität anzeigen.
Weitere Bezeichnungen sind:
- Inkrementgraph
- Zuwachsgraph
Existiert in ein Pfad p zwischen Quelle s und Ziel t in Richtung t, so nennen wir diesen augmentierten Pfad (augmenting path). Dieser aus Residualkanten bestehende Pfad gibt einen weiteren möglichen Fluß an, der im Algorithmus von Ford und Fulkersonzur Verbesserung des maximalen Flusses genutzt wird.
Erst wenn keine augmentierten Pfade mehr existieren, wurde der maximale Fluß ermittelt.
Siehe auch
- Algorithmus von Ford und Fulkerson
- Flüsse und Schnitte in Netzwerken
Dieser Artikel basiert auf dem Artikel aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation.
In der Wikipedia ist eine Liste der Autoren verfügbar.
| 
