9 Orientované grafy, Toky v sítích Nyní se budeme zabývat typem síťových úloh, ve kterých není podstatná délka hran a spojení, nýbž jejich propustnost (jako potrubní nebo počítačové sítě). Základní úlohou v této oblasti je problém nalezení maximálního toku v síti za podmínky respektování daných kapacit hran. Stručný přehled lekce * Definice a některé základní vlastnosti orientovaných grafů, souvislost. * Sítě s kapacitami hran, hledání maximálního toku a dualita. * Důsledky duality toku; vyšší souvislost, bipartitní párování, SRR. Petr Hliněný, Fl MU Brno, 2013 1/19 Fl: IB000: Toky v sítích 9.1 Základní pojmy orientovaných grafů Požadavek explicitně vyjádřit směr hrany přirozeně vede na následující definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů. Definice 9.1. Orientovaný graf je uspoř, dvojice D = (V, E), kde E C V x V. Pojmy podgrafu a isomorfismu se přirozeně přenášejí na orientované grafy. Značení: Hrana (u,v) (zvaná také šipka) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří do) vrcholu v. Opačná hrana (v, u) je různá od (u, v). Speciálně hrana tvaru (u,u) se nazývá orientovaná smyčka, c Orientované grafy odpovídají relacím, které nemusí být symetrické. c Petr Hliněný, Fl MU Brno, 2013 2/19 Fl: IB000: Toky v sítích • Orientovaná cesta délky n > O je následujícím grafem na n + 1 vrcholech 6 ... n Definice: Počet hran začínajících ve vrcholu u orientovaného grafu D nazveme výstupním stupněm (^{u) a počet hran končících v u nazveme vstupním stupněm dp(u). Součet všech výstupních stupňů je přirozeně roven součtu všech vstupních stupňů. Petr Hliněný, Fl MU Brno, 2013 3/19 Fl: IB000: Toky v sítích Souvislost na orientovaných grafech Uvedeme si odstupňovaně tři základní pohledy: • Slabá souvislost. Jedná se o tradiční souvislost na symetrizaci grafu D (tj. po „zapomenutí" směru šipek). ®-2> •-2> • 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, 2013 8/19 Fl: IB000: Toky v sítích Velikost toku v síti Značení: Pro jednoduchost píšeme ve výrazech značku 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 9.4. Tok v síti 5 = (D, z, s, w) je funkce / : E(D) —> Hq splňující * Ve G E (D) : 0 < f (e) < w(e), (respektování kapacity) * Vti £ V(D),í; ^ z,s : Yl f(e) = S í\e)- (zachování substance) e—>u e-ť— t) C Velikost toku / je dána výrazem ||/|| = Y f(e) ~ Yl f(e)- c e<— z e—>z 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. 9.3 Nalezení maximálního toku Naším úkolem je najít co největší přípustný tok v dané síti. Pro jeho nalezení existují jednoduché a velmi rychlé algoritmy. Definice 9.5. Úloha hledání maximálního toku v síti S = (D,z,s,w). Úkolem je v síti S najít tok / ze zdroje z do stoku s podle Definice 9.4 takový, který maximalizuje velikost ||/||. c Tok velikosti 5 uvedený v ukázce v předchozí části nebyl optimální, neboť v této síti najdeme i tok velikosti 6: Jak však poznáme, že větší tok již v dané síti neexistuje? Petr Hliněný, Fl MU Brno, 2013 10/19 Fl: IB000: Toky v sítích Pojem řezu v síti Definice 9.6. Rez v síti S = (D,z,s,w) je podmnožina hran X C E (D) taková, že v podgrafu D — X (tj. po odebrání hran X z D) nezbude žádná orientovaná cesta ze z do s. c Velikostí řezu X rozumíme součet kapacit hran z X, tj. ||X|| = Yleexw(e)- Věta 9.7. Maximální velikost toku v síti je rovna minimální velikosti Yezux V uvedeném obrázku nalezneme tok velikosti 5. Vyznačený řez má také velikost 5. Petr Hliněný, Fl MU Brno, 2013 11/19 Fl: IB000: Toky v sítích Nenasycené cesty v síti Definice: Mějme síť S a v ní tok /. Nenasycená cesta P (v S vzhledem k /) * je neorientovaná cesta v D mezi určenými vrcholy (obvykle ze z do s), tj. posloupnost navazujících libovolně orientovaných hran ei, e2,..., em, * kde f(e,i) < w(ei) pro e^ ve směru ze z do s a f(ej) > 0 pro ej jinak. 3/4 1/2 1/1 2/3 2/4 rezerva kapacity: W _|_]_ _|_]_ _|_]_ _|_2 _)_2 ^-^ > 0 c * Hodnotě io(ej) — /(ej) > 0 pro hrany e^ ve směru z u do v a hodnotě /(ej) > 0 pro hrany ej v opačném směru říkáme rezerva kapacity hran. Nenasycená cesta je tudíž cesta s kladnými rezervami kapacit všech hran. Petr Hliněný, Fl MU Brno, 2013 12/19 Fl: IB000: Toky v sítích Metoda 9.8. Maximální tok vylepšováním nenasycených cest. Základní myšlenkou této jednoduché metody hledání maximálního toku v dané síti je prostě opakovaně vylepšovat tok podél nalezených nenasycených cest. 3/4 1/2 1/1 2/3 2/4 rezerva kapacity: _|_2 +2 > 0 P ^-. 4/4 2/2 0/1 1/3 3/4 Pro rekapitulaci, náš tok se „vylepší" následovně; * pro hrany e,i G E (P) ve směru ze z do s zvýšíme tok na /'(e^) = /(ej) + r, * pro hrany e, G -E(-P) ve směru ze s do z snížíme tok na f'(ej) = f(ej) —r. Výsledný tok /' pak bude opět přípustný. Petr Hliněný, Fl MU Brno, 2013 13/19 Fl: IB000: Toky v sítích ■/4 ■A ■/3 ■/4 Algoritmus 9.9. Ford-Fulkersonův pro tok v síti. • Vstup: Síť S = (D,z,s,w) podle Definice 9.3. • Tok /<- (0,0, ...0). • Dále opakujeme následující: * Prohledáváním grafu najdeme množinu U vrcholů D, do kterých se dostaneme ze z po nenasycených cestách. * Pokud s G U, nechť P značí nalezenou nenasycenou cestu v S ze z do s. - Zvětšíme tok / o minimální rezervu kapacity hran v P. • Opakujeme kroky výše, dokud nenastane s 0 U. c • Výstup: Vypíšeme maximální tok / a také minimální řez jako množinu všech hran vedoucích z U do V(D) — U. Petr Hliněný, Fl MU Brno, 2013 14/19 Fl: IB000: Toky v sítích Důkaz správnosti Algoritmu 9.9: Pro každý tok / a každý řez X v síti S platí ||/|| < ||X||. Jestliže po zastavení algoritmu s tokem / nalezneme v síti S řez o stejné velikosti ||X|| = ||/||, je jasné, že jsme našli maximální možný tok v síti S. (Pozor, zastavení algoritmu jsme zatím nezdůvodnili.) c Takže dokažme, že po zastavení algoritmu nastane rovnost ||/|| = ||X||, kde X je vypsaný řez mezi U a zbytkem grafu D. Vezměme tok / v S bez nenasycené cesty ze z do s. Pak množina U z algoritmu neobsahuje s. /(e) = w{e) © U 0 f(e) 0 Nyní má každá hrana e <— U (odch. z U) plný tok /(e) = w(e) a každá hrana e^U (přich. do U) tok f(e) = 0, takže = E /(e) " E /(e) = E /(e) = E = . e-f-t/ e-^U e^-V eeX Petr Hliněný, Fl MU Brno, 2013 15/19 Fl: IB000: Toky v sítích Důsledky Ford-Fulkersonova algoritmu Z důkazu Algoritmu 9.9 pak odvodíme několik zajímavých faktů: • Pokud Algoritmus 9.9 vždy skončí, dokážeme tím i platnost Věty 9.7. c • Pro celočíselné kapacity hran sítě S Algoritmus 9.9 vždy skončí. 3/4 1/2 1/1 2/3 2/4 rezerva kapacity: ^-^ _|_2 +2 > 0 » Pokud jsou kapacity hran sítě S celočíselné, opt. tok také vyjde celočíselně. Petr Hliněný, Fl MU Brno, 2013 16/19 Fl: IB000: Toky v sítích 9.4 Zobecněné použití sítí • Sítě s kapacitami vrcholů: U sítě můžeme zadat kapacity vrcholů, neboli kapacitní váhová funkce je dána jako w : E(D) U V (D) ->• R+. a • Sítě s dolními kapacitami: Pro hrany sítě lze zadat také jejich minimální kapacity, tedy dolní meze přípustného toku, jako váhovou funkci i : E(D) £(e) < f(e) < w(e) Petr Hliněný, Fl MU Brno, 2013 17/19 Fl: IB000: Toky v sítích Bipartitní párování Definice: Párováni'v (nyní biparitním) grafu G je podmnožina hran M c E (G) taková, že žádné dvě hrany z M nesdílejí koncový vrchol, c Metoda 9.11. 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 • Hrany sítě S orientujeme od zdroje do stoku a přiřadíme jim kapacity 1. c • Nyní najdeme (celočíselný) maximální tok v S Algoritmem 9.9. Do párování vložíme ty hrany grafu G, které mají nenulový tok. Petr Hliněný, Fl MU Brno, 2013 18/19 Fl: IB000: Toky v sítích Výběr různých reprezentantů Definice: Nechť Mi, M2,..., M& jsou neprázdné množiny. Systémem různých reprezentantů množin Mi, M2,..., M& nazýváme takovou posloupnost různých prvků (xi,X2, ■ ■ ■,Xk), že Xj £ Mj pro i = 1,2,... ,k. c Věta 9.12. (Ha11) Nechť M\, M2,..., M& _/sou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, právě když platí VJc {1,2,...,A:} : M ,MJ > IJI '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 Metodě 9.11: • Použijí se speciální vrcholy u a v odpovídající zdroji a stoku; • další vrcholy reprezentují (zleva) množiny a (vpravo) prvky naší úlohy ac • ostatní hrany mimo zdrojové a stokové (kapacity 1) vždy spojují množinu Mj se všemi jejími prvky x\. □ Petr Hliněný, Fl MU Brno, 2013 19/19 Fl: IB000: Toky v sítích