Matematika III - 12. přednáška Minimální kostra, toky v sítích, párování Michal Bulant Masarykova univerzita Fakulta informatiky 5. 12. 2012 Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párovaní oooo ooooo oooo ooooooooooooo oooo Obsah přednášky Kostra grafu Q Minimální kostra O Toky v sítích Q Problém maximálního toku v síti Q Bipartitní párování Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooooo oooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooooo oooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetril, Kapitoly z diskrétni 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/ Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO ooooooooooooo OOOO Doporui :ené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetril, Kapitoly z diskrétni 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/ • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest a Clifford Stein , Introduction to Algorithms, MIT Press, 2001. H. S. Wilf, Generatingfunctionology, Academie Press, druhé vydání, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO ooooooooooooo OOOO Doporui :ené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetril, Kapitoly z diskrétni 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/ • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest a Clifford Stein , Introduction to Algorithms, MIT Press, 2001. H. S. Wilf, Generatingfunctionology, Academie Press, druhé vydání, 1994 , (rovněž http://www.math.upenn.edu/~wilf/DownldGF.html) • R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, druhé vydání, Addison-Wesley, 1994. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooooo oooo Plán prednášky Ql Kostra grafu Q Minimální kostra Q Toky v sítích Q Problém maximálního toku v síti Q Bipartitní párování <□> 3 O^O Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování •ooo ooooo oooo ooooooooooooo oooo Algoritmus pro nalezení kostry 1 Definice Libovolný strom T = (V, E') v grafu G = (V, E), E' C E se nazývá kostra (spanning tree) grafu G (tj. faktor grafu, který neobsahuje kružnice). Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování •ooo ooooo oooo ooooooooooooo oooo Algoritmus pro nalezení kostry 1 Definice Libovolný strom T = (V, E') v grafu G = (V, E), E' C E se nazývá kostra (spanning tree) grafu G (tj. faktor grafu, který neobsahuje kružnice). Seřadíme zcela libovolně všechny hrany ei,..., em v E do pořadí a postupně budujeme množiny hran E; (/' = 0,..., m) tak, že Eq = 0 a v ŕ-tém kroku přidáme hranu e,- k E/_i (tj. E/ = E/_i U {e,-} ), jestliže tím nevznikne v grafu G; = (V, E/) kružnice, a ponecháme E; = E,-_i beze změny v případě opačném. Algoritmus skončí pokud bud' má již graf G; pro nějaké / právě n — 1 hran nebo je již / = m. Pokud zastavujeme z druhého důvodu, byl původní graf nesouvislý a kostra neexistuje. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování o»oo ooooo oooo ooooooooooooo OOOO Věta Výsledkem předchozího algoritmu je vždy les T. Jestliže algoritmus skončí s k < n — 1 hranami, má původní graf n — k komponent. Zejména je tedy T kostrou, právě když algoritmus skončí pro dosažení n — 1 hran. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování o»oo ooooo oooo ooooooooooooo OOOO Věta Výsledkem předchozího algoritmu je vždy les T. Jestliže algoritmus skončí s k < n — 1 hranami, má původní graf n — k komponent. Zejména je tedy T kostrou, právě když algoritmus skončí pro dosažení n — 1 hran. Důkaz. Tvrzení, že výsledný graf T je lesem, je zřejmé z postupu konstrukce. Je-li k = n — 1, je navíc T strom podle charakterizační věty o stromech. Je-li k < n — 1, je T lesem, s n — k stromovými komponentami, neboť každá další komponenta přispívá jedničkou k hodnotě (n — 1) — k (rozdíl počtu hran ve stromu na n vrcholech a počtu hran v grafu T). □ Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oo»o ooooo oooo ooooooooooooo oooo Poznámka (složitost algoritmu) Kružnice přidáním nové hrany vznikne tehdy a jen tehdy, jestli její koncové vrcholy leží ve stejné souvislé komponentě budovaného lesu T. Stačí nám proto průběžně udržovat znalost souvislých komponent. 00.0 Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oo»o ooooo oooo ooooooooooooo oooo Poznámka (složitost algoritmu) Kružnice přidáním nové hrany vznikne tehdy a jen tehdy, jestli její koncové vrcholy leží ve stejné souvislé komponentě budovaného lesu T. Stačí nám proto průběžně udržovat znalost souvislých komponent. V abstraktní podobě nám stačí umět pro již zadané třídy ekvivalence na dané množině (v našem případě jsou to vrcholy) slučovat dvě třídy ekvivalence do jedné a nalézat pro daný prvek, do které třídy patří. Pro sjednocení jistě potřebujeme O(k) času, kde k je počet prvků slučovaných tříd a jistě můžeme použít ohraničení počtu k celkovým počtem vrcholů n. Se třídami si můžeme pamatovat i počty jejich prvků a průběžně pro každý vrchol uchovávat informaci do které třídy patří. Sjednocení dvou tříd tedy představuje přeznačení jména u všech prvků jedné z nich. Máme tedy n — 1 operací sjednocení a m operací testování ekvivalence vrcholů, proto lze složitost ohraničit 0(n2 + m). 00.0 Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oo»o ooooo oooo ooooooooooooo oooo Poznámka (složitost algoritmu) Kružnice přidáním nové hrany vznikne tehdy a jen tehdy, jestli její koncové vrcholy leží ve stejné souvislé komponentě budovaného lesu T. Stačí nám proto průběžně udržovat znalost souvislých komponent. V abstraktní podobě nám stačí umět pro již zadané třídy ekvivalence na dané množině (v našem případě jsou to vrcholy) slučovat dvě třídy ekvivalence do jedné a nalézat pro daný prvek, do které třídy patří. Pro sjednocení jistě potřebujeme O(k) času, kde k je počet prvků slučovaných tříd a jistě můžeme použít ohraničení počtu k celkovým počtem vrcholů n. Se třídami si můžeme pamatovat i počty jejich prvků a průběžně pro každý vrchol uchovávat informaci do které třídy patří. Sjednocení dvou tříd tedy představuje přeznačení jména u všech prvků jedné z nich. Máme tedy n — 1 operací sjednocení a m operací testování ekvivalence vrcholů, proto lze složitost ohraničit 0(n2 + m). Budeme-li vždy přeznačovat menší ze slučovaných tříd, pak celkový počet operací v našem algoritmu lze ohraničit 0(n\ogn + m). Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování ooo» ooooo oooo ooooooooooooo oooo Algoritmus pro nalezení kostry 2 Jiný postup: Budeme v grafu G = (V, E) s n vrcholy a m hranami postupně budovat strom T. Začneme v libovolně zvoleném vrcholu v a prázdnou množinou hran, tj. 7~o = ({i/},0). V /-tém kroku hledáme mezi hranami, které dosud nejsou v 7/_i. mají v 7~/_i jeden koncový vrchol, ale druhý koncový vrchol do 7~/_i nepatří. Některou takovou hranu přidáme i s druhým koncovým vrcholem a získáme tak T,. Algoritmus skončí, až taková hrana neexistuje. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování ooo» ooooo oooo ooooooooooooo oooo Algoritmus pro nalezení kostry 2 Jiný postup: Budeme v grafu G = (V, E) s n vrcholy a m hranami postupně budovat strom T. Začneme v libovolně zvoleném vrcholu v a prázdnou množinou hran, tj. 7~o = ({i/},0). V /-tém kroku hledáme mezi hranami, které dosud nejsou v 7/_i. mají v 7~/_i jeden koncový vrchol, ale druhý koncový vrchol do 7~/_i nepatří. Některou takovou hranu přidáme i s druhým koncovým vrcholem a získáme tak T,. Algoritmus skončí, až taková hrana neexistuje. Evidentně je výsledný graf T (v případě, že má n vrcholů) souvislý a podle počtu vrcholů a hran je to strom. Vrcholy T splývají s vrcholy souvislé komponenty G. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování ooo» ooooo oooo ooooooooooooo oooo Algoritmus pro nalezení kostry 2 Jiný postup: Budeme v grafu G = (V, E) s n vrcholy a m hranami postupně budovat strom T. Začneme v libovolně zvoleném vrcholu v a prázdnou množinou hran, tj. 7~o = ({i/},0). V /-tém kroku hledáme mezi hranami, které dosud nejsou v 7/_i. mají v 7~/_i jeden koncový vrchol, ale druhý koncový vrchol do 7~/_i nepatří. Některou takovou hranu přidáme i s druhým koncovým vrcholem a získáme tak T,. Algoritmus skončí, až taková hrana neexistuje. Evidentně je výsledný graf T (v případě, že má n vrcholů) souvislý a podle počtu vrcholů a hran je to strom. Vrcholy T splývají s vrcholy souvislé komponenty G. Algoritmus v čase 0(n + m) nalezne kostru souvislé komponenty zvoleného počátečního vrcholu v. Minimální kostra / v sítích Problém maximálního toku v síti Bipartitní párování I OOOO OOOOO OOOO OOOOOOOOOOOOO OOOO Plán přednášky Q Kostra grafu Q Minimální kostra Q Toky v sítích Q Problém maximálního toku v síti Q Bipartitní párování Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo •oooo oooo ooooooooooooo oooo Kromě nalezení kostry je často účelné znát nejlepší možnou kostru vzhledem k nějakému ohodnocení hran. Protože je to obecnou vlastností stromů, každá kostra grafu G má stejný počet hran. V grafech s ohodnocenými hranami, budeme hledat kostry s minimálním součtem ohodnocení použitých hran. Definice Nechť G = (V, E,w) je souvislý graf s ohodnocenými hranami s nezápornými vahami w(e) pro všechny hrany. Jeho minimální kostra (minimum spanning tree) T je taková kostra grafu G, která má mezi všemi jeho kostrami minimální součet ohodnocení všech hran. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo •OOOO OOOO OOOOOOOOOOOOO OOOO Kromě nalezení kostry je často účelné znát nejlepší možnou kostru vzhledem k nějakému ohodnocení hran. Protože je to obecnou vlastností stromů, každá kostra grafu G má stejný počet hran. V grafech s ohodnocenými hranami, budeme hledat kostry s minimálním součtem ohodnocení použitých hran. Definice Nechť G = (V, E,w) je souvislý graf s ohodnocenými hranami s nezápornými vahami w(e) pro všechny hrany. Jeho minimální kostra (minimum spanning tree) T je taková kostra grafu G, která má mezi všemi jeho kostrami minimální součet ohodnocení všech hran. O praktičnosti takové úlohy můžete přemýšlet třeba v souvislosti s rozvodnými sítěmi elektřiny, plynu, vody apod (viz např. problém elektrifikace části jižní Moravy, který vyřešil Otakar Borůvka v roce 1926 pomocí algoritmu - v dnešní terminologii - minimální kostry, přestože obor algoritmické teorie grafů čekal ještě cca 10 let na svůj oficiální vznik). 4 □ ► 4 S ► 4 1 -00.0 Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo o»ooo oooo ooooooooooooo oooo Kruskalův algoritmus Předpokládejme, že jsou všechna ohodnocení w(e) hran v grafu G nezáporná. Následujícímu postupu se říká Kruskalův algoritmus: • Setřídíme všech m hran v E tak, aby w/(ei) < w(e2) < ■■■ < w(em). • v tomto pořadí aplikujeme na hrany postup z Algoritmu 1 pro kostru. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo o»ooo oooo ooooooooooooo oooo Kruskalův algoritmus Předpokládejme, že jsou všechna ohodnocení w(e) hran v grafu G nezáporná. Následujícímu postupu se říká Kruskalův algoritmus: • Setřídíme všech m hran v E tak, aby w/(ei) < w(e2) < ■■■ < w(em). • v tomto pořadí aplikujeme na hrany postup z Algoritmu 1 pro kostru. Jde o typický příklad takzvaného „hladového (greedy) přístupu", kdy se k maximalizaci zisku (nebo minimalizaci nákladů) snažíme dostat výběrem momentálně nejvýhodnějšího kroku. Často tento přístup zklame, protože nizké náklady na začátku procesu mohou zavinit vysoké na jeho konci. V tomto případě (naštěstí) hladový přístup funguje, nemusíme tedy prohledávat a porovnávat až nn~2 koster na daném grafu. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO oo»oo OOOO OOOOOOOOOOOOO OOOO Věta Kruskalův algoritmus správně řeší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0(m log m), kde m je počet hran v G. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo oo»oo OOOO ooooooooooooo OOOO Věta Kruskalův algoritmus správně řeší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0(m log m), kde m je počet hran v G. Důkaz. Buď T výsledná kostra z algoritmu, To taková minimální kostra na G, která se s T shoduje na co nejvíce (seřazených) hranách. Sporem dokážeme, že Tq = T. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo oo»oo OOOO OOOOOOOOOOOOO OOOO Věta Kruskalův algoritmus správně feší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0(m log m), kde m je počet hran v G. Důkaz. Buď T výsledná kostra z algoritmu, To taková minimální kostra na G, která se s T shoduje na co nejvíce (seřazených) hranách. Sporem dokážeme, že To = T. Předpokládejme Tq ^ T a buď j nejmenší index, takový, že se T a Tq liší v hraně ej (zřejmě ej G T \ Tq). Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo oo»oo OOOO ooooooooooooo OOOO Věta Kruskalův algoritmus správně řeší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0(m log m), kde m je počet hran v G. Důkaz. Buď T výsledná kostra z algoritmu, 7~o taková minimální kostra na G, která se s T shoduje na co nejvíce (seřazených) hranách. Sporem dokážeme, že 7~o = T. Předpokládejme 7"o ^ T a buď j nejmenší index, takový, že se 7" a 7"o liší v hraně ej (zřejmě ej G T \ Tq). Pak 7"o U {e,-} obsahuje právě jednu kružnici C. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo oo»oo OOOO OOOOOOOOOOOOO OOOO Věta Kruskalův algoritmus správně feší problém minimální kostry pro každý souvislý graf G s nezáporným ohodnocením hran. Algoritmus pracuje v čase 0(m log m), kde m je počet hran v G. Důkaz. Buď T výsledná kostra z algoritmu, To taková minimální kostra na G, která se s T shoduje na co nejvíce (seřazených) hranách. Sporem dokážeme, že To = T. Předpokládejme T) 7^ T a buď j nejmenší index, takový, že se T a T) liší v hraně ej (zřejmě ej G T \ To). Pak To U {e,-} obsahuje právě jednu kružnici C. Na této kružnici tedy existuje hrana ek{k > j), která není v T. Pak ale w(e^) > w(ej) a kostra s hranami To \ {e^} U {e,-} není horší než To a protože se od T liší „později", měli jsme ji na začátku vybrat místo Tq. Spor. □ Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO ooo«o oooo ooooooooooooo OOOO I druhý z našich algoritmů pro kostru grafu v předchozím odstavci vede na minimální kostru, když v každém okamžiku volíme ze všech možných hran ef- = {v,, 1/7+1}, v; G V,, vl+\ G V \ {v,} tu, která má minimální ohodnocení. <□> <|l -a O^O Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooo«o OOOO ooooooooooooo OOOO I druhý z našich algoritmu pro kostru grafu v předchozím odstavci vede na minimálni kostru, když v každém okamžiku volíme ze všech možných hran e, = {v,, v-, G V/, G V \ {v,} tu, která má minimální ohodnocení. Výsledný postup je Primův algoritmus z roku 1957. Byl ale popsán Jarníkem již v roce 1930. Říkáme mu tedy Jarníkův algoritmus. Jarník vycházel z algoritmu O. Borůvky z r. 1926. Věta Jarníkův algoritmus najde minimální kostru pro každý souvislý graf s libovolným ohodnocením hran. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooo«o OOOO OOOOOOOOOOOOO OOOO I druhý z našich algoritmu pro kostru grafu v předchozím odstavci vede na minimálni kostru, když v každém okamžiku volíme ze všech možných hran e, = {v,, v-, G V/, G V \ {v,} tu, která má minimální ohodnocení. Výsledný postup je Primův algoritmus z roku 1957. Byl ale popsán Jarníkem již v roce 1930. Říkáme mu tedy Jarníkův algoritmus. Jarník vycházel z algoritmu O. Borůvky z r. 1926. Věta Jarníkův algoritmus najde minimální kostru pro každý souvislý graf s libovolným ohodnocením hran. Poznámka Borůvkův algoritmus tvoří stále co nejvíce souvislých komponent zaráz. Začneme s jednoprvkovými komponentami v grafu 7~o = (\/,0) a pak postupně každou komponentu propojíme nejkratší možnou hranou s komponentou jinou. Opět takto obdržíme minimální kostru. Tento algoritmu je základem nejrychlejšího známého algoritmu, běžícího v čase 0(n + m). Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOO* OOOO OOOOOOOOOOOOO OOOO Príklad Určete pomocí uvedených algoritmu minimálni kostru grafu 8 2 16 f-1 t f ( 12 i— -1 13 i— 5 i i > 4 10 6 9 r— 17 -1 i— 3 é * é é 1 15 14 Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooooo oooo Plán přednášky Qr Kostra grafu Q Minimální kostra Ql Toky v sítích Q Problém maximálního toku v síti Q Bipartitní párování Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo •ooo ooooooooooooo OOOO Další významná 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. 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 se 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. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO 0090 OOOOOOOOOOOOO OOOO Definice Síť (flow network)]e 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 —> Mq", nazývaným kapacita hran. 00.0 Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo 0090 ooooooooooooo OOOO Definice Síť (flow network)]e 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 —> Mq", nazývaným kapacita hran. Tokem v síti S = (V, E, z, s, w) rozumíme ohodnocení hran f : E —> M 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 (někdy nazýváno Kirchhoffův zákon), tj. eelN(v) eeOUT(v) a tok splňuje kapacitní omezení f (e) < w(e). 00.0 Síť (flow network)]e 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 —> Mq", nazývaným kapacita hran. Tokem v síti S = (V, E,z, s, w) rozumíme ohodnocení hran f : E —> M 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 (někdy nazýváno Kirchhoffův zákon), tj. a tok splňuje kapacitní omezení f (e) < w(e). Velikost toku f je dána celkovou balancí hodnot u zdroje v ^ z, s £ f(e)= £ f(e) eelN(v) eeOUT(v) eeOUT(z) eelN(z) Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO ooo» ooooooooooooo OOOO Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst jako hodnotu \f\= E f(e)- E eelN(s) eeOUT(s) Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO ooo» ooooooooooooo OOOO Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst jako hodnotu \f\= E f(e)- E eelN(s) eeOUT(s) 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. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO ooooo OOOO OOOOOOOOOOOOO OOOO Plán přednášky Q Kostra grafu Q Minimální kostra Q Toky v sítích Q Problém maximálního toku v síti Q Bipartitní párování Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO •OOOOOOOOOOOO OOOO Naši úlohou bude pro zadanou síť na grafu G určit maximální možný tok. Jde vlastně o speciální případ úlohy lineárního (celočíselného) programování, kde neznámými jsou toky na hranách a omezení plynou z podmínek na tok. Ukáže se, že pro řešení této úlohy existují jednoduché a přitom rychlé algoritmy. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO •OOOOOOOOOOOO OOOO Naši úlohou bude pro zadanou síť na grafu G určit maximální možný tok. Jde vlastně o speciální případ úlohy lineárního (celočíselného) programování, kde neznámými jsou toky na hranách a omezení plynou z podmínek na tok. Ukáže se, že pro řešení této úlohy existují jednoduché a přitom rychlé algoritmy. Definice Řezem v síti S = (V, E, z, s, w) rozumíme takovou množinu hran C c E, že po jejím odebrání nebude v grafu G = (V, E \ C) žádná (orientovaná) cesta z z do s. Číslo Kl = 5>(e) eec nazýváme kapacita (velikost) řezu C. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO OOOO O0OOOOOOOOOOO OOOO Evidentně platí, že nikdy nemůžeme najít větší tok, nezje kapacita kteréhokoliv z řezů. Na 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 Poznámka Tok a kapacitu hran v síti obvykle zapisujeme v obrázku ve tvaru f/c, kde f je hodnota toku na dané hraně a c její kapacita. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO OO^OOOOOOOOOO OOOO Sestavíme 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: Věta Maximální velikost toku v dané síti S = (V, E, z, s, w) je rovna minimální kapacitě řezu v této síti. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO ooo»ooooooooo OOOO Myšlenka algoritmu - prohledáváme cesty mezi uzly grafu a snažíme seje „nasytit" co největším tokem. Zavedeme si za tímto účelem terminologii. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooo»ooooooooo oooo Myšlenka algoritmu - prohledáváme cesty mezi uzly grafu a snažíme seje „nasytit" co největším tokem. Zavedeme si za tímto úč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. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo oooo»oooooooo oooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z, s, w) a výstupem maximální možný tok f : E ->• R. • Inicializace: zadáme f (e) = 0 pro všechny hrany e G E a najdeme množinu vrcholů U C V, do kterých existuje nenasycená cesta ze zdroje z. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo oooo»oooooooo oooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z, s, w) a výstupem maximální možný tok f : E ->• R. • Inicializace: zadáme f (e) = 0 pro všechny hrany e G E a najdeme množinu vrcholů U C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G U opakujeme Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo oooo»oooooooo oooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z, s, w) a výstupem maximální možný tok f : E ->• R. • Inicializace: zadáme f (e) = 0 pro všechny hrany e G E a najdeme množinu vrcholů U C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G 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 Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo oooo»oooooooo oooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z, s, w) a výstupem maximální možný tok f : E ->• R. • Inicializace: zadáme f (e) = 0 pro všechny hrany e G E a najdeme množinu vrcholů U C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G 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 • aktualizujeme U. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo oooo»oooooooo oooo Ford-Fulkersonův algoritmus (1956) Vstupem je síť S = (V, E,z, s, w) a výstupem maximální možný tok f : E ->• R. • Inicializace: zadáme f (e) = 0 pro všechny hrany e G E a najdeme množinu vrcholů U C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G 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 • aktualizujeme 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. Kostra grafu Minimální kostra Toky v sítích oooo ooooo oooo Problém maximálního toku v síti Bipartitní párování ooooo»ooooooo oooo Jak jsme viděli, velikost každého toku je nejvýše rovna kapacitě 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í, jakmile 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. Kostra grafu Minimální kostra Toky v sítích oooo ooooo oooo Problém maximálního toku v síti Bipartitní párování ooooo»ooooooo oooo Jak jsme viděli, velikost každého toku je nejvýše rovna kapacitě 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í, jakmile 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. Pro velikost toku celé sítě jistě platí ľl= E E f hrany z U do V \ U hrany z V \ U do U Tento výraz je ovšem v okamžiku zastavení roven E f(e)= E w(e) = hrany z Ľ do V \ U hrany z Ľ do V \ U což jsme chtěli dokázat. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO OOOOOOSOOOOOO OOOO Pro velikost toku celé sítě jistě platí \f\= E f(e)- E hrany z U do V \ U hrany z V \ U do U Tento výraz je ovšem v okamžiku zastavení roven E f(e)= E »"00 = ki, hrany z U do V \ U hrany z U do V \ U což jsme chtěli dokázat. Zbývá ovšem ukázat, že algoritmus skutečně zastaví. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO OOOO OOOOOOO0OOOOO oooo Zastavení Ford-Fulkersonova algoritmu Tvrzení Pro celočíselné kapacity hran sítě uvedený algoritmus vždy skončí. V obecném případě nejen, že algoritmus skončit nemusí, příslušné toky dokonce ani nemusí k maximálnímu toku konvergovat. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO OOOO OOOOOOO0OOOOO oooo Zastavení Ford-Fulkersonova algoritmu Tvrzení Pro celočíselné kapacity hran sítě uvedený algoritmus vždy skončí. V obecném případě nejen, že algoritmus skončit nemusí, příslušné toky dokonce ani nemusí k maximálnímu toku konvergovat. Důkaz. Důkaz ukončení v celočíselném případě vyplývá z toho, že vždy sytíme cestu o celočíselné hodnotě. □ Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO OOOO OOOOOOO0OOOOO oooo Zastavení Ford-Fulkersonova algoritmu Tvrzení Pro celočíselné kapacity hran sítě uvedený algoritmus vždy skončí. V obecném případě nejen, že algoritmus skončit nemusí, příslušné toky dokonce ani nemusí k maximálnímu toku konvergovat. Důkaz. Důkaz ukončení v celočíselném případě vyplývá z toho, že vždy sytíme cestu o celočíselné hodnotě. □ Poznámka Ford-Fulkersonův 0(E-\f\), kde \ f algoritmus má složitost v nej horším případě je hodnota maximálního toku. Toky v sítích OOOO Toky v sítích OOOO Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo oooooooo»oooo oooo Příklad špatného chovaní F-F algoritmu 1000/1000 1000/1000 0/1 1000/1000 1000/1000 Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO OOOO OOOOOOOOO0OOO OOOO Edmonds-Karpův algoritmus Vylepšením základního Ford-Fulkersonova algoritmu je Edmonds-Karpův algoritmus, ve kterém zvětšujeme tok podél nejkratší nenasycené cesty - tj. síť prohledáváme do šířky. U tohoto algoritmu již je zaručeno zastavení, navíc je jeho časová složitost ohraničena 0(VE2), nezávisle na hodnotě maximálního toku. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO oooooooooo»oo OOOO Chod algoritmu je ilustrován na obrázku. Vlevo jsou vybarveny 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čí. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooo»o oooo Moderní algoritmy pro maximální tok Česky viz např. Petr Parubják, XXVI. AS R '2001 Seminár, Instruments and Control, Ostrava, April 26 - 27, 2001 (http:// www.fs.vsb.cz/akce/2001/asr2001/Proceedings/papers/55.pdf) Diničův algoritmus Zjednodušuje hledání nenasycené cesty konstrukcí tzv. úrovňového grafu, kdy zlepšující hrany uvažujeme pouze tehdy, pokud vedou mezi vrcholy různých vzdáleností od zdroje. Složitost je 0(V2E), což je u hustých grafů významné vylepšení oproti složitosti 0(VE2) algoritmu Edmondse-Karpa. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooo»o oooo Moderní algoritmy pro maximální tok Česky viz např. Petr Parubják, XXVI. AS R '2001 Seminár, Instruments and Control, Ostrava, April 26 - 27, 2001 (http:// www.fs.vsb.cz/akce/2001/asr2001/Proceedings/papers/55.pdf) Diničův algoritmus Zjednodušuje hledání nenasycené cesty konstrukcí tzv. úrovňového grafu, kdy zlepšující hrany uvažujeme pouze tehdy, pokud vedou mezi vrcholy různých vzdáleností od zdroje. Složitost je 0(V2E), což je u hustých grafů významné vylepšení oproti složitosti 0(VE2) algoritmu Edmondse-Karpa. MPM algoritmus Malhotra, Pramodh Kumar a Maheshwari přišli s algoritmem složitosti 0(V3). Konstruují stejným způsobem úrovňový graf, ale vylepšují hledání maximální toku v tomto úrovňovém grafu. Viz http://www.cose.canterbury.ac.nz/tad.takaoka/alg/ ► < 8 ► 5 -00.O Kostra grafu Minimální kostra Toky v sítích oooo ooooo oooo Problém maximálního toku v síti Bipartitní párování 000000000000» oooo V praktických aplikacích mohou být na sítě kladeny další požadavky: • maximální kapacita vrcholů - snadno se převede na základní případ zdvojením vrcholů, které spojíme hranou o dané kapacitě; • minimální kapacita hran - např. aby nedocházelo k zanášení potrubí. V tomto případě lze modifikovat inicializaci, je ale třeba otestovat existenci přípustného toku (podobně jako v úloze lineárního progamování). Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování OOOO OOOOO OOOO OOOOOOOOOOOOO oooo Plán prednášky Q Kostra grafu Q Minimální kostra Q Toky v sítích Q Problém maximálního toku v síti Q Bipartitní párování <□> 3 O^O Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO OOOOOOOOOOOOO •ooo Věta (Mengerova) Pro každé dva vrcholy v a w v grafu G = (V, E) je počet hranově různých cest z v do w roven minimálnímu počtu hran, které je třeba odstranit, aby se v a w ocitly v různých komponentách vzniklého grafu. Důkaz. Plyne snadno z věty o maximálním toku a minimálním řezu v síti, kde jsou kapacity všech hran (v obou směrech) rovny 1. □ Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooooo o»oo Bipartitní párování Hezkým využitím toků v sítí je řešení úlohy bipartitního párování. Úkolem je najít v bipartitním grafu maximální podmnožinu hran takovou, aby žádné dvě hrany nesdílely vrchol. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO ooooooooooooo o»oo / / / / di partit ni párovaní Hezkým využitím toků v sítí je řešení úlohy bipartitního párovaní. Úkolem je najít v bipartitním grafu 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 (např. aby dvojici netvořil pár příliš výškově nesourodý). Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO ooooooooooooo o»oo / / / / Diparr.it ni párovaní Hezkým využitím toků v sítí je řešení úlohy bipartitního párovaní. Úkolem je najít v bipartitním grafu 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 (např. aby dvojici netvořil pár příliš výškově nesourodý). 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ého 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 (tj. zřejmě jednotkovým) tokem. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooooo oo»o Madarský algoritmus (König, Egerváry, Kuhn) Označujme kvůli jednoduchosti popisu vrcholy jedné skupiny v bipartitním grafu jako červené, vrcholy druhé skupiny jako modré. Budeme předpokládat, že vrcholy jsou obarveny tak, že počet červených vrcholů nepřevyšuje počet modrých. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooooo oo»o Madarský algoritmus (König, Egerváry, Kuhn) Označujme kvůli jednoduchosti popisu vrcholy jedné skupiny v bipartitním grafu jako červené, vrcholy druhé skupiny jako modré. Budeme předpokládat, že vrcholy jsou obarveny tak, že počet červených vrcholů nepřevyšuje počet modrých. Definice Nechť je dán bipartitní graf G = (V, E) a párování MCE. M-alternujícícestou v G nazveme takovou cestu v G, jejíž hrany tvoří střídavě hrany z M a z E \ M. Kostra grafu Minimální kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo oooo ooooooooooooo oo»o Madarský algoritmus (König, Egerváry, Kuhn) Označujme kvůli jednoduchosti popisu vrcholy jedné skupiny v bipartitním grafu jako červené, vrcholy druhé skupiny jako modré. Budeme předpokládat, že vrcholy jsou obarveny tak, že počet červených vrcholů nepřevyšuje počet modrých. Definice Nechť je dán bipartitní graf G = (V, E) a párování MCE. M-alternujícícestou v G nazveme takovou cestu v G, jejíž hrany tvoří střídavě hrany z M a z E \ M. M-rozšiřujícícestou v G nazveme M-alternující cestu, která spojuje dosud nepřiřazený červený vrchol u s dosud nepřiřazeným modrým vrcholem v. Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti Bipartitní párování oooo ooooo OOOO ooooooooooooo 0009 Algoritmus pro nalezení maximálního párování O Nalezneme libovolné párovaní M. Označíme všechny červené vrcholy jako přípustné. O Vyberme některý dosud nepřiřazený přípustný červený vrchol v (pokud neexistuje, jsme hotovi) a nalezněme pro něj (např. prostřednictvím prohledávání do hloubky) M-alternující strom s kořenem ve v (pokud neexistuje, označme v jako nepřípustný a proces opakujme s jiným vrcholem). Pokud strom obsahuje nějakou M-rozšiřující cestu, odstraníme M-hrany v této cestě z M a ostatní hrany této cesty do M přidáme. Označme všechny červené vrcholy jako přípustné a proces opakujme.