PB165 - 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)
eE+(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.
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).
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 - 0 0 * 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.
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.
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
)
eW+(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 Fp toku přes Cp 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í s a t
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 2 l v /
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):
Inicialiace 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) eW_(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