P B165 - Grafy a sítě 9. Toky v síti □ S Obsah přednášky Q Řezy v grafu Q Toky v síti Algoritmy pro maximální tok O Další problémy □ s Řez v grafu 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. Wq{P) je množina všech hran, jejichž jeden vrchol je v P a druhý nikoliv. Jelikož se jedná o rozklad, platí: PnP = 0, pu~p=v □ S Řezy v grafu V každém grafu existuje 2'v' 1 — 1 řezů. Obrázek: Příklady řezů v grafu jsou vyznačeny čárkovaně. □ s Hrany křižující řezy Definice Nechi ř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. □ g - = Bipartitnf grafy Definice Bipartitinígrafje takový graf G, Jehož množina vrcholů je disjunktním sjednocením dvou množin S a T a platí E(G) = Wg(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ý bipartitnf graf je takový bipartitnf graf jehož každý dvojice vrcholů (s, ŕ), s G S a t G T je spojena právě jednou hranou. Váha řezu Definice Vahou řezu v hranově neohodnocenem 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 C\ v neohodnocenem grafu je rovna 4. Váha řezu C2 v ohodnoceném grafu je rovna 17. □ s Minimální a maximální řez Definice Minimálním rozumíme takový řez v grafu, jehož váha je minimální. Maximální řez 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ě. Sít a tok 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) —> R, které pro každý vrchol v splňuje Kirchhoffův zákon E '(e) e£E+(v) eeE-(v) f(e) Takový graf 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. □ s Cirkulace a zdroj a spotřebič Pokud Kirchhoffův zákon platí pro všechny vrcholy, mluvíme o cirkulaci. Alternativou je tv. 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. 22 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 1(e) nazýváme dolním omezením toku v hraně. Tok, který splňuje 1(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. Výše definované sítě 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). 22 Reziduálni tok Definice Reziduálni kapacitou hrany e rozumíme číslo c(e) — f (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). Toky v síti - příklad Obrázek: Příklad toku v síti. První číslo v hodnocení hrany je tok, druhé kapacita hrany n S - = -E -00*0 Velikost toku Velikost toku značíme F(f). Velikost toku od zdroje ke spotřebiči definujeme jako množství toku, které vzniká ve zdroji s. e£E+(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. Velikost toku přes řez 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)= E f(e)- E f(e) e€W+(P) eew-(P) W+, W značí hrany vycházející z množiny W, resp. do ní vstupující. Shodnost toků přes řezy Necht Cp je libovolný řez, který odděluje zdroj a spotřebič. Potom pro velikost F p toku přes C p platí Fp{f) = F{f) 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í sat protéká tok o velikosti 11. Shodnost toků přes řezy - 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í. D □ s 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ě orienovaných. c{cP)= J2 c(e)- E /(e) eeW+(P) eeW-(P) Obrázek: Kapacity řezů Q,..., C4 jsou po řadě 16, 18, 17, 15. c4 t ---------># 11/15 ^^ Kapacita řezu má význam pro nalezení tzv. maximálního toku v grafu. m 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)). Q \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í. Algoritmus - brutální síla • Nejjednodušší 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|) Zlepšující cesta Definice Hranu nazveme hranou vpřed, je-li orientována v smeru průchodu cestou. Hrana vzad je pak orientována proti směru průchodu cestou. Definice Zlepšující cestou vzhledem k toku f nazveme takovou neorientovanou cestu ze zdroje ke spotřebiči, jejíž každá hrana splňuje f(e) < c(e) pro hranu e vpřed a f(e) > 1(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. Ford-Fulkersonův algoritmus • 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) — 1(e). Toky se takto mohou vzájemně anulovat. • 0 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. Můžeme použít značkovací proceduru (/~V(e) je počáteční a KV(e) je koncový vrchol hrany e): nicializace Označkujeme vrchol zdroje, ostatní jsou bez značek. Vpřed Existuje-li hrana e taková, že /~V(e) má značku a KV(e) nemá a současně platí f(e) < c(e), pak označkuj KV(e). Vzad Existuje-li hrana e taková, že KV(e) má značku a /~V(e) nemá a současně 1(e) < f(e), pak označkuj /~V(e). Ukončení Je-li označkovan spotřebič, nalezli jsme zlepšující cestu. Nelze-li další vrchol označkovat, pak zlepšující cesta neexistuje. 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). □ g - = ^ -00*0 Ford-Fulkersonův algoritmus - příklad Obrázek: Příklad běhu Ford-Fulkersonova algoritmu, 1. část. □ s - = ■€. -o<\(y Ford-Fulkersonův algoritmus - příklad Obrázek: Příklad běhu Ford-Fulkersonova algoritmu, 2. část. Minimální řez je vyznačen na posledním obrázku. Kapacita je 21, což je i maximální tok v tomto grafu. □ s • V obecném případě není možné dokázat, že běh algoritmu skončí. • V některých případech nemusí hodnota nalezeného toku ani konvergovat k maximu. V reálných aplikacích jsou kapacity hran obvykle reprezentovány celými čísly. To zaručuje ukončení běhu algoritmu: • Maximální tok má v takovém případě také celočíselnou hodnotu. o Časová složitost nalezení zlepšující cesty je 0(|E|) • S každou nalezenou zlepšující cestou se hodnota nalezeného toku zvýší minimálně o 1. • Maximálně může tedy proběhnout nejvýše F(f) iterací. □ g - = ^ -00*0 • Specializace Ford-Fulkersonova algoritmu. • Pro hledání zlepšujících cest je použit průchod do šířky. • Pro potřeby průchodu do šířky jsou délky hran považovány za jednotkové. • Průchod do šířky zajistí, že každá nalezená zlepšující cesta je nejméně tak dlouhá, jako předchozí nalezená. o Maximální možná délka zlepšující cesty je \V\. • Složitost algoritmu tak činí Ö(VE2). Edmonds-Karpův algoritmus - příklad 0/100 Ford-Fulkerson Edmonds-Karp 100/100 100/100 100/100 t s 100/100 Obrázek: V horní části obrázku je znázorněn možný počátek běhu Ford-Fulkersonova algoritmu. Běh může pokračovat stejným způsobem i nadále, a tak potřebovat mnoho iterací. Edmonds-Karpův algoritmus nalezne odpověď během 2 iterací. □ s Omezení toku vrcholem Reálné aplikace mohou klást i omezení na velikost toku procházejícího vrcholem - např. sběrné místo kanalizací, aktivní prvek v síti, rychlost zpracování dat na příjemci. Pokud jsou toky nezáporné, lze použít následující transformaci grafu: Obrázek: Vrchol je nahrazen dvěma vrcholy a hranou. Vrchol v s omezenou kapacitou nahradíme vrcholy vi, V2, jejichž kapacita nebude omezena. Hrany směřující do v přesměrujeme do v\, hrany z v vycházející budou vycházet z V2. Vrcholy v\, V2 spojíme hranou, jejíž kapacita bude rovna původní kapacitě vrcholu v. Na takový graf je poté možno použít standardní algoritmy pro hledání maximálního toku. Několik zdrojů a spotřebičů Obdobně lze standardní algoritmy použít i v případě, kdy zadání obsahuje více než 1 zdroj nebo spotřebič: ^ K síti přidáme fiktivní zdroj a spotřebič. Z nově přidaného zdroje povedou hrany (s „neomezenou" kapacitou) do všech zdrojů, obdobně přidáme hrany ze všech spotřebičů do nově přidaného. Ke každé hraně je krom její kapacity definována i cena a(e) jednotkového toku. Cena toku hranou e je potom rovna a(e)f(e). Celková cena toku sítí je potom definována jako 5>(e)r(e). Úkolem je potom najít maximální tok sítí takový, že jeho cena bude zároveň minimální. Prípustná cirkulace 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 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) e€W_(P) Vstupem je síť G s omezeními toku I, 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čia dosavadní tok f je přípustný. O Je-li f (ti) < 1(h), pak z := Kv(h),s := Py{H), v opačném případě (f(h) > c(h)) z := Pv(h),s:= Kv{h). 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. Q 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. □ g - = ^ -00*0