Låt oss definiera både resterande nätverk och förstärkande vägar, särskilt inom ramen för nätverksflödesalgoritmer som Ford-Fulkerson-metoden.
1. Restnätverk:
Föreställ dig att du har ett nätverk med en källa (er), ett handfat (t) och kanter med kapacitet som representerar det maximala flödet som tillåts genom varje kant. A * Rest Network * är en representation av den återstående kapaciteten i nätverket * efter * en viss flöde har redan skjutits genom det.
Så här fungerar det:
* Framåtkanter: För varje kant (U, V) i det ursprungliga nätverket med kapacitet C (U, V) och strömflödet F (U, V) inkluderar det restnätverket en motsvarande * framkant * (U, V) med kapacitet C f (u, v) =c (u, v) - f (u, v). Detta representerar den återstående kapaciteten som finns på kanten.
* bakåtkanter: Den avgörande delen är att det återstående nätverket *också *inkluderar *bakåtkanter *. För varje kant (U, V) i det ursprungliga nätverket med nuvarande flöde F (U, V) innehåller det återstående nätverket en bakåtkant (V, U) med kapacitet C f (v, u) =f (u, v). Detta representerar möjligheten att * skjuta flödet tillbaka * längs kanten och effektivt avbryta ut något av det redan skickade flödet. Kapaciteten för den bakåtkanten är lika med flödet för närvarande på framkanten, eftersom du bara kan skjuta tillbaka mängden flöde som redan finns.
I huvudsak visar det återstående nätverket den tillgängliga kapaciteten för förändringar i flödet. Den anpassar sig dynamiskt när flödet skjuts genom nätverket. Att hitta en förstärkande väg (förklaras nedan) i det återstående nätverket innebär att det fortfarande finns potential att öka det totala flödet från källan till diskbänken.
2. Förstärkningsväg:
En * förstärkande väg * är en enkel väg (inga upprepade vertikaler) i det återstående nätverket som leder från källan till diskbänken (t). Av avgörande betydelse representerar det ett sätt att öka det totala flödet genom nätverket.
Det belopp som flödet kan ökas längs förstärkningsvägen bestäms av *flaskhalskapaciteten *. Detta är den minsta restkapaciteten bland alla kanter i förstärkningsvägen.
Till exempel:
Om en förstärkande väg har kanter med återstående kapacitet på 5, 3 och 7, är flaskhalskapaciteten 3. Vi kan sedan öka flödet längs denna väg med 3 enheter. Denna process uppdaterar flödet i det ursprungliga nätverket och modifierar därefter det återstående nätverket.
Förhållandet mellan restnätverk och förstärkningsvägar:
Kärnan i många max-flödesalgoritmer (som Ford-Fulkerson) är iterativt:
1. Hitta en förstärkande väg i det nuvarande restnätverket.
2. förstärker flödet längs den vägen med flaskhalskapaciteten.
3. Uppdatera det återstående nätverket för att återspegla förändringen i flödet.
Denna process fortsätter tills inga fler förstärkningsvägar finns i det återstående nätverket, vid vilken tidpunkt det maximala flödet har uppnåtts. Max-flödet min-cut teorem garanterar detta.
