6 Toky v sítích Nyní se podíváme ještě na jednu oblast úloh, kde našla teorie grafů bohaté uplatnění (konkrétně orientované grafy). Jde o oblast tzv. „síťových" úloh: Jedná se třeba o potrubní sítě přepravující vodu nebo plyn, o dopravní síť silnic s přepravou zboží, nebo třeba o internet přenášející data. Obvykle nás zajímá problém přenést z daného zdroje do daného cíle čili stoku co nejvíce této substance, za omezujících podmínek kapacit jednotlivých přepravních cest. 5 Stručný přehled lekce • Definice sítě (ohodnoceného orientovaného grafu) a toku v ní. • Algoritmus nenasycených cest. • Důsledky pro souvislost, párování a výběr reprezentantů. ______________________________________________________________ 6.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 6.1. Síť je čtveřice 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 kladné ohodnocení hran, zvané kapacita hran. 5 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.) Detr Hliněný, Fl MU Bn : 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 <— -y pro hranu e vycházející z -y. d Definice 6.2. Tok v síti 5 = (G, z, s,w) je funkce / : E(G) -+ R+ splňující - Ve G E (G) : 0 -u e<—v Velikost toku f je dána výrazem ||/|| = J2 f(e) ~ E /(e)- c e<—ä e—>z Značení: Tok a kapacitu hran v obrázku sítě budeme zjednodušeně zapisovat ve formátu F/C, kde f1 je hodnota toku na hraně a C je její kapacita. Petr Hliněný, Fl I MAOIO: Toky v sítích 55 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 orientované). Tok je pochopitelně nezáporný a dosahuje nejvýše dané kapacity hrany. 2/5 2/4 Ve vyobrazeném příkladě vede ze zdroje vlevo do stoku vpravo tok o celkové velikosti 5. c Poznámka: Obdobně se dá velikost toku definovat u stoku, neboť o=e (/w - m=y,(j: *«> - e f (A = y,(j: *«> - e *«>) • e(zE v(zV \e<—v e—fv / v = z,s \e<—v e—fv / (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. Detr Hliněný, Fl MU Bn : 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 dané síti. Pro jeho nalezení existují jednoduché a velmi rychlé algoritmy. Problém 6.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ím, c Petr Hliněný, Fl MU Bn : MA010: Toky v sítích 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? 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, d 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 Bn : 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á, ž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|| = ^eECM)(e). c Věta 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 ř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 ^^ 2 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. etr Hliněný, Fl MU Bri rtAOW^^k^^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 ei, e2,..., em, kde /(ej) < w(ej) pro ej ve směru z u do v a /(ej) > 0 pro ej v opačném směru, c Hodnotě w(ej) — /(ej) pro hrany ej ve směru z u do v a hodnotě /(ej) pro hrany ej v opačném směru říkáme rezerva kapacity hran ej. Nenasycená cesta je tudíž cesta s kladnými rezervami kapacit všech hran. d 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/4n (zj—>—•—=> • <—•—>e------•------^vy rezerva kapacity: +1 +1 +1 -\-2 +2 Všimněte si dobře, že cesta není orientovaná, takže hrany na ní jsou v obou směrech. Petr Hliněný, Fl I MA010: Toky v sítích Algoritmus 6.6. Ford-Fulkersonův pro tok v síti. vstup síť S = (G, z, s, w); 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 ( sGU ) { 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álni tok f; výstup vypíšeme min. řez jako množinu hran vedoucích z U do V (G) — U. Detr Hliněný, Fl MU Bri ^AOW^^k^^sítích Důkaz správnosti Algoritmu 6.6: 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.) d 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) /(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 —> U (přich. do U) tok /(e) = 0, takže E /(e) - E /(e) = E /(e) = Ew(e) = ii^ii • e^U e^U e^U eeC To je přesně, co jsme chtěli dokázat o výsledném toku. Zbývá nahlédnout, že £e<-y/(«O - Ee-y/(«O = ||/||. a důkaz je hotov. D 3etr Hliněný, Fl MU Bn : MA010: Toky v sítích r Z důkazu Algoritmu 6.6 odvodíme několik zajímavých faktů: Fakt: Pokud zajistíme, že Algoritmus 6.6 vždy skončí, dokážeme i platnost Věty 6.5. c Fakt: Pro celočíselné kapacity hran sítě S Algoritmus 6.6 vždy skončí. Důsledek 6.7. Pokud jsou kapacity hran celočíselné, opt. tok také vyjde celočíselné, a Vylepšení algoritmu nenasycených cest Bohužel pro reálná čísla kapacit hran není skončení Algoritmu 6.6 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 6.8. Edmonds-Karpův pro tok v síti V Algoritmu 6.6 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)| • |i?(G)|) iteracích cyklu, celkem tedy včaseO{\V{G)\-\E{G)\2). >etr Hliněný, Fl MU Bn : MA010: Toky v sítích r Ještě lepších výsledku dosahují následující "chytré" algoritmy. Algoritmus 6.9. Dinicův 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 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)| • |i?(G)|). Algoritmus 6.10. MPM („Tří Indů") pro tok v síti (náznak) Postupuje se stejně jako v Algoritmu 6.9, 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). >etr Hliněný, Fl MU Bn : MA010: Toky v sítích 6.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, c 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: 0 5 b --------&- • G 3etr Hliněný, Fl MU Bn : 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 6.11. 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: a • 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ým kol iv algoritmem pro toky. c Tzv. vícekomoditní toky V síti lze najednou přepravovat více typů substancí. To vede na problém tzv. víceko-moditní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 0: Toky v sítích 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. Pojem (bipartitního) párování má přirozenou motivaci v mezilidských vztazích. Algoritmus 6.12. Nalezení bipartitního párování Pro daný bipartitní graf G s vrcholy rozdělenými do množin A, B sestrojíme síť 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 6.6. Do párování vložíme ty hrany grafu G, které mají nenulový tok. a etr Hliněný, Fl MU Bi__________________________________________________________,010: Toky v sítích Důkaz správnosti Algoritmu 6.12: Podle Důsledku 6.7 bude maximální tok celočíselný, a proto každou hranou poteče buď 0 nebo 1. Tím budou vybrány hrany párování a podle zadaných kapacit nebudou sdílet koncové vrcholy. D 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 vrcholů položíme rovny 1 v obou směrech. Pak máme: Důsledek 6.13. Nechť 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, pravé když po odebrání libovolných k — 1 vrcholů různých od u,v z G zůstanou u a v ve stejné komponente souvislosti zbylého grafu, c 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). __________________________________________________________ Výběr různých reprezentantů Definice: Nechť Mi,M2,... ,Mfc 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 Xi G Mi pro i = 1,2,..., k. n Věta 6.14. (Hall) Nechť Mi, M2,..., Mj. jsou neprázdné množiny. Pro tyto množiny existuje systém různých reprezentantů, pravé když platí VJc{l,2,...,fc}:|U Mj >\J\ neboli pokud sjednocení libovolné skupiny z téchto množin má alespoň tolik prvků, kolik množin je sjednoceno. Důkaz: Označme xi,x2, ■ ■ ■ ,xm po řadě všechny prvky ve sjednocení Mi U M2 U ...U Mfc. Definujeme si bipartitní graf G na množině vrcholů {1,2,..., fc} U {xi, X2,... ,xm}Lí{u,v}, ve kterém jsou hrany {w, i} pro i = 1, 2,..., k, hrany {v, Xj} pro j = 1, 2,..., m a hrany {i,Xj} pro všechny dvojice i, j, pro které Xj G Mi. ^etr Hliněný, Fl MU Bn : MA010: Toky v sítích Cesta mezi u a v má tvar u, i, Xj, v, a tudíž ukazuje na reprezentanta Xj G Mi. Systém různých reprezentantů tak odpovídá k disjunktním cestám mezi u a v. Nechť X je nyní libovolná minimální množina vrcholů v G, neobsahující samotné u a v, po jejímž odebrání z grafu nezbude žádná cesta mezi u a v. Podle Důsledku 6.13 a této úvahy mají naše množiny systém různých reprezentantů, právě když každá taková oddělující množina X má aspoň k prvků. Položme J = {1, 2,..., k} \ X. Pak každá hrana z J (mimo u) vede do vrcholů z X n {xi,..., xm} (aby nevznikla cesta mezi u, v), a proto lu jeJ Mj = \xn{Xl,...,xm}\ = \x\-\xn{í,...,k}\ = \x\-k + \J\ Vidíme tedy, že |X| > k pro všechny (minimální) volby oddělující X, právě když UjeJ Mj > \J\ pro všechny volby J, což je dokazovaná podmínka naší věty. D Poznámka: Předchozí 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 6.6 na vhodně odvozenou síť. __________________________________________________________