Laten we zowel resterende netwerken als uitbreidingspaden definiëren, vooral binnen de context van netwerkstroomalgoritmen zoals de Ford-Fulkerson-methode.
1. Resterend netwerk:
Stel je voor dat je een netwerk hebt met een bron (s), een put (t) en randen met capaciteiten die de maximale stroom vertegenwoordigen die door elke rand is toegestaan. Een *restnetwerk* is een weergave van de resterende capaciteit in het netwerk *nadat* er al een bepaalde hoeveelheid stroom doorheen is geduwd.
Hier is hoe het werkt:
* Voorwaartse randen: Voor elke rand (u, v) in het oorspronkelijke netwerk met capaciteit c(u, v) en stroom f(u, v), omvat het resterende netwerk een overeenkomstige *voorwaartse rand* (u, v) met capaciteit cf (u, v) =c(u, v) - f(u, v). Dit vertegenwoordigt de resterende capaciteit die beschikbaar is aan de rand.
* Achterwaartse randen: Het cruciale onderdeel is dat het resterende netwerk *ook* *achterwaartse randen* omvat. Voor elke rand (u, v) in het oorspronkelijke netwerk met stroom f(u, v) bevat het restnetwerk een achterwaartse rand (v, u) met capaciteit cf (v, u) =f(u, v). Dit vertegenwoordigt de mogelijkheid om de stroom langs de rand *terug te duwen*, waardoor een deel van de reeds verzonden stroom effectief wordt geannuleerd. De capaciteit van de achterrand is gelijk aan de stroom die momenteel op de voorrand staat, omdat je alleen de hoeveelheid stroom die er al is, kunt terugdringen.
In essentie toont het restnetwerk de beschikbare capaciteit voor veranderingen in de stroom. Het past zich dynamisch aan terwijl de stroom door het netwerk wordt geduwd. Het vinden van een vergrotend pad (hieronder uitgelegd) in het resterende netwerk betekent dat er nog steeds potentieel is om de totale stroom van de bron naar de put te vergroten.
2. Verbeteringspad:
Een *augmenterend pad* is een eenvoudig pad (geen herhaalde hoekpunten) in het restnetwerk dat van de bron(nen) naar de put (t) leidt. Cruciaal is dat het een manier is om de totale stroom door het netwerk te vergroten.
De mate waarmee de stroom langs het vergrotingstraject kan worden vergroot, wordt bepaald door de *knelpuntcapaciteit*. Dit is de minimale restcapaciteit van alle randen in het vergrotingspad.
Bijvoorbeeld:
Als een vergrotend pad randen heeft met een restcapaciteit van 5, 3 en 7, is de bottleneckcapaciteit 3. We kunnen de stroom langs dit pad dan met 3 eenheden vergroten. Dit proces werkt de stroom in het oorspronkelijke netwerk bij en wijzigt vervolgens het resterende netwerk.
Relatie tussen resterende netwerken en augmentatiepaden:
De kern van veel max-flow-algoritmen (zoals Ford-Fulkerson) is iteratief:
1. Vind een uitbreidingspad in het huidige restnetwerk.
2. Vergroot de stroom langs dat pad door de knelpuntcapaciteit.
3. Update het resterende netwerk om de verandering in de stroom weer te geven.
Dit proces gaat door totdat er geen vergrotende paden meer te vinden zijn in het restnetwerk, waarna de maximale doorstroming is bereikt. De max-flow min-cut-stelling garandeert dit. |