Aký je problém s minimálnym rezom a ako sa používa pri optimalizácii toku siete?

Problém s minimálnym rezom

Problém minimálny rezy je základným problémom v teórii grafov a kombinatorickej optimalizácii. Vzhľadom na graf (buď nasmerovaný alebo namierený) s kapacitou priradenými k jeho okrajom a dvoma označenými vrcholmi, zdrojom (S) a umývadlom (T) je problém nájsť súbor hrán, ktorých odstránenie odpojí zdroj od umývadla a minimalizuje súčet kapacít týchto okrajov.

Inými slovami, a strih V grafe je rozdelenie vrcholov do dvoch disjunktných sád, S a T, takže zdroj * s * patrí do S a umývadlo * t * patrí do T. kapacity strihu je súčet kapacít hrán, ktoré idú od vrcholu v S do vrcholu v T. Minimálnym problémom rezu sa zameriava na nájdenie strihu s najmenšou kapacitou.

Formálne:

* Vstup:

* Graf g =(v, e), kde v je sada vrcholov a e je sada hrán.

* Funkcia kapacity C:E -> R+ priradenie nezápornej kapacity každej hranici.

* Zdrojový vrchol s ∈ V.

* Zvýšenie vrcholu t ∈ V.

* výstup:

* Oddiel (s, t) v tak, že s ∈ S, t ∈ T a kapacita rezu c (s, t) =σ c (u, v) (kde u ∈ S a V ∈ T) sa minimalizujú.

Príklad:

Predstavte si cestnú sieť, v ktorej má každá cesta určitú dopravnú kapacitu. Chcete nájsť minimálnu sadu ciest, ktoré potrebujete zatvoriť (rez), aby ste úplne zabránili prúdeniu premávky z mesta 'do mesta' t '. Celková kapacita týchto uzavretých ciest predstavuje náklady na zníženie a hľadáte najlacnejšiu (minimálnu kapacitu) súpravy uzávierok ciest.

Ako sa používa minimálny rez na optimalizáciu toku siete (maximálny tok Min-Cut Veta)

Spojenie medzi problémom s minimálnym rezom a optimalizáciou toku siete je hlboké a zachytené maximálnym tokom Min-Cut Tyorém . Táto veta uvádza, že:

Maximálne množstvo toku, ktorý sa dá odoslať zo zdroja do umývadla v sieti, sa rovná kapacite minimálneho rezu oddeľujúceho zdroj a umývadlo.

Tu je návod, ako sa hrá:

1. Problém s sieťovým tokom: Cieľom problému toku siete je nájsť maximálne množstvo „prietoku“ (napr. Údaje, kvapalina, elektrina), ktorú je možné odoslať zo zdroja do umývadla, s výhradou kapacitných obmedzení hrán.

2. Nájdenie maximálneho toku: Algoritmy ako Ford-Fulkerson alebo Edmonds-Karp sa používajú na nájdenie maximálneho toku v sieti.

3. týkajúce sa toku na rez: MAX-FLOW MIN-CUT TEOREM nám hovorí, že akonáhle sme našli maximálny tok, hodnota tohto toku * je * kapacita minimálneho zníženia.

4. Nájdenie minimálneho rezu: Aj keď môžeme odvodiť kapacitu minimálneho zníženia z maximálneho toku, často chceme vedieť *, ktoré okraje * predstavujú minimálny rez. Toto je možné nájsť pri pohľade na zvyškový graf po spustení algoritmu maximálneho toku:

* Zostatkový graf: Zvyškový graf je graf odvodený z pôvodného grafu, ktorý zobrazuje zostávajúcu kapacitu dostupnú v každej hrane (alebo schopnosť „vrátiť sa“ tokom pozdĺž okraja).

* Identifikácia minimálneho rezu: Po nájdení maximálneho prietoku vykonajte analýzu dostupnosti zvyškového grafu od zdroja. Všetky vrcholy dosiahnuteľné zo zdroja v zvyškovom grafe patria do set „s“ minimálneho rezu. Všetky ostatné vrcholy patria do súboru „T“. Hrany, ktoré prechádzajú z 's' do 't' v * Original * Graf, predstavujú minimálny rez.

v súhrne:

* Vyriešite problém s maximálnym tokom.

* Hodnota maximálneho prietoku sa rovná kapacite minimálneho rezu (maximálna toková míľová veta).

* Analýzou zvyškového grafu Po výpočte maximálneho prietoku môžete identifikovať konkrétne hrany, ktoré tvoria minimálny rez.

Prečo je to užitočné?

* Určenie prekážok: Minimálny rez identifikuje prekážky v sieti. Toto sú okraje, ktoré po odstránení najdôležitejšie obmedzujú tok zo zdroja na umývadlo.

* Pridelenie zdrojov: Pochopenie minimálneho zníženia pomáha pri efektívnom prideľovaní zdrojov. Môžete sa sústrediť na posilnenie hrán pri minimálnom znížení, aby ste zlepšili celkovú kapacitu siete.

* siete rozdelenie: Minimálny rez sa môže použiť na rozdelenie siete na dve slabo pripojené komponenty. To môže byť užitočné pri zoskupovaní problémov alebo pri identifikácii skupín uzlov, ktoré sú od seba relatívne nezávislé.

* Riešenie ďalších problémov: Problém s minimálnym znížením má aplikácie v rôznych oblastiach vrátane segmentácie obrazu, ťažby údajov a plánovania projektu. Mnohé z týchto problémov možno modelovať ako problémy s sieťovým tokom a vyriešiť sa pomocou maximálnej tokovej vety.

Príklad použitia v scenári:

Predstavte si energetickú mriežku, ktorá distribuuje elektrinu z elektrárne (zdroj) do mesta (umývadlo). Čiary majú rôzne kapacity. Ak vypočítame minimálny rez medzi elektrárňou a mestom, môžeme:

1. Poznajte maximálne množstvo elektriny, ktoré môže mesto prijímať (maximálny prietok =minimálna kapacita).

2. Identifikujte najzraniteľnejšie čiary (okraje v minimálnom strihu), ktoré by, ak by boli poškodené alebo preťažené, výrazne ovplyvnili dodávku elektriny do mesta.

3. uprednostňuje upgrady a údržbu týchto kritických línií (hrany minimálnych rezov), aby sa zvýšila celková spoľahlivosť energetickej mriežky.

Záverom možno povedať, že problém s minimálnym znížením, ktorý je prepojený vetou maximálneho toku s minimálnou optimalizáciou toku siete, poskytuje výkonný nástroj na analýzu a zlepšenie efektívnosti a robustnosti rôznych sieťových systémov.

• Predchádzajúca strana: Aká je dôležitosť synchronizácie počítačového zariadenia so serverom Network Time Server pre presné časové obdobie? 
• Ďalšia strana: Aké je riešenie maximálneho problému toku a ako pomáha optimalizovať zdroje v sieti?