Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy PB165 - Grafy a sítě 9. Toky v síti Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Obsah přednášky Q Řezy v grafu Q Toky v síti Q Algoritmy pro maximální tok Q Další problémy Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Neformálně: • Rozříznutí grafu napříč hranami (nikoliv skrz vrcholy) na dvě poloviny. • Rozdělení vrcholů na dvě části. Definice Řezem v grafu G = (V, E) nazýváme rozklad množiny V na 2 neprázdné podmnožiny P, P. Wc(P) je množina všech hran, jejichž jeden vrchol je v P a druhý nikoliv. Jelikož se jedná o rozklad, platí: PnP = 0, PUP=V Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Řezy v grafu Obrázek: Příklady řezů v grafu jsou vyznačeny čárkovaně. ID> <1> « o^o Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Definice Necht řez C dělí vrcholy na množiny P, P. O hranách (u,v), jejichž jeden vrchol leží v P a druhý nikoliv, říkáme že křižují řez C. Obrázek: Hrany křižující řezy Q, C2 jsou vyznačeny modře. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Definice Bipartitní graf je takový graf G, jehož množina vrcholů je disjunktním sjednocením dvou množin S a T a platí E(G) = Wc(S). Množiny S a T nazýváme stranami bipartitního grafu. Každá hrana grafu G má jeden vrchol v S a druhý v T. Definice Úplný bipartitní graf je takový bipartitní graf, jehož každý dvojice vrcholů (s, t), s G S a t G T je spojena právě jednou hranou. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Definice Vahou řezu v hranově neohodnoceném grafu označujeme počet hran, které tento řez křižují. V hranově ohodnoceném grafu se vahou rozumí součet ohodnocení všech hran křižujících tento řez. Obrázek: Váha řezu Q v neohodnoceném grafu je rovna 4. Váha řezu C2 v ohodnoceném grafu je rovna 17. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Definice Minimálním rozumíme takový řez v grafu, jehož váha je minimální. Maximální fez je naopak ten s maximální vahou. Minimální řez v grafu může být nalezen v čase polynomiálním vůči velikosti grafu. Naopak, problém maximálního řezu je NP-úplný. Obrázek: Minimální řez ve vyobrazeném grafu je vyznačen zeleně, maximální červeně. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Definice Sítí nazýváme orientovaný, hranově ohodnocený graf G = (V, E). Definice Tokem v síti nazýváme takové ohodnocení hran reálnými čísly f:E(G) —> M., které pro každý vrchol v splňuje Kirchhoffův zákon £ f(e)= £ f(e) eeE+(v) eeE-(v) Takový g raf si můžeme představit jako soustavu potrubí, pro níž platí zákon zachování hmoty, tj. kolik do vrcholu přitéká, tolik z něj zase vytéká. Orientace hrany určuje směr proudění, záporný tok představuje proudění proti směru hrany. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Pokud Kirchhoffův zákon platí pro všechny vrcholy, mluvíme o cirkulaci. Alternativou je tzv. tok od zdroje ke spotřebiči, kde dva vrcholy Kirchhoffův zákon nesplňují. Ve zdroji tok vzniká a ve spotřebiči (stok, výlevka, sink) zaniká. Tok od zdroje ke spotřebiči můžeme vždy převést na cirkulaci přidáním hrany spojující zdroj a spotřebič. Takovou hranu nazýváme návratovou hranou. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Zpravidla omezujeme tok na hraně shora i zdola, tj. platí f(e) G (/(e),c(e)). Číslo c(e) nazýváme kapacitou hrany, případně horním omezením toku v hraně. Číslo /(e) nazýváme dolním omezením toku v hraně. Tok, který splňuje /(e) < f(e) < c(e) pro všechny hrany e nazýváme přípustným tokem. V řadě praktických případů bývá dolní omezení toku zpravidla rovno 0, je-li však nenulové, není a priori jasné, zda existuje přípustný tok v síti. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Výše definované s/řějsou vhodnými reprezentacemi reálných sítí. Klasická teorie grafů se velmi často věnuje problémům toků na železničních, silničních a dalších dopravních sítích. Samostatnou oblastí jsou rozvodné sítě - vodovodní, plynové atd. Obecně mluvíme o transportních sítích. Většina úloh je věnována optimalizaci takovýchto sítí, případně nalezení úzkých míst, maximální kapacity (propustnosti) sítě, garance minimální propustnosti i při výpadku některých linek či vrcholů apod. Pro nás jsou zajímavé toky v počítačových sítích. Na řešení úloh s toky lze převést i řadu plánovacích úloh, např. tzv. přiřazovacíúlohy. V těch máme za úkol přiřadit n úkolů mezi pracovníky tak, abychom minimalizovali náklad (provedení konkrétní úlohy konkrétním pracovníkem má svou cenu). Lze převést na bipartitní graf (pracovníci jsou zdroje a úlohy jsou spotřebiče, hrana představuje cenu práce). Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Definice Reziduálni kapacitou hrany e rozumíme číslo c(e) — ^(e), tj. rozdíl kapacity hrany a aktuálního toku. Reziduálni kapacity hran tvoří reziduálni síť. V mnoha případech potřebujeme zjistit, zda reziduálni síť existuje. Hrany s reziduálni kapacitou nula nejsou v reziduálni síti obsaženy (není možné přes ně vést nenulový tok). Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Velikost toku značíme F(f). Velikost toku od zdroje ke spotřebiči definujeme jako množství toku, které vzniká ve zdroji s. F(f)= £ f(e)- E f(e) ee£+(s) eeE-(s) E+, E označují součet toků vstupujících do vrcholu, resp. vystupujících z něj. Obrázek: Velikost vyobrazeného toku (11) je dána množstvím toku opouštějícím zdroj. 5 -00.0 Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Nechť řez C dělí vrcholy grafu na množiny P,P. Označíme jej Cp. Dále nechť zdroj toku náleží do množiny P a spotřebič do P.Potom má smysl definovat velikost Fp toku přes řez Cp jako rozdíl mezi velikostí toku na hranách vedoucích z množiny P a velikostí toku na hranách vedoucích do této množiny. Říkáme, že řez Cp odděluje zdroj a spotřebič. FP(f)= y, f(e)- E f(e) eeW+(P) eew-(P) 1/1/+, l/l/- značí hrany vycházející z množiny l/l/, resp. do ní vstupující. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Věta Nechť Cp je libovolný řez, který odděluje zdroj a spotřebič. Potom pro velikost Fp toku přes Cp platí _FP{f) = Fjf)_ Přes všechny řezy oddělující zdroj a spotřebič tedy protéká stejný tok. Obrázek: Přes všechny vyznačené (i nevyznačené) řezy oddělující s a t protéká tok o velikosti 11. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Důkaz. Důkaz povedeme indukcí: Základ indukce: Položme P = {s}, kde s je zdroj toku. Tvrzení platí z definice. Indukční krok: Do množiny P přidáme libovolný vrchol grafu, různý od spotřebiče. Jelikož pro tento vrchol musí platit Kirchhoffův zákon, nezmění se nikterak rozdíl mezi velikostmi toků z P vytékajících a do P vtékajících. Platnost tvrzení se tedy nezmění. Jelikož postupným přidáváním vrcholů lze získat libovolný řez, který odděluje zdroj od spotřebiče, platí tvrzení pro všechny řezy zdroj od spotřebiče oddělující. □ Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Kapacita řezu oddělujícího zdroj a spotřebič specifikuje, jaký maximální tok může tímto řezem protéct. Definována je jako součet kapacit všech hran, které tento řez protínají ve směru od zdroje ke spotřebiči zmenšená o součet minimálních kapacit hran opačně orientovaných. c(cP)= y, c(e)- E '(e) eeW+(P) eew-(p) Obrázek: Kapacity řezů Q,..., C4 jsou po řadě 16, 18, 17, 15. Kapacita řezu má význam pro nalezení tzv. maximglníhOjtoku. v grafu. s ^,0,0 Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Problém maximálního toku je hledání největšího toku v grafu od zdroje ke spotřebiči. Následující podmínky jsou ekvivalentní: O Tok f je maximální (maximalizujeme F(f)). O \f\ je kapacita některého řezu oddělujícího zdroj od spotřebiče. O V reziduálni síti neexistuje cesta ze zdroje ke spotřebiči. Algoritmy pro nalezení maximálního toku vycházejí z těchto ekvivalencí - hledají řez s minimální kapacitou nebo přidávají cesty mezi zdrojem a spotřebičem, dokud nějaké v reziduálni síti existují. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy • Nejednodušší algoritmus. • Generuje postupně všechny podmnožiny vrcholů, pro každý provede následující kroky: • Najde mezi hranami všechny, které křižují řez definovaný touto množinou vrcholů. • Sečte kapacity hran křižujících tento řez, směřujících od zdroje ke spotřebiči. • Výsledkem je řez s minimální vypočtenou kapacitou. Jelikož všech řezů oddělujících zdroj od spotřebiče je 2lv/l~2 — 1, pro každý je potřeba zkontrolovat všech \E\ hran, celková časová složitost algoritmu hledání maximálního toku brutální silou je 0(2M-2|E|) /(e) pro hranu vzad. Definice říká, že aktuální tok lze zvýšit na hranách vpřed a snížit na hranách vzad o nějakou hodnotu d > 0. Definice Kapacitou zlepšující cesty pak rozumíme maximální hodnotu d, o kterou lze tok na zlepšující cestě změnit. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy • Využívá ekvivalence mezi maximalitou toku a neexistencí cesty ze zdroje ke spotřebiči v reziduálni síti. • Hledá zlepšující cesty mezi zdrojem a spotřebičem, dokud nějaká taková existuje. • Pro hledání cest používá i zpětných hran. • Z hran na cestě se vybere ta, jejíž reziduálni kapacita je minimální. • V případě zpětné hrany (projité proti směru její orientace) se namísto hodnoty c(e) — f(e) bere tok, který hranou protéká ve směru její orientace - tedy f(e) — l(e). Toky se takto mohou vzájemně anulovat. • O tuto minimální kapacitu se zvýší tok po všech dopředných hranách na nalezené cestě. • Naopak, na hranách zpětných se hodnota toku sníží o stejnou hodnotu. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Můžeme použít značkovací proceduru (Py(e) je počáteční a Ky(e) je koncový vrchol hrany e): nicializace Označkujeme vrchol zdroje, ostatní jsou bez značek. Vpřed Existuje-li hrana e taková, že Py(e) m^ značku a Ky(e) nemá a současně platí f(e) < c(e), pak označkuj Ky(e). Vzad Existuje-li hrana e taková, že Ky(e) má značku a Py(e) nemá a současně /(e) < ^(e), pak označkuj Py(e). Ukončení Je-li označkován spotřebič, nalezli jsme zlepšující cestu. Nelze-li další vrchol označkovat, pak zlepšující cesta neexistuje. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Pro všechny hrany (u,v) I f(u,v) = 0 Dokud existuje zlepšující cesta p: I Vyber minimální kapacitu d hrany na této cestě. I Pro všechny hrany na cestě p: I | f(u,v) = f(u,v) + d I | f(v,u) = f(v,u) - d Algoritmus neříká, jakým způsobem se má cesta ze zdroje ke spotřebiči hledat. V praxi se používá obvykle průchod do hloubky, nebo průchod do šířky, čímž se z algoritmu stává Edmonds-Karpův (viz dále). 4Ľ3k4l3*4 = k4 = * -š -O^O Řezy v grafu Toky v síti Algoritmy pro maximální tok - příklad Další problémy Obrázek: Příklad běhu Ford-Fulkersonova algoritmu, 1. část. < □ ► (e)f(e). eeE Úkolem je potom najít maximální tok sítí takový, že jeho cena bude zároveň minimální. 4Ľ3k4l3*4 = k4 = * -š -O^O Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Pokud se omezíme na cirkulace, je celá řada algoritmů (a odpovídající teorie) jednodušší. A platí, že úlohy týkající se přípustného toku od zdroje ke spotřebiči lze převést na hledání přípustné cirkulace přidáním návratové hrany. Věta V síti s omezeními toku I a c existuje přípustná cirkulace právě tehdy, když každý řez má nezápornou kapacitu c{cP)= y, c(e)- E /(e)^° eeW+{P) eeW-{P) Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Vstupem je síť G s omezeními toku /, c a libovolná (i nulová) cirkulace f. Výstupem je buď přípustná cirkulace f nebo řez se zápornou kapacitou. O Najdeme hranu h s nepřípustným tokem. Pokud taková hrana neexistuje, výpočet končí a dosavadní tok f je přípustný. O Je-li f(h) < l(h), pak z := Kv(h),s := Py{h), v opačném případě (f(h) > c{h)) z := Pv(h),s:= Kv{h). Q Nalezneme zlepšující cestu z vrcholu z do vrcholu s. Pokud cesta neexistuje, výpočet končí, přípustná cirkulace neexistuje a množina označkovaných vrcholů P určuje řez Cp, který má zápornou hodnotu. O Pokud cesta existuje, doplníme zlepšující cestu o hranu h, čímž vznikne zlepšující kružnice. Vypočteme její kapacitu, změníme toky na jejích hranách (viz předchozí algoritmy). Pak se vracíme zpět na krok 1.