Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Drsná matematika III -- 11. přednáška Toky v sítích Jan Slovák Masarykova univerzita Fakulta informatiky 27. 11. 2006 Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Obsah přednášky 1 Literatura 2 Toky v sítích 3 Problém maximálního toku v síti 4 Další aplikace Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Plán přednášky 1 Literatura 2 Toky v sítích 3 Problém maximálního toku v síti 4 Další aplikace Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Kde je dobré číst? Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ Bill Cherowitzo, Applied Graph Therory, Lecture Notes, http://www- math.cudenver.edu/~wcherowi/courses/m4408/m4408f.html Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Plán přednášky 1 Literatura 2 Toky v sítích 3 Problém maximálního toku v síti 4 Další aplikace Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Další skupina aplikací jazyka teorie grafů se týká přesunu nějakého měřitelného materiálu v pevně zadané síti. Vrcholy v orientovaném grafu představují body, mezi kterými lze podél hran přenášet předem známá množství, která jsou zadána formou ohodnocení hran. Některé vybrané vrcholy představují zdroj sítě), jiné výstup ze sítě. Podle analogie potrubní sítě pro přenos kapaliny říkáme výstupním vrcholům stok sítě). Síť je tedy pro nás orientovaný graf s ohodnocenými hranami a vybranými vrcholy, kterým říkáme zdroje a stoky. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Je zřejmé, že se můžeme bez újmy na obecnosti omezit na orientované grafy s jedním zdrojem a jedním stokem. V obecném případě totiž vždy můžeme přidat jeden stok a jeden zdroj navíc a spojit je vhodně orientovanými hranami s všemi zadanými zdroji a stoky tak, že ohodnocení přidaných hran bude zároveň zadávat maximální kapacity jednotlivých zdrojů a stoků. Situace je naznačena na obrázku, kde černými vrcholy nalevo jsou zobrazeny všechny zadané zdroje, zatímco černé vrcholy napravo jsou všechny zadané stoky. Nalevo je jeden přidaný (virtuální) zdroj jako bílý vrchol a napravo jeden stok. Označení hran není v obrázku uvedeno. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Definition Síť je orientovaný graf G = (V , E) s vybraným jedním vrcholem z nazvaným zdroj a jiným vybraným vrcholem s nazvaným stok, spolu s nezáporným ohodnocením hran w : E R. Tokem v síti S = (V , E, z, s, w) rozumíme ohodnocení hran f : E R takové, že součet hodnot u vstupních hran u každého vrcholu v, kromě zdroje a stoku, je stejný jako součet u výstupních hran z téhož vrcholu, tj. eIN(v) f (e) = eOUT(v) f (e). Velikost toku f je dána celkovou balancí hodnot u zdroje . Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Definition Síť je orientovaný graf G = (V , E) s vybraným jedním vrcholem z nazvaným zdroj a jiným vybraným vrcholem s nazvaným stok, spolu s nezáporným ohodnocením hran w : E R. Tokem v síti S = (V , E, z, s, w) rozumíme ohodnocení hran f : E R takové, že součet hodnot u vstupních hran u každého vrcholu v, kromě zdroje a stoku, je stejný jako součet u výstupních hran z téhož vrcholu, tj. eIN(v) f (e) = eOUT(v) f (e). Velikost toku f je dána celkovou balancí hodnot u zdroje . Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst jako hodnotu |f | = eIN(s) f (e) - eOUT(v) f (e). Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Na obrázku máme nakreslenu jednoduchou síť se zvýrazněným bílým zdrojem a černým stokem. Součtem maximálních kapacit hran vstupujících do stoku vidíme, že maximální možný tok v této síti je 5. 4 0011 0011 0 0 1 1 0 0 1 1 0011 0011 00110011 0011 2 3 2 5 3 3 2 2 1 3 2 1 2 0 0 1 1 Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Plán přednášky 1 Literatura 2 Toky v sítích 3 Problém maximálního toku v síti 4 Další aplikace Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Naší úlohou bude pro zadanou síť na grafu G určit maximální možný tok. Definition Řezem v síti S = (V , E, z, s, w) rozumíme takovou množinu hran C E, že po jejím odebrání nebude v grafu G = (V , E \ C) žádná cesta z z do s. Číslo |C| = eC w(e) nazýváme velikost řezu C. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Evidentně platí, že nikdy nemůžeme najít větší tok, než je hodnota kteréhokoliv z řezů. N a dalším obrázku máme zobrazen tok sítí s hodnotou 5 a čárkovanými lomenými čarami jsou naznačeny řezy o hodnotách 12, 8 a 5. 2/3 0011 0011 0011 0011 0011 0011 0 0 1 1 0 0 1 1 0011 2/2 1/3 1/2 0/2 1/2 1/1 0/2 1/3 2/2 2/4 1/3 2/5 1/1 0 0 1 1 Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Sestavíme funkční algoritmus, který pomocí postupných konstrukcí vhodných cest najde řez s minimální možnou hodnotou a zároveň najde tok, který tuto hodnotu realizuje. Tím dokážeme následující větu: Theorem Maximální velikost toku v dané síti S = (V , E, z, s, w) je rovna minimální velikosti řezu v této síti. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Myšlenka algoritmu ­ prohledáváme cesty mezi uzly grafu a snažíme se je ,,nasytit co největším tokem. Zavedeme si za títo účelem terminologii. O neorientované cestě v síti S = (V , E, z, s, w) z vrcholu v do vrcholu w řekneme, že je nenasycená, jestliže pro všechny hrany této cesty orientované ve směru z v do w platí f (e) < w(e) a f (e) > 0 pro hrany orientované opačně. Za rezervu kapacity hrany e pak označujeme číslo w(e) - f (e) pro případ hrany orientované ve směru z v do w a číslo f (e) při orientaci opačné. Pro zvolenou cestu bereme za rezervu kapacity minimální rezervu kapacity z jejích hran. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Fordův-Fullkersonův algoritmus Vstupem je síť S = (V , E, z, s, w) a výstupem maximální možný tok f : E R. Iniciace: zadáme f (e) = 0 pro všechny hrany e E a prohledáváním do šířky z vrcholu z najdeme množinu vrcholů U V , do kterých existuje nenasycená cesta;. Hlavní cyklus: Dokud s U opakujeme zvolíme nenasycenou cestu P ze zdroje z do s a zvětšíme tok f u všech hran této cesty o její minimální rezervu obnovíme U. na výstup dáme maximální tok f a minimální řez C tvořený všemi hranami vycházejícími z U a končícími v doplňku V \ U. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Důkaz správnosti algoritmu Jak jsme viděli, velikost každého toku je nejvýše rovna hodnotě kteréhokoliv řezu. Stačí nám tedy ukázat, že v okamžiku zastavení algoritmu jsme vygenerovali řez i tok se stejnou hodnotou. Algoritmus se zastaví při prvním případu, kdy neexistuje nenasycená cesta ze zdroje z do stoku s. To znamená, že U neobsahuje s a pro všechny hrany e z U do zbytku je f (e) = w(e), jinak bychom museli koncový vrchol e přidat k U. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Důkaz správnosti algoritmu Jak jsme viděli, velikost každého toku je nejvýše rovna hodnotě kteréhokoliv řezu. Stačí nám tedy ukázat, že v okamžiku zastavení algoritmu jsme vygenerovali řez i tok se stejnou hodnotou. Algoritmus se zastaví při prvním případu, kdy neexistuje nenasycená cesta ze zdroje z do stoku s. To znamená, že U neobsahuje s a pro všechny hrany e z U do zbytku je f (e) = w(e), jinak bychom museli koncový vrchol e přidat k U. Zároveň ze stejného důvodu všechny hrany e, které začínají v komplementu V \ U a končí v U musí mít tok f (e) = 0. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Pro velikost toku celé sítě jistě platí |f | = hrany z U do V \ U f (e) - hrany z V \ U do U f (e). Tento výraz je ovšem v okamžiku zastavení roven hrany z U do V \ U f (e) = hrany z U do V \ U w(e) = |C|, což jsme chtěli dokázat. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Pro velikost toku celé sítě jistě platí |f | = hrany z U do V \ U f (e) - hrany z V \ U do U f (e). Tento výraz je ovšem v okamžiku zastavení roven hrany z U do V \ U f (e) = hrany z U do V \ U w(e) = |C|, což jsme chtěli dokázat. Zbývá ovšem ukázat, že algoritmus skutečně zastaví. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Pro velikost toku celé sítě jistě platí |f | = hrany z U do V \ U f (e) - hrany z V \ U do U f (e). Tento výraz je ovšem v okamžiku zastavení roven hrany z U do V \ U f (e) = hrany z U do V \ U w(e) = |C|, což jsme chtěli dokázat. Zbývá ovšem ukázat, že algoritmus skutečně zastaví. Všimněme si, že pro celočíslené hodnoty ohodnocení hran získáme také celočíselný tok. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace 0/3 0011 0011 0011 0011 0011 0011 0 0 1 1 0 0 1 1 0011 0/2 0/2 0/2 1/1 0/2 0/3 0/2 2/4 0/3 1/5 0/1 2/3 2/2 0011 0/3 0011 0011 0011 0011 0011 0011 0 0 1 1 0011 0 0 1 1 0/2 0/2 2/2 1/1 0/2 2/3 2/2 2/4 0/3 3/5 0/1 2/3 2/2 0011 Chod algoritmu je ilustrován na obrázku. Vlevo jsou vybaveny dvě nejkratší nenasycené cesty ze zdroje do stoku (horní má dvě hrany, spodní tři). Jsou vyznačeny červeně. Napravo je pak nasycena další cesta v pořadí a je vyznačena modře. Je nyní zjevné, že nemůže existovat další nenasycená cesta ze zdroje do stoku. Proto algoritmus v tomto okamžiku skončí. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Plán přednášky 1 Literatura 2 Toky v sítích 3 Problém maximálního toku v síti 4 Další aplikace Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Můžeme požadovat dodržení maximální kapacity průtoku přes jednotlivé vrcholy. Nebo můžeme chtít dodržet nejen maximální ale také minimální toky přes jednotlivé hrany či vrcholy. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Můžeme požadovat dodržení maximální kapacity průtoku přes jednotlivé vrcholy. Nebo můžeme chtít dodržet nejen maximální ale také minimální toky přes jednotlivé hrany či vrcholy. Přidání kapacit vrcholů je jednoduché ­ prostě vrcholy zdvojíme a dvojčata oznčující vstup do vrcholu a výstup z vrcholu spojíme právě jednou hranou s příslušnou kapacitou. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Můžeme požadovat dodržení maximální kapacity průtoku přes jednotlivé vrcholy. Nebo můžeme chtít dodržet nejen maximální ale také minimální toky přes jednotlivé hrany či vrcholy. Přidání kapacit vrcholů je jednoduché ­ prostě vrcholy zdvojíme a dvojčata oznčující vstup do vrcholu a výstup z vrcholu spojíme právě jednou hranou s příslušnou kapacitou. Omezení minimálními průtoky lze zahrnout do iniciace našeho algoritmu. Je ovšem zapotřebí otestovat, jestli takový tok vůbec existuje. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Můžeme požadovat dodržení maximální kapacity průtoku přes jednotlivé vrcholy. Nebo můžeme chtít dodržet nejen maximální ale také minimální toky přes jednotlivé hrany či vrcholy. Přidání kapacit vrcholů je jednoduché ­ prostě vrcholy zdvojíme a dvojčata oznčující vstup do vrcholu a výstup z vrcholu spojíme právě jednou hranou s příslušnou kapacitou. Omezení minimálními průtoky lze zahrnout do iniciace našeho algoritmu. Je ovšem zapotřebí otestovat, jestli takový tok vůbec existuje. V literatuře lze najít řadu dalších nuancí, nebudeme se jim zde věnovat. Literatura Toky v sítích Problém maximálního toku v síti Další aplikace Hezkým využitím toků v sítí je řešení úlohy bipartitního párování. Úlohou je v bipartitním grafu najít maximální podmnožinu hran takovou, aby žádné dvě hrany nesdílely vrchol. Jde o abstraktní variantu docela obvyklé úlohy ­ třeba spárování kluků a holek k tanci v tanečních, kdybychom měli předem známé možnosti, ze kterých vybíráme. Tento problém docela snadno převedeme na hledání maximálního toku. Přidáme si uměle navíc ke grafu zdroj, který propojíme hranami jdoucími do všech vrcholů v jedné skupině v bipartitním grafu, zatímco ze všech vrcholů ve druhé skupině vedeme hranu do přidanéhoho stoku. Všechny hrany opatříme maximální kapacitou 1 a hledáme maximální tok. Za páry pak bereme hrany s nenulovým tokem.