6   Toky v sítích
Nyn í se pod íváme ještě na jednu oblast uloh, kde nasla teorie grafu bohaté uplatněn í (konkrétně orientované grafy). Jde o oblast tzv. „sítových" uloh:
Jedna se treba o potrubn í síte prepravuj íc í vodu nebo plyn, o dopravn í sít silnic s prepravou zboZ í, nebo treba o internet prenasej íc í data. Obvykle nas zaj íma problem prenest z daneho zdroje do daneho c íle cili stoku co nejv íce teto substance, za omezuj íc ích podm ínek kapacit jednotlivých prepravn ích cest.
5
StruCny přehled lekce
• Definice sítě (ohodnoceného orientovaného grafu) a toku v ní.
• Algoritmus nenasycených cest.
• DUsledky pro souvislost, parovaní a vyber reprezentantu.
Petr Hliněný,  FI MU Brno_1_FI: MA010: Toky v sítích
5
6.1   Definice sítě
Základní strukturou pro reprezentaci sítí je orientovaný graf. Vrcholy grafu modelují jednotlivé uzly síte a hrany jejich spojnice.
Definice 6.1. Síť je ctverice S = (G, z, s, w), kde
- G je orientovaný graf,
- vrcholy z G V (G), s G V (G) jsou zdroj a stok,
- w : E(G) — R+ je kladne ohodnocení hran, zvane kapacita hran.
4
5
Poznámka: V praxi může být zdrojů a stoků více, ale v definici stačí pouze jeden zdroj a stok, z nehož / do nejž vedou hraný do ostatních zdrojů / stoků. (Dokonce pak různe zdroje a stoký mohoů mít sve kapacity.)
Petr Hlín
ny.
FI MU Brno
: MA010: Toky v sítích
5
Značení: Pro jednoduchost p íšeme ve výrazech znak e — v pro hranu e přicházej íc í do vrcholu v a e — v pro hranu e vycházej íc í z v. c
Definice 6.2. Tok v s íti S = (G, z, s, w) je funkce f : E (G) — R++ splnuj ící
- Ve G E (G) : 0 < f (e) < w(e),
- Vv G V (G),v = z, s :   E f (e)= E f (e). c
e—>v e<—v
Velikost toku f je dana výrazem ||f || = E f (e) — E f (e). c
e——z e—>z
Značení: Tok a kapacitu hran v obrazku síte budeme zjednoduSene zapisovat ve formatu F/C, kde F je hodnota toku na hrane a C je její kapacita.
Petr Hliněný,  FI MU Brno_3_FI: MA010: Toky v sítích
Neformálně tok znamená, kolik substance je každou hranou zrovna přenášeno (ve směru této hrany, proto hrany musí být orientovane). Tok je pochopitelne nezaporny a dosahuje nejvýše dane kapacity hrany.
2/5
2/4 -
3/3
3/5
Ve vyobrazenem príklade vede ze zdroje vlevo do stoku vpravo tok o celkove velikosti 5. c Poznámka: Obdobne se da velikost toku definovat u stoku, nebot
o = E (/(e) -f= E ÍEf(e) - Ef= E ÍEf(e) - Ef■
e£E vGV \e——v e—>v /        v = z,s \e——v e—>v /
(SCítance uprostred predchozího vztahu nabývají nulove hodnoty pro vsechny vrcholy v krome z a s dle definice toku.) Proto velikost toku poatana u zdroje je rovna opacne velikosti toku pocítaneho u stoku.
Petr Hlín
FI MU Brno
: MA010: Toky v sítích
6.2   Hledání maximálního toku
Naším úkolem je naj ít co největší tok v dane síti. Pro jeho nalezen í existuj í jednoduché a velmi rychle algoritmy.
Problém 6.3. Maximáln ího toku v s íti
Je dana st S = (G, z, s, w) a našim úkolem je pro ni najít co největší tok ze zdroje z do stokú s vzhledem k ohodnocení w. c
3/5
Petr Hliněný,  FI MU Brno 5 FI: MA010: Toky v sítích
4/5
Jak však poznáme, ze větší tok již v dane síti neexistuje? V teto konkrétní ukázce to nen í obt ížne, vid íme totiž, že obe dve hrany přicházej íc í do stoku maj í soucet kapacit 2 + 4 + 6, takze více nez 6 do stoku ani pritect nemuze. c
V obecnosti lze pouzít obdobnou uvahu, kdy najdeme podmnozinu hran, ktere nelze tokem „obej ít" a ktere v součtu kapacit daj í velikost naseho toku. Existuje vsak takova mnozina hran vzdy? Odpoved' nam da nasleduj íc í definice a veta.
Petr Hliněný,  FI MU Brno_6_FI: MA010: Toky v sítích
Definice 6.4. Řez v síti S = (G, z, s, w)
je podmnožina hran C C E (G) taková, ze v podgrafu G — C (tj. po odebrání hran C z G) nezbude žádná orientovana cesta že z do s.
Velikosti řezu C rozumíme souCet kapacit hran z C, tj. ||C|| =    eec w(e). c
Veta 6.5. Maximální velikost toku v síti je rovna minimální velikosti řezu.
Na následuj íc ím obrázku vid íme trochu jinou síť s ukázkou netriviáln ího minimáln ího rezu velikosti 5, náznáCeneho svislou Cárkovánou Čárou. VSimnete si dobre, Ze definice rezu mluv í o preruSen í vsech orientovaných cest ze z do s, tákze do rezu stáC í zápoC ítát hrány jdouc í pres svislou cáru od z do s, ále ne hránu jdouc í zpet. Proto je velikost vyznáceneho rezu 1+4 = 5.
1
Poznámka: Táto vetá poskytuje tzv. dobrou charakterizaci problemu máximáln ího toku: Kdyz uz nálezneme máximáln í tok, ták je pro nás vzdy snádne dokázát, ze leps í tok nen í, nálezen ím príslusneho rezu o stejne velikosti. Pritom toto zduvodnen í řezem muzeme smele ukázát i nekomu, kdo se moc nevyzná v mátemátice.
Petr Hliněný,  FI MU Brno_7_FI: MA010: Toky v sítích
Nenasycené cesty v síti
Definice: Mejme síť S a v ní tok f. Nenasycena cesta (v S vzhledem k f) je neorientovaná cesta v G z vrcholu u do vrcholu v (obvykle ze z do s), tj. posloupnost navazujících hran ei, e2,..., em, kde f (ej) < w(ej) pro ej ve smeru z u do v a f (ej) > 0 pro ej v opacnem smeru. c
Hodnote w(ej) — f (ej) pro hrany ej ve smeru z u do v a hodnote f (ej) pro hrany ej v opacnem smeru ríkame rezerva kapacity hran ej. Nenasycení cesta je tudíz cesta s kladnými rezervami kapacit vsech hran. c
Zde vidíme příklad nenasycené cesty ze zdroje do stoku s minimální rezervou kapacity +1.
^3/4        1/2        1/1 2/3 2/4^
rezerva kapacity:        +1 +1 +1 +2 +2
Vsimnete si dobre, ze cesta nen í orientovana, takze hrany na n í jsou v obou smerech.
Petr Hliněný,  FI MU Brno
: MA010: Toky v sítích
4
Algoritmus 6.6. Ford-FulkersonUv pro tok v síti.
vstup  sít S = (G, z, s, w); tok f = 0; repeat {
Prohledáváním grafu najdeme množinu U vrcholu G, do kterých se dostaneme ze z po nenasycených cestách; if ( s G U ) {
P = (výše nalezená) nenasycená cesta v S ze z do s;
Zvětšíme tok f o minimální rezervu kapacity hran v P;
}
until ( s G U );
výstup   vypíšeme maximální tok f;
vystup   vypíšeme min. řez jako mnoiinu hran vedoucích z U do V(G) — U.
Petr Hlín
FI MU Brno
: MA010: Toky v sítích
1
Důkaz správnosti Algoritmu 6.6:
Pro káždý tok f á káždý rez C v síti S plátí ||/1| < ||C||. Jestliže po zástávení algoritmu s tokem f nálezneme v síti S řez o stejne velikosti ||C|| = ||f ||, je jásne, že jsme nášli máximální mozný tok v síti S. (Pozor, zástávení álgoritmu jsme zátím nezdůvodnili.) c
Tákze dokázme, ze po zástáven í álgoritmu nástáne rovnost ||f || = ||C||, kde C je výpsáný řez mezi U á zbytkem gráfu G. Vezmeme tok f v S bez nenásýcene cestý ze z do s. Pák mnoziná U z álgoritmu neobsáhuje s. Schemátický výpádá situáce tákto:
f (e) = w(e)
U
f (e) = 0 c
Jelikoz z U zádne nenásýcene cestý dále nevedou, má kázdá hráná e <— U (odch. z U) plný tok f (e) = w(e) á kázdá hráná e — U (prich. do U) tok f (e) = 0, tákze
E f (e) - E f (e) = E f (e) = E w(e) = ||C|| .
e—U
eeC
To je přesne, co jsme chteli dokázát o výslednem toku. Zbývá náhlednout, ze ||C|| = Ee^u f (e) - Ee-u f (e) = ||f ||, ádukázjehotov. □
Petr Hliněný,  FI MU Brn.
: MA010: Toký v sítích
Z dúkazu Algoritmu 6.6 odvodíme nekolik zajímavých faktú:
Fakt: Pokud zajistíme, Ze Algoritmus 6.6 vZdy skoncí, dokaZeme i platnost Vety 6.5. c
Fakt: Pro celocíselne kapacity hran síte S Algoritmus 6.6 vzdy skončí.
DUsledek 6.7. Pokúd jsoú kapacity hran celocíselne, opt. tok take vyjde celocíselne.c
Vylepšen í algoritmu nenasycených cest
Bohuzel pro realna císla kapacit hran není skoncení Algoritmu 6.6 vubec zaruceno, dokonce se daj í naj ít extremn í prípady, ktere nepovedou k resen í ani v limite. Proto je potrebne zakladn í algoritmus (i pro potřeby teorie) ponekud vylepsit. c
Algoritmus 6.8. Edmonds-KarpUv pro tok v s íti
V Algoritmů 6.6 vZdy sytíme nejkratši nenasycenou cestú, neboli prohl. naši síl: do šířky
(viz mnoZina U).
Tato implementace zarúčeněskončípo O(\V(G)| • \E(G)|) iteracích cyklú, celkem tedy vcase O(\V(G)\• \E(G)\2).
Petr Hliněný,  FI MU Brr
MA010: Toky v sítích
Ještě lepších výsledků dosahují následující "chytré" algoritmy.
Algoritmus 6.9. DinicUv pro tok v síti (náznak)
V intencích Algoritmu 6.6 provádíme následující iterace:
• Prohledáváním sítě do šířky nalezneme všechny nenasycené cesty nejkratsí delky souběžně, ktere nám vytvorí "vrstvenou sít" (vrstvy odpovídají nenasycene vzdálenosti vrcholu od zdroje).
• Nalezene nenasycene cesty pak nasytíme novým prohledáním vrstvene síte.
Tato implementace zaručene skončí už po O(\V(G)\) iteracích cyklu, ale jednotlive iterace jsou poněkud nárožnejě! - O(\V (G)\ • |E(G)|). l
Algoritmus 6.10. MPM („Tří IndU") pro tok v síti (náznak) Postupuje se stejne jako v Algoritmu 6.9, jen nesycení v druhem bode proběhne rychlejším algoritmem v ěase O(\V(G)\2) v každe iteraci, celkem tedy v O(\V(G)\3).
Petr Hliněný,  FI MU Brr
MA010: Toky v sítích
6.3   Zobecnění dennice sítí
Pojmy sítě a toků v ní lze zobecnit v několika směrech. My si zde stručně uvedeme tři možnosti.
Sítě s kapacitami vrcholů
U síte můžeme zadat i kapacity vrcholů, neboli kapacitní víhova funkce je dana jako
Vyznam pro prípustne toky v takove síti je, ze zadnym vrcholem nemůze celkem „protect" více nez povolene mnozství substance. c
Fakt. Takovou síť „zdvojením" vrcholu snadno převedeme na beznou síť, ve ktere kapacity puvodních vrcholu budou uvedeny u novych hran spojujících zdvojene vrcholy. Viz neformalní schema:
w : E(G) U V(G)     R+.
r
3
V
Petr Hliněný,  FI MU Brr
MA010: Toky v sítích
S ítě s doln ími kapacitami
Pro hrany sítě lze zadat take jejich minimalní kapacity, tedy dolní meze příp. toku.
To je modelovano druhou (vedle f) vahovou funkcí 1 : E (G) — R+. Prípustný tok pak musí splnovat l(e) < f (e) < w(e) pro vSechny hrany e. c
V teto modifikaci ulohyjiZ prípustny tok nemusí vubec existovat. Algoritmus 6.11. Tok v s íti s doln ími kapacitami
I tuto úlohu lze řešit dosud uvedenými nástroji, pokud postupujeme ve dvou fázích: c
Nejprve nalezneme přípustnou cirkulaci v síti vznikle přidáním „zpětné" hrany sz. Toho lze dosahnout hledaním toku ve specialnísíti vyjadřující„přebytky" (ci nedostatky) dolních mezí toku v jednotlivych vrcholech.
Pote z přípustne cirkulace jako vychozího stavu uř získame maximalní tok kterymkoliv algoritmem pro toky. c
Tzv. vícěkomoditn í toky
V síti lze najednou přepravovat více typu substancí. To vede na problem tzv. vícekomoditních toku v síti. Tento problem je slozitejsí, uz není v obecnosti snadno resitelny a přesahuje ramec naseho textu, takze se jím nebudeme zabyvat.
Petr Hlinený,  FI MU Brno 14 FI: MA010: Toky v sítích
6.4   Speciální aplikace sítí Bipartitní párování
Definice: Párován i v (biparitním) grafu G je podmnozina hran M C E (G) takova, ze zadne dve hraný z M nesdílejí koncový vrchol.
Pojem (bipartitního) párování má přirozenou motivaci v mezilidských vztazích. c
Algoritmus 6.12. Nalezení bipartitního parovaní
Pro dany bipartitní graf G s vrcholy rozdělenými do množin A, B sestrojíme sít S následovne:
A B
Všechny hrany site S orientujeme od zdroje do stoku a přiřadíme jim kapacity 1. Nyní najdeme (celočíselný) maximální tok v S Algoritmem 6.6. Do parovíni vložíme ty hrany grafu G, které mají nenulovy tok. c
Petr Hliněný,  FI MU Brr
MA010: Toky v sítích
DUkaz správnosti Algoritmu 6.12: Podle Důsledku 6.7 bude maximální tok celočíselný, a proto každou hranou poteCe bud' 0 nebo 1. Tím budou výbráný hraný párování a
Vyšší grafová souvislost
Představme si, že na libovolnem grafu G definujeme zobecnenou sít tak, že kapacity vsech hran a vsech vrcholu položíme rovný 1 v obou smerech. Pak máme:
Duisledek 6.13. Necht: u,v jsou dva vrcholy grafu G a k > 0 je přirozené číslo. Pak mezi vrcholy u a v existuje v G aspoň k disjunktních cest, práve kdyň po odebrání libovolných k — 1 vrcholu mznych od u, v z G zustanou u a v ve stejne komponente souvislosti zbyleho grafu. c
Použitím tohoto tvržení pro vsechný dvojice vrcholu grafu snadno dokížeme dříve uvedenou duležitou Vetu 2.6 (Mengerovu).
podle žádaných kapacit nebudou sdílet koncove vrcholý.
□
V
Petr Hlinený,  FI MU Brr
MA010: Toky v sítích
Vyber různých reprezentantů
Definice: Nechť M;[,M2,...,Mk jsou neprazdne mnoziny. Systémem různých reprezentantů mnozin Mi, M2,..., Mk nazývame takovou posloupnost ruznych prvku
(xi,X2,..., xk), ze Xi G Mi pro i = 1, 2,..., k. c
Veta 6.14. (Hall) Necht. M1, M2,..Mk jsoů neprázdne množiny. Pro tyto množiny existuje system různych reprezentantů, práve když platí
VJ c{1, 2,...,k} : |M     Mj > |J|,
neboli pokůd sjednocení libovolne skůpiny z techto mnozin ma alespoň tolik prvků, kolik množzin je sjednoceno.
Důkaz: Oznacme x1,x2,...,xm po rade vsechny prvky ve sjednocení M1 U M2 U •••U Mk. Definujeme si bipartitní graf G na mnozine vrcholu {1,2,..., k} U {xi, x2,..., xm}U{u, v}, ve kterem jsou hrany {u, i} pro i = 1, 2,..., k, hrany {v, xj} pro j = 1, 2,..., m a hrany {i, xj} pro vsechny dvojice i, j, pro ktere x j G Mi.
Petr Hliněný,  FI MU Brr
MA010: Toky v sítích
Cesta mezi u a v ma tvar u, i, x j, v, a tudíz ukazuje na reprezentanta x j G Mj. System ruznych reprezentantu tak odpovída k disjunktním cestam mezi u a v. Necht X je nyní libovolna minimalní mnozina vrcholu v G, neobsahující samotne u a v, po jejímz odebraní z grafu nezbude zadna cesta mezi u a v. Podle Dusledku 6.13 a teto uvahy mají nase mnoziny system ruznych reprezentantu, prave kdyz kazda takova oddělující mnozina X ma aspon k prvku.
Polozme J = (1, 2,..., k} \ X. Pak kazda hrana z J (mimo u) vede do vrcholu z X n (xi,..., xm} (aby nevznikla cesta mezi u, v), a proto
|M   Mj = |X n(xi,...,xm }| = |X | —|X n(i,...,k}| = |X | — k + |J |.
Vidíme tedy, ze |X| > k pro vsechny (minimílní) volby oddelující X, prave kdyz Ujej Mj > |J| pro vsechny volby J, coz je dokazovana podmínka nasí vety. □
Poznámka: Predchoz í dukáz nám táke dává návod, ják system ruznych reprezentántu pro dáne mnoziny nálezt - stác í pouz ít Algoritmus 6.6 ná vhodne odvozenou s ít.
Petr Hliněný,  FI MU Brno_18_FI: MA010: Toky v sítích