Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku i / síti ooooooo oooooooo ooooo OOOO ooooooooooooo Matematika III - 10. přednáška Stromy a kostry Michal Bulant Masarykova univerzita Fakulta informatiky 1. 12. 2010 Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Obsah přednášky Q Rovinné grafy • Platónska tělesa a Barvení map Q Kostra grafu Q Minimálni kostra Q Toky v sítích Q Problém maximálního toku v síti Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové 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.f i. muni.cz/~hlineny/Vyuka/GT/ Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové 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.f i. muni.cz/~hlineny/Vyuka/GT/ • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-cs-facuity.Stanford.edu/~knuth/sgb.html). Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Obsah třetí písemky 3.12. v 17.00 • grafy - základní pojmy, skóre, izomorfismus grafů Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Obsah třetí písemky 3.12. v 17.00 • grafy - základní pojmy, skóre, izomorfismus grafů • sledy v grafu - počty sledů, tahů, cest, nejkratší cesty Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Obsah třetí písemky 3.12. v 17.00 • grafy - základní pojmy, skóre, izomorfismus grafů • sledy v grafu - počty sledů, tahů, cest, nejkratší cesty • eulerovské tahy a hamiltonovské kružnice, problém čínskeho pošťáka Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Obsah třetí písemky 3.12. v 17.00 • grafy - základní pojmy, skóre, izomorfismus grafů • sledy v grafu - počty sledů, tahů, cest, nejkratší cesty • eulerovské tahy a hamiltonovské kružnice, problém čínskeho pošťáka • stromy - charakterizace a vlastnosti, izomorfismus stromů, kostry (ne minimálni kostry) grafů, Huffmanův kód Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Plán přednášky Q Rovinné grafy a Platónska tělesa • Barvení map Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku / síti ooooooo oooooooo ooooo OOOO ooooooooooooo Vztah mezi počty hran, stěn a vrcholů lze odvodit pro všechny rovinné grafy. Jde o tzv. Eulerův vztah. Všimněme si, že z něho zejména vyplývá, že počet stěn v rovinném grafu nezávisí na způsobu, jaké jeho rovinné nakreslení vybereme. Věta Necht G = (V, E,S) je souvislý rovinný graf. Pak platí \V\-\E\ + \S\=2. □ s - ■ Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku / síti ooooooo oooooooo ooooo OOOO ooooooooooooo Vztah mezi počty hran, stěn a vrcholů lze odvodit pro všechny rovinné grafy. Jde o tzv. Eulerův vztah. Všimněme si, že z něho zejména vyplývá, že počet stěn v rovinném grafu nezávisí na způsobu, jaké jeho rovinné nakreslení vybereme. ' Věta * Necht G = (V, E,S) je souvislý rovinný graf. Pak platí \V\ -\E\ + \S\ = 2. Důkaz. Indukcí podle počtu hran. ^1 Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti •oooooo oooooooo ooooo OOOO ooooooooooooo Jako ilustraci kombinatorické práce s grafy odvodíme klasifikaci tzv. pravidelných mnohostěnů, tj. mnohostěnů poskládaných ze stejných pravidelných mnohoúhelníků tak, že se jich v každém vrcholu dotýká stejný počet. Již v dobách antického myslitele Platóna se vědělo, že jich je pouze pět: Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti •oooooo oooooooo ooooo OOOO ooooooooooooo Jako ilustraci kombinatorické práce s grafy odvodíme klasifikaci tzv. pravidelných mnohostěnů, tj. mnohostěnů poskládaných ze stejných pravidelných mnohoúhelníků tak, že se jich v každém vrcholu dotýká stejný počet. Již v dobách antického myslitele Platóna se vědělo, že jich je pouze pět: Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti o«ooooo oooooooo ooooo OOOO ooooooooooooo Přeložíme si požadavek pravidelnosti do vlastností příslušného grafu: chceme aby každý vrchol měl stejný stupeň d > 3 a zároveň aby na hranici každé stěny byl stejný počet k > 3 vrcholů. Označme n počet vrcholů, e počet hran a s počet stěn. Máme k dispozici jednak vztah provazující stupně vrcholů s počtem hran: dn = 2e Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti o«ooooo oooooooo ooooo OOOO ooooooooooooo Přeložíme si požadavek pravidelnosti do vlastností příslušného grafu: chceme aby každý vrchol měl stejný stupeň d > 3 a zároveň aby na hranici každé stěny byl stejný počet k > 3 vrcholů. Označme n počet vrcholů, e počet hran a s počet stěn. Máme k dispozici jednak vztah provazující stupně vrcholů s počtem hran: dn = 2e a podobně počítáme počet hran, které ohraničují jednotlivé stěny, a bereme v úvahu, že každá je hranicí dvou stěn, tj. ks. 2e Eulerův vztah pak říká 2 = n e + s 2e 2e ~ď~e + T' Úpravou odtud dostáváme pro naše známé d a k vztah 1 1 -d + ~k 1 1 2 + e- Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti oo«oooo oooooooo ooooo OOOO ooooooooooooo Protože e a n musí být přirozená čísla (tj. zejména je \ > 0) a minimum pro d i k je 3, dostáváme přímou diskusí všech možností tento výčet: d k n e s 3 3 4 6 4 3 4 8 12 6 4 3 6 12 8 3 5 20 30 12 5 3 12 30 20 Tabulka zadává všechny možnosti. Ve skutečnosti ale také všechny odpovídající pravidelné mnohostěny existují - již jsme je viděli. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooo«ooo oooooooo ooooo oooo ooooooooooooo Maximálni počet hran Věta Nechi (V, E, S) je rovinný graf s aspoň třemi vrcholy. Pak \E\ < 3\V\ -6. Rovnost pritom nastáva pro maximální rovinný graf, tj. rovinný graf, k němuž nejde při zachování rovinnosti přidat žádnou hranu. Pokud navíc uvažovaný graf neobsahuje trojúhelník (tj. K3 jako podgraf), platí dokonce \E\ < 2\V\ —4. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooo«ooo oooooooo ooooo oooo ooooooooooooo Maximálni počet hran Věta Nechi (V, E, S) je rovinný graf s aspoň třemi vrcholy. Pak \E\ < 3\V\ -6. Rovnost pritom nastáva pro maximální rovinný graf, tj. rovinný graf, k němuž nejde při zachování rovinnosti přidat žádnou hranu. Pokud navíc uvažovaný graf neobsahuje trojúhelník (tj. K3 jako podgraf), platí dokonce \E\ < 2\V\ —4. Důkaz. Maximální rovinný graf má všechny stěny ohraničené kružnicí délky 3, z čehož plyne 3|S| = 2\E\ a odtud již pomocí Eulerova vztahu dostáváme první tvrzení. Podobně v druhé části. □ Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti oooo»oo oooooooo ooooo oooo ooooooooooooo Důsledek • Ks není rovinný; Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti oooo»oo oooooooo ooooo oooo ooooooooooooo Důsledek • K5 není rovinný; • K33 není rovinný; Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku / síti oooo»oo oooooooo ooooo OOOO ooooooooooooo Důsledek • K5 není rovinný; 9 K33 není rovinný; 9 každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5; Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku / síti oooo»oo oooooooo ooooo OOOO ooooooooooooo Důsledek • K5 není rovinný; 9 K33 není rovinný; 9 každý rovinný graf obsahuje alespoň jeden vrchol stupně nejvýše 5; 9 každý rovinný graf bez trojúhelníků obsahuje alespoň jeden vrchol stupně nejvýše 3. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooo«o oooooooo ooooo oooo ooooooooooooo Problém čtyř barev Jedním z nejznámějších kombinatorických problémů je otázka: Je možné každou mapu obarvit 4 barvami? Tento problém sice na první pohled vypadá ryze geometricky, ale dá se přeformulovat do kombinatorické podoby. Definice Mapou nazýváme souvislý rovinný multigraf bez mostů. Normální mapou pak mapu, jejíž všechny vrcholy jsou stupně 3. Obarvení mapy je funkce, která každé stěně mapy přiřadí číslo (barvu). Problém čtyř barev byl rozřešen teprve po více než sto letech bádání - mnoho matematiků na prezentovaný důkaz stále pohlíží s despektem, protože je založen na prověření velkého množství případů pomocí počítače. Elementárními kombinatorickými prostředky je možné alespoň dokázat možnost obarvení normálních map pěti barvami - viz literatura. Každou normální mapu je možné obarvit pomocí čtyř barev. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Plán přednášky 9 Platónská tělesa • Barvení map Q Kostra grafu O Toky v sítích Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo •OOOOOOO ooooo oooo ooooooooooooo V praktických aplikacích často zadáva graf všechny možnosti propojení mezi objekty, příkladem může být třeba silniční nebo vodovodní nebo elektrická síť. Pokud nám stačí zajistit propojitelnost každých dvou vrcholů při minimálním počtu hran, hledáme vlastně v grafu G faktor T, který je stromem. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo •OOOOOOO ooooo oooo ooooooooooooo V praktických aplikacích často zadáva graf všechny možnosti propojení mezi objekty, příkladem může být třeba silniční nebo vodovodní nebo elektrická síť. Pokud nám stačí zajistit propojitelnost každých dvou vrcholů při minimálním počtu hran, hledáme vlastně v grafu G faktor T, který je stromem. 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). Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo •OOOOOOO ooooo oooo ooooooooooooo V praktických aplikacích často zadáva graf všechny možnosti propojení mezi objekty, příkladem může být třeba silniční nebo vodovodní nebo elektrická síť. Pokud nám stačí zajistit propojitelnost každých dvou vrcholů při minimálním počtu hran, hledáme vlastně v grafu G faktor T, který je stromem. 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). Evidentně může kostra v grafu existovat pouze pokud je graf G souvislý. Místo formálního důkazu, že platí i opak uvedeme přímo algoritmus, jak kostru grafu sestrojit. □ s - ■ * Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti OOOOOOO O0OOOOOO ooooo oooo ooooooooooooo Počet koster grafu Kn Věta (Cayleyho formule) Pro n > 2 je počet koster n{Kn) na Kn (tj. počet stromu na daných n vrcholech) roven nn~2. Poznámka Počet koster je významný pojem používaný v mnoha aplikacích. Např. v elektrotechnice, při hypotetickém předpokladu jednotkového odporu mezi každými dvěma vrcholy spojenými hranou, naměříme mezi 2 vrcholy spojenými hranou (vodičem) odpor, který je roven počtu koster obsahujících tuto hranu lomeno celkový počet koster v grafu Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku i / síti ooooooo oo«ooooo ooooo OOOO ooooooooooooo Důkaz: Není znám žádný přímočarý způsob, jak dokázat platnost této jednoduché formule, lze ji ale dokázat mnoha různými způsoby (např. pomocí skóre, kódování koster, determinantů, či počítání povykosů - viz [MN]). Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku i / síti ooooooo oo«ooooo ooooo OOOO ooooooooooooo Důkaz: Není znám žádný přímočarý způsob, jak dokázat platnost této jednoduché formule, lze ji ale dokázat mnoha různými způsoby (např. pomocí skóre, kódování koster, determinantů, či počítání povykosů - viz [MN]). Spočítáme dvěma způsoby povykosy (povykos = postup výroby kořenového stromu). Povykos je definován jako trojice (T, r, v), kde T je strom na n vrcholech, r jeho kořen a v očíslování hran, neboli bijekce v : E(T) —> {1, 2,..., n — 1} (začínáme s prázdnou množinou hran a postupně přidáváme hrany v pořadí podle v). Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku i / síti ooooooo oo«ooooo ooooo OOOO ooooooooooooo Důkaz: Není znám žádný přímočarý způsob, jak dokázat platnost této jednoduché formule, lze ji ale dokázat mnoha různými způsoby (např. pomocí skóre, kódování koster, determinantů, či počítání povykosů - viz [MN]). Spočítáme dvěma způsoby povykosy (povykos = postup výroby kořenového stromu). Povykos je definován jako trojice (7, r, v), kde T je strom na n vrcholech, r jeho kořen a v očíslování hran, neboli bijekce v : E(T) —> {1, 2,..., n — 1} (začínáme s prázdnou množinou hran a postupně přidáváme hrany v pořadí podle v). Pro každý strom T můžeme kořen r zvolit n způsoby a očíslování hran (n — 1)! způsoby, proto je počet povykosů n{n — 1)! • n{Kn). Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo OOO0OOOO ooooo OOOO ooooooooooooo Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností. Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo OOO0OOOO ooooo OOOO ooooooooooooo Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo OOO0OOOO ooooo OOOO ooooooooooooo Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; • na konci musí z každého vrcholu kromě jediného vycházet nějaká šipka, proto musí každá nová šipka vycházet z vrcholu, z něhož ještě žádná nevychází. Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo OOO0OOOO ooooo OOOO ooooooooooooo Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; • na konci musí z každého vrcholu kromě jediného vycházet nějaká šipka, proto musí každá nová šipka vycházet z vrcholu, z něhož ještě žádná nevychází. Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo OOO0OOOO ooooo OOOO ooooooooooooo Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; • na konci musí z každého vrcholu kromě jediného vycházet nějaká šipka, proto musí každá nová šipka vycházet z vrcholu, z něhož ještě žádná nevychází. V každé komponentě již vytvořeného grafu je právě jeden vrchol, z něhož nevychází šipka. Šipka číslo k + 1 musí vést do některého vrcholu a vycházet z kořene některé z ostatních komponent -n(n — k — 1) možností. Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo OOO0OOOO ooooo OOOO ooooooooooooo Důkaz - pokr.: Druhý způsob: kořenový strom budeme uvažovat jako orientovaný strom se šipkami směřujícími ke kořeni. Začneme s prázdným grafem a budeme přidávat šipky v n — 1 krocích. 1. šipka: n(n — 1) možností, další šipka: • nesmí vytvořit kružnici; • na konci musí z každého vrcholu kromě jediného vycházet nějaká šipka, proto musí každá nová šipka vycházet z vrcholu, z něhož ještě žádná nevychází. V každé komponentě již vytvořeného grafu je právě jeden vrchol, z něhož nevychází šipka. Šipka číslo k + 1 musí vést do některého vrcholu a vycházet z kořene některé z ostatních komponent -n(n — k — 1) možností. Celkem máme n-2 Y\n(n-k-l) = (n-l)\nn-1 k=Q způsobů a porovnáním s prvním výpočtem dostaneme tvrzení. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooo«ooo ooooo oooo ooooooooooooo Algoritmus pro nalezení kostry 1 Seřadíme zcela libovolně všechny hrany e\,..., em v E do pořadí a postupně budujeme množiny hran E,(/ = 0,..., m) tak, že Eo = 0 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, Ej) kružnice, a ponecháme Ej = E,_i beze změny v případě opačném. Algoritmus skončí pokud buď 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooo«ooo ooooo oooo ooooooooooooo Algoritmus pro nalezení kostry 1 Seřadíme zcela libovolně všechny hrany e\,..., em v E do pořadí a postupně budujeme množiny hran E,(/ = 0,..., m) tak, že Eo = 0 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, Ej) kružnice, a ponecháme Ej = E,_i beze změny v případě opačném. Algoritmus skončí pokud buď 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. 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku / síti ooooooo ooooo»oo ooooo OOOO ooooooooooooo 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 — í) — k (rozdíl počtu hran ve stromu a počtu hran v grafu T). □ Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooo«o ooooo OOOO ooooooooooooo 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. |r)Q,o. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooo«o ooooo OOOO ooooooooooooo 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 0{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). |r)Q,o. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooo«o ooooo OOOO ooooooooooooo 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 0{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 O(nlogn + m). Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo 0000000« ooooo oooo ooooooooooooo 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. To = ({V},0). V /-tém kroku hledáme mezi hranami, které dosud nejsou v T;_i, mají v T;_i jeden koncový vrchol, ale druhý koncový vrchol do T;_i nepatří. První takovou hranu přidáme i s druhým koncovým vrcholem a získáme tak T,-. Algoritmus skončí, až taková hrana neexistuje. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti OOOOOOO 0000000« ooooo oooo ooooooooooooo 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. To = ({V},0)- V /-tém kroku hledáme mezi hranami, které dosud nejsou v T,_i, mají v T,-_i jeden koncový vrchol, ale druhý koncový vrchol do T,-_i nepatří. První 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti OOOOOOO 0000000« ooooo oooo ooooooooooooo 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. To = ({V},0). V /-tém kroku hledáme mezi hranami, které dosud nejsou v T;_i, mají v T;_i jeden koncový vrchol, ale druhý koncový vrchol do T;_i nepatří. První 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Plán přednášky 9 Platónská tělesa » Barvení map r\OStT3 ffr3ÍU Q Minimální kostra O Toky v sítích Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo •oooo OOOO ooooooooooooo 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo •oooo OOOO ooooooooooooo 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 algopritmické teorie grafů, čekal ještě cca 10 let na svůj oficiální vznik). □ s Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo o«ooo oooo ooooooooooooo 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(e1) < w(e2) <••• < w{em). • v tomto pořadí aplikujeme na hrany postup z Algoritmu 1 pro kostru. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo o«ooo oooo ooooooooooooo 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(e1) < 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku / síti ooooooo oooooooo oo»oo OOOO ooooooooooooo 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo oo»oo OOOO ooooooooooooo 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, T"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 To = T. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo oo»oo OOOO ooooooooooooo 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 To = T. Předpokládejme To 7^ T a buď j nejmenší index, takový, že se T a To liší v hraně e,- (zřejmě e j G T\ To). Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo oo»oo OOOO ooooooooooooo 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, T"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 To = T. Předpokládejme To 7^ T a buď j nejmenší index, takový, že se T a To liší v hraně e,- (zřejmě e j G T\ To). Pak To U {e,-} obsahuje právě jednu kružnici C. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo oo»oo OOOO ooooooooooooo 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, T"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 To = T. Předpokládejme To 7^ T a buď j nejmenší index, takový, že se T a To liší v hraně e,- (zřejmě e j 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{ej<) > w(ej) a kostra s hranami To \ {ei<} 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. □ Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo oooooooo ooo«o OOOO ooooooooooooo I druhý z našich algoritmů 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-,, v,+\ G V \ {v;} tu, která má minimální ohodnocení. Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo oooooooo ooo«o OOOO ooooooooooooo I druhý z našich algoritmů 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-,, 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo ooo«o OOOO ooooooooooooo I druhý z našich algoritmů 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-,, v,+\ G V \ {v;} tu, která má minimální ohodnocení. Výsledný postup je Primuv 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 To = (V,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). Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo oooo» OOOO ooooooooooooo Příklad Určete pomocí uvedených algoritmů minimální kostru grafu 8 2 16 (1-1 13 4 5 10 6 17 (i-i 3 é-é-é-* 1 15 14 Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Plán přednášky a Platónska tělesa 9 Barvení map Q Toky v sítích Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku i / síti ooooooo oooooooo ooooo •ooo ooooooooooooo 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v s ítích Problém maximálního toku v síti ooooooo oooooooo ooooo oo»o ooooooooooooo Definice Síť (fíow 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. O0.O- Rovinné grafy Kostra grafu Minimálni kostra Toky v s ítích Problém maximálního toku v síti ooooooo oooooooo ooooo oo»o ooooooooooooo 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. v^z,s => y, f^= E f(e) eelN(v) eeOUT(v) a tok splňuje kapacitní omezení f\é) < w{e). O0.O- 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) Rovinné grafy Kostra grafu ooooooo oooooooo Minimálni kostra OOOOO Toky v sítích Problém maximálního toku v síti ooo« ooooooooooooo Z definice je zřejmé, že velikost toku můžeme stejně dobře vypočíst jako hodnotu \f\ = E '(«)- E '(«)• eelN(s) eeOUT(s) Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku i / síti ooooooo oooooooo ooooo ooo« ooooooooooooo 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooooo Plán přednášky » Platónská tělesa 9 Barvení map Q Toky v sítích Q Problém maximálního toku v síti Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo •oooooooooooo 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v : ítích Problém maximálního toku v síti ooooooo oooooooo ooooo OOOO •oooooooooooo 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 |C| = J>(e) eec nazýváme kapacita (velikost) řezu C. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku / síti ooooooo oooooooo ooooo OOOO o»ooooooooooo 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku / síti ooooooo oooooooo ooooo OOOO oo«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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku \ / síti ooooooo oooooooo ooooo OOOO OOO0OOOOOOOOO 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku \ / síti ooooooo oooooooo ooooo OOOO OOO0OOOOOOOOO 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooo«oooooooo 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ů íl C V, do kterých existuje nenasycená cesta ze zdroje z. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooo«oooooooo 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ů íl C V, do kterých existuje nenasycená cesta ze zdroje z. • Hlavní cyklus: Dokud s G Ľ opakujeme Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooo«oooooooo 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ů íl 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 Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooo«oooooooo 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ů íl 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 U. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooo«oooooooo 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) = 0 pro všechny hrany e G E a najdeme množinu vrcholů íl 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 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 Ľ a končícími v doplnku V\U. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti OOOOOOO OOOOOOOO OOOOO OOOO OOOOO0OOOOOOO 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti OOOOOOO OOOOOOOO OOOOO OOOO OOOOO0OOOOOOO 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo oooooooo ooooo OOOO oooooo«oooooo 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo oooooooo ooooo OOOO oooooo«oooooo 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í. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti OOOOOOO OOOOOOOO OOOOO OOOO OOOOOOO0OOOOO 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti OOOOOOO OOOOOOOO OOOOO OOOO OOOOOOO0OOOOO 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ě. □ Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti OOOOOOO OOOOOOOO OOOOO OOOO OOOOOOO0OOOOO 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. Rovinné grafy Kostra grafu Minimálr ooooooo oooooooo ooooo í kostra Toky v sítích oooo Problém maximálního toku v síti oooooooo«oooo Príklad špatného chování F-F algoritmu Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooooooo«oooo Príklad špatného chování F-F algoritmu 1/1000 0/1000 1/1 0/1000 1/1000 Rovinné grafy Kostra grafu Minimálr ooooooo oooooooo ooooo í kostra Toky v sítích OOOO Problém maximálního toku v síti oooooooo«oooo Príklad špatného chování F-F algoritmu Rovinné grafy Kostra grafu Minimálr ooooooo oooooooo ooooo í kostra Toky v sítích oooo Problém maximálního toku v síti oooooooo«oooo Príklad špatného chování F-F algoritmu Rovinné grafy Kostra grafu Minimálr ooooooo oooooooo ooooo í kostra Toky v sítích OOOO Problém maximálního toku v síti oooooooo«oooo Príklad špatného chování F-F algoritmu Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooooooo«oooo Príklad špatného chování F-F algoritmu 2/1000 1/1000 1/1 1/1000 2/1000 Rovinné grafy Kostra grafu Minimálr ooooooo oooooooo ooooo í kostra Toky v sítích OOOO Problém maximálního toku v síti oooooooo«oooo Príklad špatného chování F-F algoritmu Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooooooo«oooo Príklad špatného chování F-F algoritmu 1000/1000 999/1000 1/1 999/1000 1000/1000 Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooooooo«oooo Príklad špatného chování F-F algoritmu 1000/1000 1000/1000 0/1 1000/1000 1000/1000 Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooo»ooo 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. Rovinné grafy Kostra grafu Minimálni kostra Toky v : sítích Problém maximálního toku v síti ooooooo oooooooo ooooo OOOO oooooooooo«oo 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čí. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooo«o Moderní algoritmy pro maximální tok Česky viz např. Petr Parubják, XXVI. ASR '2001 Seminár, Instruments and Control, Ostrava, April 26 - 27, 2001 (http://www.fs.vsb.cz/akce/2001/asr2001/Proceedings/ papers/55.pdf Diničuv 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 Edmonds-Karpa. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo ooooooooooo«o Moderní algoritmy pro maximální tok Česky viz např. Petr Parubják, XXVI. ASR '2001 Seminár, Instruments and Control, Ostrava, April 26 - 27, 2001 (http://www.fs.vsb.cz/akce/2001/asr2001/Proceedings/ papers/55.pdf Diničuv 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 Edmonds-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. Rovinné grafy Kostra grafu Minimálni kostra Toky v sítích Problém maximálního toku v síti ooooooo oooooooo ooooo oooo oooooooooooo* 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í).