Čo je to zvyšková sieť a rozširujúca sa cesta?

Definujme tak zvyškové siete a rozširujúce sa cesty, najmä v kontexte algoritmov toku siete, ako sú metóda Ford-Fulkerson.

1. Zvyšková sieť:

Predstavte si, že máte sieť so zdrojom (S), umývadlom (T) a okrajmi s kapacitami predstavujúcimi maximálny prietok povolený cez každú hranu. A * Zostatková sieť * je reprezentáciou zostávajúcej kapacity v sieti * po tom, čo * cez ňu už bolo presunuté určité množstvo toku.

Takto to funguje:

* Hrany vpred: Pre každú hranu (u, v) v pôvodnej sieti s kapacitou C (u, v) a prúdom F (u, v), zvyšková sieť obsahuje zodpovedajúcu * prednú hranu * (u, v) s kapacitou C _{f (u, v) =c (u, v) - f (u, v). To predstavuje zostávajúcu kapacitu dostupnú na okraji.}

in Kľúčovou časťou je, že zvyšková sieť *tiež *obsahuje *spätné hrany *. Pre každú hranu (u, v) v pôvodnej sieti s prúdovým tokom f (u, v), zvyšková sieť obsahuje spätnú hranu (V, u) s kapacitou C _{f (v, u) =f (u, v). To predstavuje možnosť * posunúť tok späť * pozdĺž okraja, čím účinne zrušuje časť už odoslaných tokov. Kapacita spätnej hrany sa rovná toku, ktorý je momentálne na prednej hrane, pretože môžete len posunúť späť množstvo toku, ktorý už existuje.}

Zvyšková sieť v podstate ukazuje dostupnú kapacitu na zmeny toku. Dynamicky sa prispôsobuje, keď je tok presadzovaný cez sieť. Nájdenie dráhy rozšírenia (vysvetlené nižšie) v zvyškovej sieti znamená, že stále existuje potenciál zvýšiť celkový tok zo zdroja na umývadlo.

2. Augmenting Cesta:

Agmentujúca cesta * je jednoduchá cesta (bez opakovaných vrcholov) v zvyškovej sieti, ktorá vedie zo zdrojov (S) do umývadla (t). Je dôležité, že to predstavuje spôsob, ako zvýšiť celkový tok cez sieť.

Množstvo, pomocou ktorého sa dá tok zvýšiť pozdĺž rozširovacej cesty, je určené kapacitou *prekážky *. Toto je minimálna zvyšková kapacita medzi všetkými hranami v rozširovacej ceste.

Napríklad:

Ak má rozširovacia cesta hrany so zvyškovými kapacitou 5, 3 a 7, kapacita prekážky je 3. Potom môžeme zvýšiť tok pozdĺž tejto cesty o 3 jednotky. Tento proces aktualizuje tok v pôvodnej sieti a následne upravuje zvyškovú sieť.

Vzťah medzi zvyškovými sieťami a rozširujúcimi sa cestami:

Jadro mnohých algoritmov maximálneho toku (napríklad Ford-Fulkerson) je iteratívne:

1. Nájdite rozširujúcu cestu v súčasnej zvyškovej sieti.

2. Rozšíriť tok Pozdĺž tejto cesty kapacitou prekážky.

3. Aktualizujte zvyškovú sieť odrážať zmenu toku.

Tento proces pokračuje, až kým sa v zvyškovej sieti nenájdete žiadne ďalšie rozširujúce sa cesty, v ktorom sa dosiahol maximálny prietok. Tým sa zaručuje maximálny tok.

• Predchádzajúca strana: Plná forma VCC a VDD v TTL CMOS? 
• Ďalšia strana: Je na vašom zariadení príliš nízka virtuálna pamäť?