4   Toky v sítích
Nyní se podíváme ještě na jednu oblast úloh, kde našla teorie grafů bohaté uplatnění.Jde o oblast tzv. „síťových" úloh, kde se jedná (třeba) o potrubní sítě přepravující vodu nebo plyn, o dopravní síť silnic s přepravou zboží, nebo o datovou (počítačovou) síť.
Obvykle nás zajímá problém přenést z daného zdroje do daného cíle čili stoku co nejvíce substance, za omezujících podmínek kapacit jednotlivých přepravních cest.
Stručný přehled lekce
• Definice sítě (ohodnoceného orientovaného grafu) a toku v ní.
• Algoritmus nenasycených cest; jeho vylepšené verze.
• Důsledky pro souvislost, párovania výběr reprezentantů, apod.
Petr Hliněný,   Fl MU Brno, 2011
1/18
Fl: MA010: Toky v sítích
4.1   Definice sítě
Základní strukturou pro reprezentaci sítí je orientovaný graf. Vrcholy grafu modelují jednotlivé uzly sítě a hrany jejich spojnice.
Definice 4.1. Síť je čtveřice S — (G,z,s,w), kde
- G je orientovaný graf,
- vrcholy z e V (G), s G V (G) jsou zdroj a stok,
- w : E(G) —>• R+ je kladné ohodnocení hran, zvané kapacita hran.
Poznámka: V praxi může být zdrojů a stoků více, ale v definici stačí pouze jeden zdroj a stok, z něhož / do nějž vedou hrany do ostatních zdrojů / stoků. (Dokonce pak různé zdroje a stoky mohou mít své kapacity.)
Petr Hliněný,   Fl MU Brno, 2011
2/18
Fl: MA010: Toky v sítích
■r
Značení: Pro jednoduchost píšeme ve výrazech znak e —>• v pro hranu e přicházející do vrcholu v a e «— f pro hranu e vycházející z v. n
Definice 4.2. Tok v síti S — (G, z, s, w) je funkce / : E(G) —>• Hg" splňující
- Ve e £(G) : 0 </(e) < w(e),
- VveV(G),vŕz,s:   E /(e)= E /(e).
(respektování kapacity) (zachování substance) □
Velikost toku f je dána výrazem ||/|| — E /(e) — E /(e)'
Značení: Tok a kapacitu hran v obrázku sítě budeme zjednodušeně zapisovat ve formátu F/C, kde F je hodnota toku na hraně a C je její kapacita.
Petr Hliněný,   Fl MU Brno, 2011
3/18
Fl: MA010: Toky v sítích
Neformálně tok znamená, kolik substance je každou hranou zrovna přenášeno. Tok je pochopitelně nezáporný a dosahuje nejvýše dané kapacity hrany.
Ve vyobrazeném příkladě vede ze zdroje vlevo do stoku vpravo tok o celkové velikosti 5. □ Poznámka: Obdobně se dá velikost toku definovat u stoku, neboť
o = E (/(<o - /(<o) = E (E /(<o - E /(<o) = E (E m E m
e(žiE v(žiV  \e-í— v e—>v J        v —z,s   \e-í— v e—>v
(Sčítance uprostřed předchozího vztahu nabývají nulové hodnoty pro všechny vrcholy v kromě zas dle definice toku.) Proto velikost toku počítaná u zdroje je rovna opačné velikosti toku počítaného u stoku.
Petr Hliněný,   Fl MU Brno, 2011
4/ 18
Fl: MA010: Toky v sítích
4.2   Hledání maximálního toku
Naším úkolem je najít co největšítok v dané síti. Pro jeho nalezení existují jednoduché a velmi rychlé algoritmy.
Problém 4.3. Maximálního toku v síti
Je dána síí S — (G, z, s, w) a našim úkolem je pro ni najít co největší tok ze zdroje z do stoku s vzhledem k ohodnocení w. i
Petr Hliněný,   Fl MU Brno, 2011
5/18
Fl: MA010: Toky v sítích
Jak však poznáme, že větší tok již v dané síti neexistuje? V této konkrétní ukázce to není obtížné, vidíme totiž, že obě dvě hrany přicházející do stoku mají součet kapacit 2 + 4+6, takže více než 6 do stoku ani přitéct nemůže. □
V obecnosti lze použít obdobnou úvahu, kdy najdeme podmnožinu hran, které nelze tokem „obejít" a které v součtu kapacit dají velikost našeho toku. Existuje však taková množina hran vždy? Odpověď nám dá následující definice a věta.
Petr Hliněný,   Fl MU Brno, 2011
6/18
Fl: MA010: Toky v sítích
Definice 4.4. Řez v síti S — (G, z, s, w)
je podmnožina hran C C E (G) taková, že v podgrafu G — C (tj. po odebrání hran C z G) nezbude žádná orientovaná cesta ze z do s.
Velikostířezu C rozumíme součet kapacit hran z C, tj. ||C|| — ^2eecw(e)- D
Věta 4.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 řezu velikosti 5, naznačeného svislou čárkovanou čarou. Všimněte si dobře, že definice řezu mluví o přerušení všech orientovaných cest ze z do s, takže do řezu stačí započítat hrany jdoucí přes svislou čáru od z do s, ale ne hranu jdoucí zpět. Proto je velikost vyznačeného řezu 1 + 4 = 5.
1
Poznámka: Tato věta poskytuje tzv. dobrou charakterizaci problému maximálního toku: Když už nalezneme maximální tok, tak je pro nás vždy snadné dokázat, že lepší tok není, nalezením příslušného řezu o stejné velikosti. Přitom toto zdůvodnění řezem můžeme směle ukázat i někomu, kdo se moc nevyzná v matematice.
Petr Hliněný,   Fl MU Brno, 2011
7/18
Fl: MA010: Toky v sítích
Nenasycené cesty v síti
Definice: Mějme síť S a v ní tok /. Nenasycená cesta (v S vzhledem k /) je neorientovaná cesta v G z vrcholu u do vrcholu v (obvykle ze z do s), tj. posloupnost navazujících hran e±, e?, ■ ■ ■, em, kde /(e^) < w(ei) pro ve směru z m do f a /(e^) > 0 pro v opačném směru. □
Hodnotě w(ei) — /(e^) pro hrany    ve směru z m do f a hodnotě /(e^) pro hrany v opačném směru říkáme rezerva kapacity hran e^. Nenasycená cesta je tudíž cesta s kladnými rezervami kapacit všech hran. □
Zde vidíme příklad nenasycené cesty ze zdroje do stoku s minimální rezervou kapacity +1.
rezerva kapacity:
1/2
+1
1/1
+1
+2
2/3
2/4
+2
> o
Všimněte si dobře, že cesta není orientovaná, takže hrany na ní jsou v obou směrech.
Algoritmus 4.7. Ford—Fulkersonův pro tok v síti.
vstup  síi S — (G, z, s, vo); tokf = 0; repeat {
Prohledáváním grafu najdeme množinu U vrcholů G, do kterých se dostaneme ze z po nenasycených cestách;
if ( seU ) {
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;
výstup   vypíšeme min. řez jako množinu hran vedoucích z U do V(G) — U.
Petr Hliněný,   Fl MU Brno, 2011
9/18
Fl: MA010: Toky v sítích
Důkaz správnosti Algoritmu 4.7:
Pro každý tok / a každý řez C v síti S platí ||/|| < ||C||. Jestliže po zastavení algoritmu s tokem / nalezneme v síti S řez o stejné velikosti ||C|| — ||/||, je jasné, že jsme našli maximální možný tok v síti S. (Pozor, zastavení algoritmu jsme zatím nezdůvodnili.) □
Takže dokažme, že po zastavení algoritmu nastane rovnost ||/|| — \\C\\, kde C je vypsaný řez mezi U a zbytkem grafu G. Vezměme tok f v S bez nenasycené cesty ze z do s. Pak množina U z algoritmu neobsahuje s. Schematicky vypadá situace takto:
/(e) = w(e)
0
U
0
/(e) = 0
Jelikož z U žádné nenasycené cesty dále nevedou, má každá hrana e ^— U (odch. z U) plný tok /(e) = w(e) a každá hrana e —>• í/ (přich. do í/) tok /(e) = 0, takže
eeC
To je přesně, co jsme chtěli dokázat o výsledném toku. Zbývá nahlédnout, že ||C|
Ee<-[/ /(e) - Ee^[/ /(e) = 11/11. 3 dŮkaZ Je n0t0V-
Z
Petr Hliněný,   Fl MU Brno, 2011
10/18
Fl: MA010: Toky v sítích
Z důkazu Algoritmu 4.7 odvodíme několik zajímavých faktů:
Fakt: Pokud zajistíme, že Algoritmus 4.7 vždy skončí, dokážeme i platnost Věty 4.5. □
Fakt: Pro celočíselné kapacity hran sítě S Algoritmus 4.7 vždy skončí.
Důsledek 4.8. Pokud jsou kapacity hran celočíselné, opt. tok také vyjde celočíselně.
Vylepšení algoritmu nenasycených cest
Bohužel pro reálná čísla kapacit hran není skončení Algoritmu 4.7 vůbec zaručeno, dokonce se dají najít extrémní případy, které nepovedou k řešení ani v limitě. Proto je potřebné základní algoritmus (i pro potřeby teorie) poněkud vylepšit. □
Algoritmus 4.9. Edmonds—Karpův pro tok v síti
V Algoritmu 4.7 vždy sytíme nejkratší nenasycenou cestu, neboli prohl. naši síí do šířky (viz množina U).
Tato implementace zaručeně skončí po 0(\V(G) \ ■ \E(G)\) iteracích cyklu, celkem tedy včaseO(\V(G)\■ \E(G)\2).
Petr Hliněný,   Fl MU Brno, 2011
11/18
Fl: MA010: Toky v sítích
Ještě lepších výsledků dosahují následující "chytré" algoritmy.
Algoritmus 4.10. Dinicův pro tok v síti (náznak) V intencích Algoritmu 4.7 provádíme následující iterace:
• Prohledáváním sítě do šířky nalezneme všechny nenasycené cesty nejkratší délky souběžně, které nám vytvoří "vrstvenou síť' (vrstvy odpovídají nenasycené vzdálenosti vrcholů od zdroje).
• Nalezené nenasycené cesty pak nasytíme novým prohledáním vrstvené sítě.
Tato implementace zaručeně skončí už po 0(\V(G)\) iteracích cyklu, ale jednotlivé iterace jsou poněkud náročnější, 0(\V(G)\ ■ \E(G)\). □
Algoritmus 4.11. MPM („Tří Indů") pro tok v síti (náznak) Postupuje se stejně jako v Algoritmu 4.10, jen nesycení v druhém bodě proběhne rychlejším algoritmem v čase 0(\V(G)\2) v každé iteraci, celkem tedy v 0(\V(G)\3).
Petr Hliněný,   Fl MU Brno, 2011
12/18
Fl: MA010: Toky v sítích
4.3   Zobecnění definice 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ítě můžeme zadat i kapacity vrcholů, neboli kapacitní váhová funkce je dána jako
w : e(g)uv(g) -> R+.
Význam pro přípustné toky v takové síti je, že žádným vrcholem nemůže celkem „protéct" více než povolené množství substance.
Fakt. Takovou síť „zdvojením" vrcholů snadno převedeme na běžnou síť, ve které kapacity původních vrcholů budou uvedeny u nových hran spojujících zdvojené vrcholy. Viz neformální schéma:
5
5
Petr Hliněný,   Fl MU Brno, 2011
13/18
Fl: MA010: Toky v sítích
Sítě s dolními kapacitami
Pro hrany sítě lze zadat také jejich minimální kapacity, tedy dolní meze příp. toku.
To je modelováno druhou (vedle /) váhovou funkcí £ : e(g) —>• Rq . Přípustný tok pak musí splňovat £(e) < f(e) < w(e) pro všechny hrany e. □
V této modifikaci úlohy již přípustný tok nemusí vůbec existovat. Algoritmus 4.12. Tok v síti s dolními kapacitami
/ tuto úlohu lze řešit dosud uvedenými nástroji, pokud postupujeme ve dvou fázích: □
• Nejprve nalezneme přípustnou cirkulaci v síti vzniklé přidáním „zpětné" hrany sz. Toho lze dosáhnout hledáním toku ve speciální síti vyjadřující „ přebytky" (či nedostatky) dolních mezí toku v jednotlivých vrcholech.
• Poté z přípustné cirkulace jako výchozího stavu už získáme maximální tok kterýmkoliv algoritmem pro toky. □
Tzv. vícekomoditní toky
V síti lze najednou přepravovat více typů substancí. To vede na problém tzv. vícekomoditních toků v síti. Tento problém je složitější, už není v obecnosti snadno řešitelný a přesahuje rámec našeho textu, takže se jím nebudeme zabývat.
Petr Hliněný,   Fl MU Brno, 2011
14/18
Fl: MA010: Toky v sítích
^4.4   Speciální aplikace sítí
Bipartitní párování
Definice: Párování v (biparitním) grafu G je podmnožina hran M C E (G) taková, že žádné dvě hrany z M nesdílejí koncový vrchol. □
Algoritmus 4.13. Nalezení bipartitního párování
Pro daný bipartitní graf G s vrcholy rozdělenými do množin A, B sestrojíme sít S následovně:
A B
Všechny hrany sítě S orientujeme od zdroje do stoku a přiřadíme jim kapacity 1. Nyní najdeme (celočíselný) maximální tok v S Algoritmem 4.7. Do párování vložíme ty hrany grafu G, které mají nenulový tok. □
Důkaz správnosti Algoritmu 4.13: Podle Důsledku 4.8 bude maximální tok celočíselný, a proto každou hranou poteče bud' 0 nebo 1. Tím budou vybrány hrany párování a podle zadaných kapacit nebudou sdílet koncové vrcholy. C
Petr Hliněný,   Fl MU Brno, 2011
15/18
Fl: MA010: Toky v sítích
Vyšší grafová souvislost
Představme si, že na libovolném grafu G definujeme zobecněnou síť tak, že kapacity všech hran a všech vrcholu položíme rovny 1 v obou směrech. Pak máme:
Důsledek 4.14. 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ávě když po odebrání libovolných k — 1 vrcholů různých od u,v z G zůstanou u a v ve stejné komponentě souvislosti zbylého grafu.
Použitím tohoto tvrzení pro všechny dvojice vrcholů grafu snadno dokážeme dříve uvedenou důležitou Větu 2.6 (Mengerovu).
Petr Hliněný,   Fl MU Brno, 2011
16/18
Fl: MA010: Toky v sítích
Výběr různých reprezentantů
Definice: Nechť Mi, M2, ■ ■ ■, Mk jsou neprázdné množiny. Systémem různých reprezentantů množin Mi,M2,..., Mk nazýváme takovou posloupnost různých prvků
(x1,x2,... ,xfc), že xí e Mi pro i — 1, 2,..., k. □
Věta 4.15. (Hall) Nechť M\, M2,..., M^ jsou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, právě když platí
VJC {1,2,...,*;} : M 7m->
> \J\
'je J
neboli pokud sjednocení libovolné skupiny z těchto množin má alespoň tolik prvků, kolik množin je sjednoceno.
Důkaz lze podat konstrukcí vhodné sítě podobné té v Algoritmu 4.13: □
• Speciální vrcholy u a v odpovídají zdroji a stoku,
• další vrcholy reprezentují prvky a množiny naší úlohy, □
• ostatní hrany přicházející do vrcholu Xj znázorňují všechny z daných množin,
které obsahují prvek x
Poznámka: Tento důkaz nám také dává návod, jak systém různých reprezentantů pro dané množiny nalézt - stačí použít Algoritmus 4.7 na vhodně odvozenou síť.
Petr Hliněný,   Fl MU Brno, 2011
17/18
Fl: MA010: Toky v sítích
Segmentace obrazu
Jedním ze základních problémů počítačového vidění je segmentace obrazu na popředí a pozadí.
K jeho řešení lze (mezi mnoha jinými přístupy) zvolit i následující postup:
• Vstupem je matice obrazových bodů (pixelů), z nichž každý má přiřazeny hodnoty pravděpodobnosti bytí v popředí a bytí v pozadí. Dále jsou určeny „separační penalizace" pro dvojice sousedních pixelů. □
• Síť zkonstruhujeme přidáním univerzálního zdroje z a stoku s, přičemž hrany ze z do pixelů mají kapacitu rovnou pravděpodobnosti bytí v popředí a hrany do s obdobně pro pozadí. Hrany mezi sousedními pixelyjsou obousměrné s kapacitami rovnými zmíněným penalizacím.
• Minimálnířez v této síti poté určuje „přechody" mezi popředím a pozadím daného obrazu.
Petr Hliněný,   Fl MU Brno, 2011
18/18
Fl: MA010: Toky v sítích