Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Matematika III - 11. přednáška Toky v sítích, párování Michal Bulant Masarykova univerzita Fakulta informatiky 8. 12. 2010 Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Obsah přednášky Q Toky v sítích Q Problém maximálního toku v síti O Další aplikace • Bipartitní párování • Stromové datové struktury a prefixové kódy Q Vytvořující funkce Q Operace s vytvořujícími funkcemi a Přehled mocninných řad Toky v sítích Problém maximálního toku v síti oooo ooooooooooooo Další aplikace oooooooo Vytvořující funkce ooooooooo Operace s vytvořujícími funkcemi oooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU 9 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.f i.muni.cz/~-Qhlineny/Vyuka/GT/ Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU 9 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.f i.muni.cz/~-Qhlineny/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) Toky v sítích Problém maximálního toku v síti oooo ooooooooooooo Další aplikace oooooooo Vytvořující funkce ooooooooo Operace s vytvořujícími funkcemi oooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU 9 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.f i.muni.cz/~-Qhlineny/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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Plán přednášky Q Toky v sítích Q I I s " ' I si . I " a Bipartitní párování • Stromové datové struktury a prefixové kódy Q Vytvořující funkce a Přehled mocninných řad Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi •ooo ooooooooooooo oooooooo ooooooooo oooooooooo 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oo«o ooooooooooooo oooooooo ooooooooo oooooooooo Definice Síť (ftow network)]e orientovaný graf G = (V, E) s vybraným jedním vrcholem z nazvaným zdroj a jiným vybraným vrcholem nazvaným stok, spolu s nezáporným ohodnocením hran w : E —> R^~, nazývaným kapacita hran. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oo«o ooooooooooooo oooooooo ooooooooo oooooooooo Definice Síť (ftow 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 —> R^~, nazývaným kapacita hran. 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 (někdy nazýváno Kirchhofíův zákon), tj. eelN(v) eeOUT(v) a tok splňuje kapacitní omezení f (e) < w{e). O0.O- Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oo«o ooooooooooooo oooooooo ooooooooo oooooooooo Síť (ftow 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 —> R^~, nazývaným kapacita hran. 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 (někdy nazýváno Kirchhofíů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 eelN(v) eeOUT(v) eeOUT(z) e€/A/(z) Toky v s litích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícíi ni funkcemi ooo« ooooooooooooo oooooooo ooooooooo oooooooooo Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst jako hodnotu \f\= E f(e)- E f(e)- eelN(s) eeOUT(s) Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi ooo« ooooooooooooo oooooooo ooooooooo oooooooooo Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst jako hodnotu \f\= E f(e)- E f(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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Plán přednášky Q Problém maximálního toku v síti a Bipartitní párování • Stromové datové struktury a prefixové kódy Q Vytvořující funkce 9 Přehled mocninných řad Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO »000000000000 oooooooo ooooooooo oooooooooo Naší ú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. Toky v : ítích Problém maximálního toku v sí i Další aplikace Vytvořující funkce Operace s vytvořující mi funkcemi OOOO •oooooooooooo oooooooo ooooooooo oooooooooo Naší ú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 |C| = J>(e) eec nazýváme kapacita (velikost) řezu C. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo o«ooooooooooo oooooooo ooooooooo oooooooooo Evidentně platí, že nikdy nemůžeme najít větší tok, než je 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oo»oooooooooo oooooooo ooooooooo oooooooooo 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ě fezu v této síti. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooo«ooooooooo oooooooo ooooooooo oooooooooo 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooo«ooooooooo oooooooo ooooooooo oooooooooo 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{é) 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooo»oooooooo oooooooo ooooooooo oooooooooo 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) = O pro všechny hrany e G E a najdeme množinu vrcholů U C V, do kterých existuje nenasycená cesta ze zdroje z. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO 0000*00000000 oooooooo ooooooooo oooooooooo 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) = O 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 Ľ opakujeme Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooo»oooooooo oooooooo ooooooooo oooooooooo 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 ŕ~(e) = O 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 Ľ 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 Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO 0000*00000000 oooooooo ooooooooo oooooooooo 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 ŕ~(e) = O 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 Ľ 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 li. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooo»oooooooo oooooooo ooooooooo oooooooooo 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 ŕ~(e) = O 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 Ľ 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 li. • na výstup dáme maximální tok f a minimální řez C tvořený všemi hranami vycházejícími z Ľ a končícími v doplňku V\U. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcem oooo ooooo«ooooooo oooooooo ooooooooo oooooooooo Důkaz správnosti algoritmu 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 Ľ do zbytku je f(e) = w(e), jinak bychom museli koncový vrchol e přidat k U. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcem oooo ooooo«ooooooo oooooooo ooooooooo oooooooooo Důkaz správnosti algoritmu 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 Ľ 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooooo«oooooo oooooooo ooooooooo oooooooooo Pro velikost toku celé sítě jistě platí \f\= E f(e)- E f(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 »"(<0 = |C| hrany z U do V \ U hrany z U do V \ U což jsme chtěli dokázat. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooooo«oooooo oooooooo ooooooooo oooooooooo Pro velikost toku celé sítě jistě platí \f\= E f(e)- E f(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 »"(<0 = |C|, 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í. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooo»ooooo oooooooo ooooooooo oooooooooo 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooo»ooooo oooooooo ooooooooo oooooooooo 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ě. □ Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooo»ooooo oooooooo ooooooooo oooooooooo 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 algoritmus má složitost v nejhorším případě 0(E • \ f\), kde |f| je hodnota maximálního toku. Problém maximálního toku i oooooooo«oooo Další aplikace oooooooo Vytvořující funkce ooooooooo Príklad špatného chování F-F algoritmu Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooooooo«oooo oooooooo ooooooooo oooooooooo Příklad špatného chování F-F algoritmu 1/1000 0/1000 1/1 0/1000 1/1000 Problém maximálního toku i oooooooo«oooo Další aplikace oooooooo Vytvořující funkce ooooooooo Príklad špatného chování F-F algoritmu Problém maximálního toku i oooooooo«oooo Další aplikace oooooooo Vytvořující funkce ooooooooo Príklad špatného chování F-F algoritmu Problém maximálního toku i oooooooo«oooo Další aplikace oooooooo Vytvořující funkce ooooooooo Príklad špatného chování F-F algoritmu Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooooooo«oooo oooooooo ooooooooo oooooooooo Příklad špatného chování F-F algoritmu 2/1000 1/1000 1/1 1/1000 2/1000 Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooooooo«oooo oooooooo ooooooooo oooooooooo Problém maximálního toku i oooooooo«oooo Další aplikace oooooooo Vytvořující funkce ooooooooo Príklad špatného chování F-F algoritmu Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooooooo«oooo oooooooo ooooooooo oooooooooo Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooooooo«oooo oooooooo ooooooooo oooooooooo Příklad špatného chování F-F algoritmu 1000/1000 999/1000 1/1 999/1000 1000/1000 Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo oooooooo«oooo oooooooo ooooooooo oooooooooo Příklad špatného chování F-F algoritmu 1000/1000 1000/1000 0/1 1000/1000 1000/1000 Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcem oooo ooooooooo»ooo oooooooo ooooooooo oooooooooo 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. Toky v : sítích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícíi ni funkcemi OOOO oooooooooo«oo oooooooo ooooooooo oooooooooo 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čí. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooo»o oooooooo ooooooooo oooooooooo 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooo»o oooooooo ooooooooo oooooooooo Moderní algoritmy pro maximální tok Česky viz např. Petr Parubják, XXVI. AS R '2001 Seminar, 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/ Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOO* oooooooo ooooooooo oooooooooo Zobecnění sítí 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í). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Plán přednášky Q Problém maximálního toku v síti O Další aplikace • Bipartitní párování • Stromové datové struktury a prefixové kódy O Vytvořující funkce Q Operace s vytvořujícími funkcemi • Přehled mocninných rad Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo »0000000 ooooooooo oooooooooo 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. □ Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo o«oooooo ooooooooo oooooooooo 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo o«oooooo ooooooooo oooooooooo 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. 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ý). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo o«oooooo ooooooooo oooooooooo 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. 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oo»ooooo ooooooooo oooooooooo Maďarský 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oo»ooooo ooooooooo oooooooooo Maďarský 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oo»ooooo ooooooooo oooooooooo Maďarský 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo ooo«oooo ooooooooo oooooooooo Algoritmus pro nalezení maximálního párování O Nalezneme libovolné párování 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. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOO0OOO ooooooooo oooooooooo Datové struktury Obvykle (Kořenové pěstěné) binární stromy nesoucí informaci v uzlech. • AVL stromy (vyvážené), podobně red-black stromy Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOO0OOO ooooooooo oooooooooo Datové struktury Obvykle (Kořenové pěstěné) binární stromy nesoucí informaci v uzlech. • AVL stromy (vyvážené), podobně red-black stromy • B-stromy (2-3 stromy, B* stromy) Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcem OOOO OOOOOOOOOOOOO OOOO0OOO ooooooooo oooooooooo Datové struktury Obvykle (Kořenové pěstěné) binární stromy nesoucí informaci v uzlech. • AVL stromy (vyvážené), podobně red-black stromy • B-stromy (2-3 stromy, B* stromy) • binární halda, Fibonacciho halda Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcem OOOO OOOOOOOOOOOOO OOOO0OOO ooooooooo oooooooooo Datové struktury Obvykle (Kořenové pěstěné) binární stromy nesoucí informaci v uzlech. • AVL stromy (vyvážené), podobně red-black stromy • B-stromy (2-3 stromy, B* stromy) • binární halda, Fibonacciho halda • a mnoho dalších Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcem OOOO OOOOOOOOOOOOO OOOO0OOO ooooooooo oooooooooo Datové struktury Obvykle (Kořenové pěstěné) binární stromy nesoucí informaci v uzlech. • AVL stromy (vyvážené), podobně red-black stromy • B-stromy (2-3 stromy, B* stromy) • binární halda, Fibonacciho halda • a mnoho dalších Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcem OOOO OOOOOOOOOOOOO OOOO0OOO ooooooooo oooooooooo Datové struktury Obvykle (Kořenové pěstěné) binární stromy nesoucí informaci v uzlech. • AVL stromy (vyvážené), podobně red-black stromy • B-stromy (2-3 stromy, B* stromy) • binární halda, Fibonacciho halda • a mnoho dalších V této oblasti odkážeme na předmět Návrh algoritmů a další, my si pouze ukážeme využití binárních stromů v kódování (Huffmanův algoritmus). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo ooooo«oo ooooooooo oooooooooo Pracujeme s pěstěnými binárními stromy, kde máme navíc každou hranu obarvenou některým symbolem z dané výstupní abecedy A (často A = {0,1}). Kódovými slovy C jsou slova nad abecedou A, na která převádíme symboly vstupní abecedy. Našim úkolem je reprezentovat daný text pomocí vhodných kódových slov nad výstupní abecedou. Je snadno vidět, že je užitečné chtít, aby seznam kódových slov byl bezprefixový (v opačném případě může nastat problém s dekódováním). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo ooooo«oo ooooooooo oooooooooo Pracujeme s pěstěnými binárními stromy, kde máme navíc každou hranu obarvenou některým symbolem z dané výstupní abecedy A (často A = {0,1}). Kódovými slovy C jsou slova nad abecedou A, na která převádíme symboly vstupní abecedy. Našim úkolem je reprezentovat daný text pomocí vhodných kódových slov nad výstupní abecedou. Je snadno vidět, že je užitečné chtít, aby seznam kódových slov byl bezprefixový (v opačném případě může nastat problém s dekódováním). Příklad Text: MADAM, I'M ADAM C = {0,1,00,01,10,11,000} Pokud symboly přiřazujeme tak, jak přicházejí na řadu, dostaneme M = 0, A = 1, D = 00,, = 01, / = 10/ = 11,. = 000. Přitom ale např. není jasné dekódování řetězce 01001 - je to MADA, Ml, nebo ,DA? Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOO0O ooooooooo oooooooooo Prefixový kód C splňuje, že žádný prvek C není prefixem jiného slova z C. Ke konstrukci binárních prefixových kódů (tj. nad abecedou A = {0,1}) využijeme binárních stromů. Označíme-li hrany vycházející z každého uzlu 0, resp. 1, a označíme-li navíc listy stromu symboly vstupní abecedy, dostaneme prefixový kód nad A pro tyto symboly zřetězením označení hran na cestě z kořene do příslušného listu. Takto vytvořený kód je zřejmě prefixový. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOO0O ooooooooo oooooooooo Prefixový kód C splňuje, že žádný prvek C není prefixem jiného slova z C. Ke konstrukci binárních prefixových kódů (tj. nad abecedou A = {0,1}) využijeme binárních stromů. Označíme-li hrany vycházející z každého uzlu 0, resp. 1, a označíme-li navíc listy stromu symboly vstupní abecedy, dostaneme prefixový kód nad A pro tyto symboly zřetězením označení hran na cestě z kořene do příslušného listu. Takto vytvořený kód je zřejmě prefixový. Uděláme-li tuto konstrukci navíc tak, abychom odrazili četnost symbolů vstupní abecedy v kódovaném textu, dosáhneme tak dokonce bezztrátové komprese dat. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo 0000000« ooooooooo oooooooooo Huffmanův algoritmus Nechť M je seznam četností symbolů vstupní abecedy v textu. Algoritmus postupně zkonstruuje optimální binární strom (tzv. minimum-weight binary tree) a přiřazení symbolů listům. • Vyber dvě nejmenší četnosti w\, 1/1/2 z M. Vyrob strom se dvěma listy označenými příslušnými symboly a kořenem označeným w\ + 1/1/2 , odeber z M hodnoty w\, 1/1/2 a nahraď je hodnotou wi + 1/1/2. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO 0000000« ooooooooo oooooooooo Huffmanův algoritmus Nechť M je seznam četností symbolů vstupní abecedy v textu. Algoritmus postupně zkonstruuje optimální binární strom (tzv. minimum-weight binary tree) a přiřazení symbolů listům. • Vyber dvě nejmenší četnosti w\, 1/1/2 z M. Vyrob strom se dvěma listy označenými příslušnými symboly a kořenem označeným w\ + 1/1/2 , odeber z M hodnoty w\, 1/1/2 a nahraď je hodnotou w\ + 1/1/2. • Tento krok opakuj; pouze v případě, že vybraná hodnota z M je součtem, pak nevyráběj nový list, ale " připoj" příslušný již existující podstrom. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Plán přednášky ^% Prrthl^m mavimalníhrt trtUn \/ cíti • Bipartitní párování • Stromové datové struktury a prefixové kódy Q Vytvořující funkce Q Operace s vytvořujícími funkcemi a Přehled mocninných řad uudfezA ds Ájdpouu ju jfnujdop e jfnqojiod iíods oooooooo» eo^uru. pj!"ruoA4Ä/\ oooooooo soe>|||de JSJEQ ooooooooooooo Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo «00000000 oooooooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO «00000000 oooooooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Hledáme zjevně čísla /, jak taková, že / + j: + k = 22 a zároveň / G {0,1, 2, 3,4}, j G {0,2,4, 6, 8,10}, k G {0,5,10,15}. Uvažme součin polynomů (třeba nad reálnými čísly) (x0+xl+x2+x3+x4)(x0+x2+x4+x6+x8+x10)(x0+x5+x10+xl5) Mělo by být zřejmé, že hledaný počet řešení je díky (Cauchyovskému) způsobu násobení polynomů právě koeficient u x22 ve výsledném polynomu. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO «00000000 oooooooooo Motto: spojité a diskrétní modely se vzájemně potřebují a doplňují. Příklad Máme v peněžence 4 korunové mince, 5 dvoukorunových a 3 pětikorunové. Z automatu, který nevrací, chceme minerálku za 22 Kč. Kolika způsoby to umíme, aniž bychom ztratili přeplatek? Hledáme zjevně čísla /, jak taková, že / + j: + k = 22 a zároveň / G {0,1, 2, 3,4}, j G {0,2,4, 6, 8,10}, k G {0,5,10,15}. Uvažme součin polynomů (třeba nad reálnými čísly) (x0+xl+x2+x3+x4)(x0+x2+x4+x6+x8+x10)(x0+x5+x10+xl5) Mělo by být zřejmé, že hledaný počet řešení je díky (Cauchyovskému) způsobu násobení polynomů právě koeficient u x22 ve výsledném polynomu. Skutečně tak dostáváme čtyři možnosti 3*5 + 3*2 + 1*1, 3*5 + 2*2 + 3*1, 2 * 5 + 5 * 2 + 2 * 1 a 2 * 5 + 4 * 2 + 4 * 1. Toky v : sítích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícíi ni funkcemi OOOO ooooooooooooo oooooooo o»ooooooo oooooooooo Předchozí příklad asi vypadal spis jako složitý zápis jednoduchých "backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo o»ooooooo oooooooooo Předchozí příklad asi vypadal spis jako složitý zápis jednoduchých "backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice i +j = r splňujících / € /,_/' € J roven koeficientu u xr v polynomu (J2iel x')(J2jeJ Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo o»ooooooo oooooooooo Předchozí příklad asi vypadal spis jako složitý zápis jednoduchých "backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice i +j = r splňujících / € /,_/' € J roven koeficientu u xr v polynomu (J2iel x')(J2jeJ Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo o»ooooooo oooooooooo Předchozí příklad asi vypadal spis jako složitý zápis jednoduchých "backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice i +j = r splňujících / G /,_/' G J roven koeficientu u xr v polynomu (J2iel x')(J2jeJ Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? Hledáme přirozená čísla a\, 32, 35, a\o, 320 a 350 taková, že 3/ je násobkem / pro všechna / G {1,2,5,10,20,50} a zároveň 3i + 32 + 35 + 3io + 320 + <350 = 100. Toky v : ítích Problém maximálního toku v sí i Další aplikace Vytvořující funkce Operace s vytvořující ni funkcemi OOOO ooooooooooooo oooooooo o»ooooooo oooooooooo Předchozí příklad asi vypadal spis jako složitý zápis jednoduchých "backtrackingových úvah". Následující příklad ukazuje, že tento postup lze ale s výhodou zobecnit. Nechť /, J jsou konečné množiny nezáporných celých čísel. Potom je pro dané r G N počet řešení (/,_/') rovnice i +j = r splňujících / G /,_/' G J roven koeficientu u xr v polynomu (J2iel x')(J2jeJ Příklad Kolika způsoby můžeme pomocí mincí (1, 2, 5, 10, 20 a 50 Kč) zaplatit platbu 100 Kč? Hledáme přirozená čísla a\, 32, 35, a\o, 320 a 350 taková, že 3/ je násobkem / pro všechna / G {1,2,5,10,20,50} a zároveň a\ + 32 + 35 + 3io + 320 + 350 = 100. Podobně jako výše je vidět, že požadovaný počet lze získat jako koeficient u x100 v (l+x + x2 + ...)(l + x2+x4 + ...)(l + x5+x10 + ...) (1 +x10 +x20 + )(1 + x20 +x40 + )(1 +x50 +x100 + ) □ s - ■ Toky v sítích Problém maximálního toku ■ / síti Další aplikace Vytvořující funkce Operace s vytvořujícíi ni funkcemi OOOO ooooooooooooo oooooooo oo«oooooo oooooooooo Podobným způsobem můžeme znovu velmi snadno odvodit některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo oo«oooooo oooooooooo Podobným způsobem můžeme znovu velmi snadno odvodit některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu. '-' Věta (binomická) Pro n G N a r G R (l+x)" = olatí Na levou stranu se můžeme dívat jako na součin n polynomů, pravá je zápisem polynomu vzniklého jejich roznásobením. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo oo«oooooo oooooooooo Podobným způsobem můžeme znovu velmi snadno odvodit některé kombinatorické vztahy, které známe již z dřívějška. Využijeme přitom binomickou větu. '-' Věta (binomická) Pro n G N a r G R (l+x)" = olatí Na levou stranu se můžeme dívat jako na součin n polynomů, pravá je zápisem polynomu vzniklého jejich roznásobením. Dosazením čísel x = 1, resp. x = —1 dostáváme známé vzorce: Důsledek • ELo • ELo( il) 2r = 0. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooo»ooooo oooooooooo Podíváme se teď na obě strany v binomické větě "spojitýma očima" a s využitím vlastností derivací odvodíme další vztah mezi kombinačními čísly. Důsledek Platí Toky v : ítích Problém maximálního toku v sí i Další aplikace Vytvořující funkce Operace s vytvořující ni funkcemi OOOO ooooooooooooo oooooooo ooo»ooooo oooooooooo Podíváme se teď na obě strany v binomické větě "spojitýma očima" a s využitím vlastností derivací odvodíme další vztah mezi kombinačními čísly. Důsledek Platí Důkaz. Na obě strany binomické věty se podíváme jako na polynomiální funkce. Derivací levé strany dostaneme n(l +x)n_1, derivací pravé strany (člen po členu) pak Ylk=i ^(£)x'<_1- Dosazením x = 1 dostaneme tvrzení. □ Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo oooo«oooo oooooooooo (Formální) mocninné řady * Definice Buď dána nekonečná posloupnost a = (ao, a\, 32,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru 00 E 3ix' = 30 + a\x + 32X2 H----. /'=0 Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo oooo«oooo oooooooooo (Formální) mocninné řady * Definice Buď dána nekonečná posloupnost a = (ao, a\, 32,.. .). Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru 00 ^ a,x' = ao + aix + a2x2 H----. ;=o Poznámka O formální mocninné řadě hovoříme proto, že se zatím na tuto řadu díváme čistě formálně jako na jiný zápis dané posloupnosti a nezajímáme se o konvergenci. Na druhou stranu to ale znamená, že formální mocninná řada není funkce a nemůžeme do ní dosazovat. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo oooo«oooo oooooooooo Buď dána nekonečná posloupnost a = (ao, a\, 32,.. .)■ Její vytvořující funkcí rozumíme (formální) mocninnou řadu tvaru O formální mocninné řadě hovoříme proto, že se zatím na tuto řadu díváme čistě formálně jako na jiný zápis dané posloupnosti a nezajímáme se o konvergenci. Na druhou stranu to ale znamená, že formální mocninná řada není funkce a nemůžeme do ní dosazovat. To ovšem vzápětí napravíme, když s využitím znalostí z analýzy nekonečných řad přejdeme od formálních mocninnných řad k příslušným funkcím. 00 ;=o Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooo»ooo oooooooooo Příklad Posloupnosti samých jedniček odpovídá formální mocninná řada 1 + x + x2 + x3 + • • •. Z analýzy víme, že stejně zapsaná mocninná řada konverguje pro x e (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto "zakódování'posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooo»ooo oooooooooo Příklad Posloupnosti samých jedniček odpovídá formální mocninná řada 1 + x + x2 + x3 + • • •. Z analýzy víme, že stejně zapsaná mocninná řada konverguje pro x e (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto "zakódování'posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. Jak jsme již zmínili, tento obrat lze ale použít pouze tehdy, pokud víme, že řada alespoň v nějakém okolí 0 konverguje. Často ale "diskrétní' matematici používají následující " podvod" : • pomocí formálních mocninných řad odvodí nějaký vztah (formuli, rekurenci,...) bez toho, aby se zajímali o konvergenci □ s - ■ * Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooo»ooo oooooooooo Příklad Posloupnosti samých jedniček odpovídá formální mocninná řada 1 + x + x2 + x3 + • • •. Z analýzy víme, že stejně zapsaná mocninná řada konverguje pro x e (—1,1) a její součet je roven funkci 1/(1 — x). Stejně tak obráceně, rozvineme-li tuto funkci do Taylorovy řady v bodě 0, dostaneme zřejmě původní řadu. Takovéto "zakódování'posloupnosti čísel do funkce a zpět je klíčovým obratem v teorii vytvořujících funkcí. Jak jsme již zmínili, tento obrat lze ale použít pouze tehdy, pokud víme, že řada alespoň v nějakém okolí 0 konverguje. Často ale "diskrétní' matematici používají následující " podvod" : • pomocí formálních mocninných řad odvodí nějaký vztah (formuli, rekurenci,...) bez toho, aby se zajímali o konvergenci • jinými prostředky (často matematickou indukcí) tento vztah dokážou Toky v sítích Problém maximálního toku ■ / síti Další aplikace Vytvořující funkce Operace s vytvořujícíi ni funkcemi OOOO ooooooooooooo oooooooo oooooo«oo oooooooooo Vytvořující funkce v praxi využíváme: • k nalezení explicitní formule pro n-tý člen posloupnosti; • často vytvořující funkce vycházejí z rekurentních vztahů, občas ale díky nim odvodíme rekurentní vztahy nové; Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo oooooo«oo oooooooooo Vytvořující funkce v praxi využíváme: • k nalezení explicitní formule pro n-tý člen posloupnosti; • často vytvořující funkce vycházejí z rekurentních vztahů, občas ale díky nim odvodíme rekurentní vztahy nové; • výpočet průměrů či jiných statistických závislostí (např. průměrná složitost algoritmu); Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo oooooo«oo oooooooooo Vytvořující funkce v praxi využíváme: • k nalezení explicitní formule pro n-tý člen posloupnosti; • často vytvořující funkce vycházejí z rekurentních vztahů, občas ale díky nim odvodíme rekurentní vztahy nové; • výpočet průměrů či jiných statistických závislostí (např. průměrná složitost algoritmu); • důkaz různých identit; • často je nalezení přesného vztahu příliš obtížné, ale mnohdy stačí vztah přibližný nebo asymptotické chování. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO OOOOOOO0O oooooooooo Exponenciální vytvořující funkce Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciálníVarianty. n>0 Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO OOOOOOO0O oooooooooo Exponenciální vytvořující funkce Kromě výše zmíněných vytvořujících funkcí se v praxi rovněž často objevují jejich tzv. exponenciálníVarianty. n>0 Poznámka Jméno vychází z toho, že exponenciální funkce ex je (exponenciální) vytvořujícífunkcí pro základní posloupnost (1,1,1,1,...). Později ukážeme některé příklady (např. Cayleyho větu), kdy je použití exponenciálních vytvořujících funkcí výhodnější. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO 00000000« oooooooooo Dosazování do mocninných řad Následující větu znáte z matematické analýzy z loňského semestru: Věta Buď (ao, ai, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G R, že pro všechna n > 1 je \ an\ < K", pak řada a{x) = ^ an*" n>0 konverguje pro každé x G (—^, Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a{x). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO 00000000« oooooooooo Dosazování do mocninných řad Následující větu znáte z matematické analýzy z loňského semestru: Věta Buď (ao, ai, 32,...) posloupnost reálných čísel. Platí-li pro nějaké K G R, že pro všechna n > 1 je \ an\ < K", pak řada a{x) = ^ an*" n>0 konverguje pro každé x G (—^, Součet této řady tedy definuje funkci na uvedeném intervalu, tuto funkci označujeme rovněž a{x). Hodnotami funkce a{x) na libovolném okolí O je jednoznačně určena původní posloupnost, neboi má a{x) v O derivace všech řádů a platí a(")(0) an =-:—• n\ Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooooooo Plán přednášky ^% Prrthl^m mavimalníhrt trtUn \/ cíti • Bipartitní párování • Stromové datové struktury a prefixové kódy kb vvtvořuiici funkce Q Operace s vytvořujícími funkcemi a Přehled mocninných řad Toky v : sítích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícír ni funkcemi OOOO ooooooooooooo oooooooo ooooooooo •OOOOOOOOO Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: Toky v : sítích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícír tií funkcemi OOOO ooooooooooooo oooooooo ooooooooo •OOOOOOOOO Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + b;) posloupností člen po členu odpovídá součet a(x) + b{x) příslušných vytvořujících funkcí. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO OOOOOOOOO «000000000 Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (aj + b;) posloupností člen po členu odpovídá součet a(x) + b{x) příslušných vytvořujících funkcí. • Vynásobení (a ■ a i) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a ■ a(x) příslušné vytvořující funkce. Toky v : sítích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícír tií funkcemi OOOO ooooooooooooo oooooooo ooooooooo •OOOOOOOOO Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + b;) posloupností člen po členu odpovídá součet a(x) + b{x) příslušných vytvořujících funkcí. • Vynásobení (a ■ a,) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a ■ a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. Toky v : sítích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícír tií funkcemi OOOO ooooooooooooo oooooooo ooooooooo •OOOOOOOOO Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + b;) posloupností člen po členu odpovídá součet a(x) + b{x) příslušných vytvořujících funkcí. • Vynásobení (a ■ a,) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a ■ a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (ao,..., a^-1,0,...) a poté podělíme vytvořující funkci xk. Toky v : sítích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícír ni funkcemi OOOO ooooooooooooo oooooooo ooooooooo •OOOOOOOOO Některým jednoduchým operacím s posloupnostmi odpovídají jednoduché operace nad mocninnými řadami: • Sčítání (a; + b;) posloupností člen po členu odpovídá součet a(x) + b{x) příslušných vytvořujících funkcí. • Vynásobení (a ■ a,) všech členů posloupnosti stejným skalárem a odpovídá vynásobení a ■ a(x) příslušné vytvořující funkce. • Vynásobení vytvořující funkce a(x) monomem xk odpovídá posunutí posloupnosti doprava o k míst a její doplnění nulami. • Pro posunutí posloupnosti doleva o k míst (tj. vynechání prvních k míst posloupnosti) nejprve od a(x) odečteme polynom bk(x) odpovídají posloupnosti (ao,..., a^-1,0,...) a poté podělíme vytvořující funkci xk. 9 Substitucí polynomu f(x) s nulovým absolutním členem za x vytvoříme specifické kombinace členů původní posloupnosti. Jednoduše je vyjádříme pro f(x) = ax, což odpovídá vynásobení /c-tého členu posloupnosti skalárem ak. Dosazení f(x) = x" nám do posloupnosti mezi každé dva členy vloží Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo o«oooooooo Příklad Viděli jsme, že 1/(1 — x) je vytvořující funkcí posloupnosti ze samých jedniček. Substitucí 2x za x tak dostaneme tvrzení, že 1/(1 — 2x) je vytvořující funkcí posloupnosti (1, 2,4, 8,...). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo o«oooooooo Příklad Viděli jsme, že 1/(1 — x) je vytvořující funkcí posloupnosti ze samých jedniček. Substitucí 2x za x tak dostaneme tvrzení, že 1/(1 — 2x) je vytvořující funkcí posloupnosti (1, 2,4, 8,...). S využitím substituce —x za x dostaneme, že je-li a(x) vytvořující pro (ao, ai,...), je (a(x) + a(—x))/2 vytvořující pro a0,0,a2,0,...). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo o«oooooooo Příklad Viděli jsme, že 1/(1 — x) je vytvořující funkcí posloupnosti ze samých jedniček. Substitucí 2x za x tak dostaneme tvrzení, že 1/(1 — 2x) je vytvořující funkcí posloupnosti (1, 2,4, 8,...). S využitím substituce —x za x dostaneme, že je-li a(x) vytvořující pro (ao, ai,...), je (a(x) + a(—x))/2 vytvořující pro a0,0,a2,0,...). Příklad Určete vytvořující funkci posloupnosti (1,1,2,2,4,4,8,8, ...)• Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo o«oooooooo Příklad Viděli jsme, že 1/(1 — x) je vytvořující funkcí posloupnosti ze samých jedniček. Substitucí 2x za x tak dostaneme tvrzení, že 1/(1 — 2x) je vytvořující funkcí posloupnosti (1, 2,4, 8,...). S využitím substituce —x za x dostaneme, že je-li a(x) vytvořující pro (ao, ai,...), je (a(x) + a(—x))/2 vytvořující pro a0,0,a2,0,...). Příklad Určete vytvořující funkci posloupnosti (1,1,2,2,4,4,8,8, ...). Řešení Podle předchozího příkladu je 1/(1 — 2x) vytvořující funkcí posloupnosti (1,2,4,8,...). Substitucí x2 za x dostaneme vytvořující funkci 1/(1 — 2x2) pro (1, 0, 2, 0,4, 0,...) a celkem pak je (1 + x)/(l — 2x2) hledanou vytvořující funkcí. Toky v : sítích Problém maximálního toku v sil :i Další aplikace Vytvořující funkce Operace s vytvořujícír ni funkcemi OOOO ooooooooooooo oooooooo ooooooooo oo»ooooooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oo»ooooooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'(x) vytvořuje posloupnost (ai, 2a2,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce Jq a(ř) dř vytvořuje posloupnost (0, ao, \a\, |a2, ^33,...), pro k > 1 je člen s indexem k je \ak-\ (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a(x)). Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oo»ooooooo Dalšími důležitými operacemi, které se při práci s vytvořujícími funkcemi často objevují, jsou: • Derivování podle x: funkce a'{x) vytvořuje posloupnost (ai, 2a2,3a3,...), člen s indexem k je (k + l)a/c+i (tj. mocninnou řadu derivujeme člen po členu). • Integrování: funkce Jq a(ř) dř vytvořuje posloupnost (0, ao, \a\, |a2, ^33,...), pro k > 1 je člen s indexem k je \ak-i (zřejmě je derivací příslušné mocninné řady člen po členu původní funkce a(x)). • Násobení řad: součin a{x)b{x) je vytvořující funkcí posloupnosti (co, ci, C2,... )> kde (tj. členy v součinu až po Ck jsou stejné jako v součinu (30 + 3ix + 32x2 H-----h akxk)(b0 + bix + b^x2 H----bkxk). Posloupnost c bývá také nazývána konvolucí posloupností 3, b. i+j=k Toky v : ítích Problém maximálního toku v sí i Další aplikace Vytvořující funkce Operace s vytvořující ni funkcemi OOOO ooooooooooooo oooooooo ooooooooo ooo«oooooo Příklad Jaká je vytvořující funkce pro posloupnost druhých mocnin (12,22,32,...)? Řešení Lze očekávat, že bude snazší bude nejprve určit vytvořující funkce pro (1, 2, 3,...). Podle předchozího víme, že 1/(1 — x) vytvoří posloupnost samých jedniček a její derivace 1/(1 — x)2 pak posloupnost (1,2,3,...). Jak ale zjistit funkci odpovídající druhým mocninám? Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo ooo«oooooo Příklad Jaká je vytvořující funkce pro posloupnost druhých mocnin (12,22,32,...)? Řešení Lze očekávat, že bude snazší bude nejprve určit vytvořující funkce pro (1, 2, 3,...). Podle předchozího víme, že 1/(1 — x) vytvoří posloupnost samých jedniček a její derivace 1/(1 — x)2 pak posloupnost (1,2,3,...). Jak ale zjistit funkci odpovídající druhým mocninám? Druhou derivací dostaneme 2/(1 — x)3, k ní odpovídající posloupnost je (1 x 2,2 x 3, 3 x 4,...), jejíž člen s indexem k je (k + 2){k + 1). Snadno vidíme, že výslednou vytvořující funkcí je tedy ( ___L_ alXj"(l-x)3 (1-x)2" ■ -5 -O Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooo»ooooo Příklad Uvažme jeden speciální případ násobení vytvořujících funkcí a(x) a b(x), je-li a(x) = 1/(1 — x). Pak konvolucí příslušných posloupností je posloupnost, jejíž vytvořující funkce je dána mocninnou řadou (1 + x + x2 + x3 + • • • )(bo + bix + b2X2 + •••) = = bo + (bo + bí)x + (bo + bi + b2)x2 + ■■■ Vyjádřeno slovy, vynásobením funkce b{x) funkcí 1/(1 — x) dostaneme vytvořující funkci posloupnosti částečných součtů původní posloupnosti (bo, b\, bi, ■ ■ ■ )■ Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo ooooo«oooo Přehled mocninných řad: 1 1 -x sin x n>0 1 — x ^—' n Ev" — n!' n>0 x2n+l n>0 (2n + l)!' cosx = £(_!)»_ n>0 v 7 '=i:(0 Toky v : ítích Problém maximálního toku v sí i Další aplikace Vytvořující funkce Operace s vytvořující ni funkcemi OOOO ooooooooooooo oooooooo ooooooooo oooooo»ooo Poznámka • Poslední vzorec ' k>0 v 7 je tzv. zobecněná binomická věta, kde pro r G R je binomický koeficient definován vztahem fr\ = r(r - l)(r - 2) • • • (r -/c + 1) \k) ~ k\ Speciálně klademe (q) = 1. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo oooooo»ooo Poznámka • Poslední vzorec k>0 v 7 je tzv. zobecněná binomická věta, kde pro r e R je binomický koeficient definován vztahem _ r(r-l)(r-2)-(r-/c + l) k, ~ k\ Speciálně klademe (g) » Pro n G N z uvedeného vztahu snadno dostaneme + n- 1 n + k-l\ k n-1 -X Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo ooooooo«oo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, F\ = 1, Fn+2 = Fn+\ + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice. Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo ooooooo«oo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, F\ = 1, Fn+2 = Fn+\ + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice. Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát} -výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = 1], [2|n] apod. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi oooo ooooooooooooo oooooooo ooooooooo ooooooo«oo Fibonacciho čísla a zlatý řez Připomeňme, že Fibonacciho čísla jsou dána rekurentním předpisem Fo = 0, F\ = 1, Fn+2 = Fn+i + Fn. Již dříve jste si uváděli všemožné výskyty této posloupnosti v přírodě, v matematice nebo v teoretické informatice. Našim cílem bude (opět) najít formuli pro výpočet n-tého členu posloupnosti. Poznámka (Nejen) pro manipulace se sumami používají autoři Concrete mathematics velmi vhodné označení [logický predikát} -výraz je roven 1 v případě splnění predikátu, jinak 0. Např. [n = 1], [2|n] apod. Pro vyjádření koeficientu u x" ve vytvořující funkci F(x) se pak často používá zápis [x"]F(x). □ s Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO OOOOOOOOO OOOOOOOO0O Příklad - pokr. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Pak zřejmě F(x) — xF(x) — x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) = 1_x_ 2. Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOOOOOOOOOOO OOOOOOOO OOOOOOOOO OOOOOOOO0O Příklad - pokr. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Pak zřejmě F(x) — xF(x) — x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) = 1_*_x2. Využijeme k tomu rozklad na parciální zlomky a dostaneme x _ A B 1 — X — X2 X — X\ X — X2 ' kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO OOOOOOOOO OOOOOOOO0O Příklad - pokr. Uvažme vytvořující funkci F(x) Fibonacciho posloupnosti. Pak zřejmě F(x) — xF(x) — x2F(x) = x, a tedy Našim cílem je tedy odvodit vztah pro n-tý člen posloupnosti odpovídající vytvořující funkci F(x) = 1_*_x2. Využijeme k tomu rozklad na parciální zlomky a dostaneme x _ A B 1 — X — X2 X — X\ X — X2 ' kde xi,X2 jsou kořeny polynomu 1 — x — x2 a A, B vhodné konstanty odvozené z počátečních podmínek. Po substituci Ai = 1/xi, A2 = 1/x2 dostáváme vztah x a b 1 — x — x2 1 — Aix 1 —A2X' odkud snadno pomocí znalostí o vytvořujících funkcích Problém maximálního toku v síti ooooooooooooo Další aplikace oooooooo Vytvořující funkce ooooooooo Operace s vytvořujícími funkcemi OOOOOOOOO* Příklad - závěr S využitím počátečních podmínek dostáváme V5 Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Problém maximálního toku v síti ooooooooooooo Další aplikace oooooooo Vytvořující funkce ooooooooo Operace s vytvořujícími funkcemi OOOOOOOOO* Příklad - závěr S využitím počátečních podmínek dostáváme y/5 Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 — V5)/2 ř« —0.618, vidíme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla 1 (\ + y/Š\n V5{ 2 ) ■ Problém maximálního toku v síti ooooooooooooo Další aplikace oooooooo Vytvořující funkce ooooooooo Operace s vytvořujícími funkcemi OOOOOOOOO* Příklad - závěr S využitím počátečních podmínek dostáváme y/5 Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 — V5)/2 ř« —0.618, vidíme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla ~^{l±fi)n- Navíc je vidět, že lim „_►<*, Fn/Fn+1 = « 0.618, což je poměr známý jako zlatý řez - objevuje se již od antiky v architektuře, výtvarném umění i hudbě. Toky v sítích Problém maximálního toku v síti Další aplikace Vytvořující funkce Operace s vytvořujícími funkcemi OOOO OOOOOOOOOOOOO OOOOOOOO OOOOOOOOO OOOOOOOOO* Příklad - závěr S využitím počátečních podmínek dostáváme y/5 Jistě je zajímavé, že tento výraz plný iracionálních čísel je vždy celočíselný. Uvážíme-li navíc, že (1 — V5)/2 ř« —0.618, vidíme, že pro všechna přirozená čísla lze Fn snadno spočítat zaokrouhlením čísla ~^{l±fi)n- Navíc je vidět, že lim „_►<*, Fn/Fn+1 = « 0.618, což je poměr známý jako zlatý řez - objevuje se již od antiky v architektuře, výtvarném umění i hudbě. Analogický postup je možné použít při řešení obecných lineárních diferenčních rovnic k-tého stupně s konstatními koeficienty. Má-li charakteristická rovnice jednoduché kořeny, je situace jednodušší-viz dříve. □ g - ■