Matematika III - 8. přednáška Grafy a algoritmy - cesty a souvislost Michal Bulant Masarykova univerzita Fakulta informatiky 18. 11. 2009 □ S O Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy Q Prohledávání v grafech • Prohledávání do šířky a do hloubky • Souvislé komponenty grafu Q Nejkratší cesty • Metrika na grafech • Dijkstruv algoritmus pro hledání nejkratších cest Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Predmetové záložky v IS MU □ s • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-es-facuity.stanford.edu/~knuth/sgb.html). • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-es-facuity.stanford.edu/~knuth/sgb.html). ooooooooooooo Plán přednášky Stupně uzlů a skóre grafu Algoritmy a reprezentace grafů • Grafové algoritmy PrnhlpHáx/ání \/ crrafprh • Prohledávání do šířky a do hloubky • Souvislé komponenty grafu Nejkratší cesty 9 Metrika na grafech • Dijkstruv algoritmus pro hledání nejkratších cest n S - = -E -00*0 ooooooooooooo Stupně uzlů a skóre grafu Izomorfní grafy se od sebe liší pouze přejmenováním vrcholů. Proto musí mít stejné všechny číselné charakteristiky, které se přečíslováním vrcholů nemění. Jednoduché údaje tohoto typu můžeme dostat sledováním počtů hran vycházejících z jednotlivých vrcholů. ooooooooooooo Stupně uzlů a skóre grafu Izomorfní grafy se od sebe liší pouze přejmenováním vrcholů. Proto musí mít stejné všechny číselné charakteristiky, které se přečíslováním vrcholů nemění. Jednoduché údaje tohoto typu můžeme dostat sledováním počtů hran vycházejících z jednotlivých vrcholů. Definice Pro vrchol v G V v grafu G = (V, E) říkáme, že jeho stupeň je k, jestliže v E existuje k hran, jejichž hraničním vrcholem i/je. Píšeme v takovém případě deg v = k. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vrcholu v a výstupní stupeň deg_ v. □ s ooooooooooooo Stupně uzlů a skóre grafu Izomorfní grafy se od sebe liší pouze přejmenováním vrcholů. Proto musí mít stejné všechny číselné charakteristiky, které se přečíslováním vrcholů nemění. Jednoduché údaje tohoto typu můžeme dostat sledováním počtů hran vycházejících z jednotlivých vrcholů. Definice Pro vrchol v G V v grafu G = (V, E) říkáme, že jeho stupeň je k, jestliže v E existuje k hran, jejichž hraničním vrcholem i/je. Píšeme v takovém případě deg v = k. U orientovaných grafů rozlišujeme vstupní stupeň deg+ v vrcholu v a výstupní stupeň deg_ v. Skóre grafu G s vrcholy V = (v\,..., vn) je posloupnost (deg i/i, deg v2,..., deg vn) Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. □ s Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. Naopak ale snadno najdeme příklad grafů se stejným skóre, které izomorfní být nemohou, např. G = C3 U C3 má skóre (2, 2, 2, 2, 2, 2), stejně jako Q- Zjevně ale izomorfní nejsou, protože v Co existuje cesta délky 5, která v druhém grafu být nemůže. □ s Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. Naopak ale snadno najdeme příklad grafů se stejným skóre, které izomorfní být nemohou, např. G = C3 U C3 má skóre (2, 2, 2, 2, 2, 2), stejně jako Q- Zjevně ale izomorfní nejsou, protože v Co existuje cesta délky 5, která v druhém grafu být nemůže. Jaká skóre mohou grafy mít? □ s Pro izomorfní grafy se jejich skóre může lišit pouze permutací hodnot. Pokud tedy porovnáme skóre grafů setříděné podle velikosti hodnot, pak různá skóre zaručují neizomorfnost grafu. Naopak ale snadno najdeme příklad grafů se stejným skóre, které izomorfní být nemohou, např. G = C3 U C3 má skóre (2, 2, 2, 2, 2, 2), stejně jako Q- Zjevně ale izomorfní nejsou, protože v Co existuje cesta délky 5, která v druhém grafu být nemůže. Jaká skóre mohou grafy mít? Protože každá hrana vychází ze dvou vrcholů, musí být v celkovém součtu skóre započtena každá hrana dvakrát. Proto platí ^degi/ = 2|E|. vev Zejména tedy musí být součet všech hodnot skóre sudý. □ s Následující věta je vlastně o návod, jak pro dané skóre buď zjistit, že graf s takovým neexistuje nebo takový graf sestrojit. Věta (Havel, Hakimi - Algoritmus na sestrojení grafu s daným skóre) Pro libovolná přirozená čísla 0 < d\ < ■ ■ ■ < dn existuje graf G na n vrcholech s těmito hodnotami skóre tehdy a jen tehdy, když existuje graf se skóre (c/i, d2,..., dn_dn - 1, dn_dn+1 - 1,..., c/„_i - 1) na n — 1 vrcholech. Příklad Existuje graf, jehož skóre je (2,3,3,3,3,3,4,5)? Pokud ano, sestrojte jej. □ s Důkaz. „<= zrejme. „=>" idea: ukáže se, že při pevně zadaném (vzestupném) skóre (c/i,,..., dn) existuje graf s tímto skóre, jehož vrchol vn je spojen hranou právě s posledními dn vrcholy vn-d„, ■ ■ ■, vn-i- D □ s ooooooooooooo Plán přednášky Q Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy Dr^i~.\^A- • Prohledávání do šířky a do hloubky • Souvislé komponenty grafu Nejkratší cesty 9 Metrika na grafech • Dijkstruv algoritmus pro hledání nejkratších cest n S - = -E -00*0 ooooooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. □ s - = ■€. -o<\(y ooooooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, □ s ooooooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme □ s ooooooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme • a hranou, kterou jsme do uzlu vstoupili. □ s ooooooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme • a hranou, kterou jsme do uzlu vstoupili. □ s ooooooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme • a hranou, kterou jsme do uzlu vstoupili. Při zpracování informace se zároveň rozhodujeme, kterými výstupními hranami budeme pokračovat a v jakém pořadí. □ s ooooooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Rozumíme tím postup, kdy v nějakém orientovaném grafu přecházíme z uzlu do uzlu podél hran a přitom zpracováváme informace, které jsou určeny a ovlivněny: • výsledkem předchozích operací, • uzlem, ve kterém se zrovna nacházíme • a hranou, kterou jsme do uzlu vstoupili. Při zpracování informace se zároveň rozhodujeme, kterými výstupními hranami budeme pokračovat a v jakém pořadí. Pokud je graf neorientovaný, můžeme všechny hrany považovat za dvojice hran orientované opačnými směry. □ s Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: □ s Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: Definice (Hranový seznam/Edge List) Graf G = (V, E) si v něm reprezentujeme jako dva seznamy V a E propojené ukazateli tak, že každý vrchol ukazuje na všechny z něj vycházející hrany (případně také na všechny do něj vcházející hrany u orientovaných grafů) a každá hrana ukazuje na svůj počáteční a koncový vrchol. □ s Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: Definice (Hranový seznam/Edge List) Graf G = (V, E) si v něm reprezentujeme jako dva seznamy V a E propojené ukazateli tak, že každý vrchol ukazuje na všechny z něj vycházející hrany (případně také na všechny do něj vcházející hrany u orientovaných grafů) a každá hrana ukazuje na svůj počáteční a koncový vrchol. Je vidět, že pamět potřebná na uchování grafu je v tomto případě 0(\V\ + \E\), protože na každou hranu ukazujeme právě dvakrát a na každý vrchol ukazujeme tolikrát, kolik je jeho stupeň a součet stupňů je také roven dvojnásobku počtu hran. Až na konstantní násobek jde tedy stále o optimální způsob uchovávání grafu v paměti. □ s Directed Graph Ja) S*Í Oŕ nptrej NQtiW A&SWKV tots fitXrJi him PiŤYft^f.fHm Cor Lac l n v k FVxJurts-aofiK Čeriaci nun About Hm K ..' ■.■ i- . ' Prf*C* Wř* taft «p HfetMffl /*ou ',■■., Adjacency List Representation (a) 5aŕof/JDďes WorfaťdriwcwKťllíste ■ [ • r ■ Undiroctod Graph (b} Adjacency Lisi representation (b) □ S Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (i/i,..., vn) a definujme matici Ac = (a//) nad Z2 (tj zaplněnou jen nulami a jedničkami) takto: {1 jestliže je hrana e// = {v,, vj} v E 0 jestliže není hrana e-,j = {v-n vj} v E Matici Ac nazýváme matice sousednosti grafu G. □ s - Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (i/i,..., vn) a definujme matici Ac = (a//) nad Z2 (tj zaplněnou jen nulami a jedničkami) takto: {1 jestliže je hrana e// = {v,, vj} v E 0 jestliže není hrana e-,j = {v-n vj} v E Matici Ag nazýváme matice sousednosti grafu G. Zadání grafu pomocí matice sousednosti potřebuje vždy 0(n2) místa v paměti. Pokud je ale v grafu málo hran, dostáváme tzv. řídkou matici se skoro všemi prvky nulovými. Takové lze naopak reprezentovat pomocí hranových seznamů odpovídajících grafů a to i včetně obecných číselných hodnot pro jednotlivé hrany. Příklad pro procvičení - násobení matic pomocí reprezentace hranovým seznamem. □ s b D jr f \\ e jCy* f □irBctnrl Grapľi (a) b ô/j\ Jk~^ ' ' ■ Undirected Graph (t>) 2 h C j H i v/ y y v' y ■y y y y v/ Adjacency Matrix Representation (a) n b c d * t a y :> y y y C y y -: y y y y ü y f y Adjacency Malrix Representation (b) □ S Definice (Základní operace nad grafem) • odebrání hrany • přidání hrany 9 přidání vrcholu 9 odebrání vrcholu 9 dělení hrany nově přidaným vrcholem Jak se projeví tyto operace v našich reprezentacích? □ s - Jednoduchou aplikací maticového počtu je tvrzení: Necht G = (V, E) je graf s uspořádanými vrcholy V = (v\,... ,vn) a maticisousednosti Aq. Označme AkG = (a)- ) prvky k-té mocniny matice Aq. Pak a)- je počet sledů délky k mezi vrcholy v\ a vj. Důkaz. Jednoduchou aplikací maticového počtu je tvrzení: Necht G = (V, E) je graf s uspořádanými vrcholy V = (v\,... ,vn) a maticisousednosti Aq. Označme AkG = (a)- ) prvky k-té mocniny matice Aq. Pak a)- je počet sledů délky k mezi vrcholy v\ a vj. Důkaz. Indukcí. D Důsledek Jsou-li G = (V, E) a Ac jako v předchozí větě, pak lze všechny dvojice vrcholů G spojit cestou právě tehdy, když má matice (A + In)"-1 samé nenulové členy (zde In označuje jednotkovou matici s n řádky a sloupci). □ s Q Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy Q Prohledávání v grafech • Prohledávání do šířky a do hloubky • Souvislé komponenty grafu Q Nejkratší cesty » Metrika na grafech • Dijkstruv algoritmus pro hledání nejkratších cest •oooooooooooo Prohledávání v grafech Algoritmy bývají založeny na postupném prohledávání všech vrcholů v grafu. Zpravidla máme zadaný počáteční vrchol nebo si jej na začátku procesu zvolíme. V průběhu procesu pak v každém okamžiku jsou vrcholy • již zpracované, tj. ty, kterými jsme již při běhu algoritmu prošli a definitivně je zpracovali; • aktivní, tj. ty vrcholy, které jsou detekovány a připraveny pro zpracování; » spící, tj. ty vrcholy, na které teprve dojde. •oooooooooooo Prohledávání v grafech Algoritmy bývají založeny na postupném prohledávání všech vrcholů v grafu. Zpravidla máme zadaný počáteční vrchol nebo si jej na začátku procesu zvolíme. V průběhu procesu pak v každém okamžiku jsou vrcholy • již zpracované, tj. ty, kterými jsme již při běhu algoritmu prošli a definitivně je zpracovali; • aktivní, tj. ty vrcholy, které jsou detekovány a připraveny pro zpracování; • spící, tj. ty vrcholy, na které teprve dojde. Zároveň si udržujeme přehled o již zpracovaných hranách. V každém okamžiku musí být množiny vrcholů a/nebo hran v těchto skupinách disjunktním rozdělením množin vrcholů V a množin E hran grafu G a některý z aktivních vrcholů je aktuálně zpracováván. Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. □ s Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. • V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme stav na aktivní. □ s Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. • V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme stav na aktivní. • V dalších krocích vždy u zpracovávaného vrcholu probíráme ty z něho vycházející hrany, které dosud nebyly probrány a jejich koncové vrcholy přidáváme mezi aktivní. Tento postup aplikujeme stejně u orientovaných i neorientovaných grafů, jen se drobně mění význam adjektiv koncový a počáteční u vrcholů. □ s Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. • V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme stav na aktivní. • V dalších krocích vždy u zpracovávaného vrcholu probíráme ty z něho vycházející hrany, které dosud nebyly probrány a jejich koncové vrcholy přidáváme mezi aktivní. Tento postup aplikujeme stejně u orientovaných i neorientovaných grafů, jen se drobně mění význam adjektiv koncový a počáteční u vrcholů. V konkrétních úlohách se můžeme omezovat na některé z hran, které vychází z aktuálního vrcholu. Na principu to ale nic podstatného nemění. □ s Pro realizaci algoritmů je nutné se rozhodnout, v jakém pořadí zpracováváme aktivní vrcholy a v jakém pořadí zpracováváme hrany z nich vycházející. V zásadě přichází v úvahu dvě možnosti zpracovávání vrcholů: O vrcholy vybíráme pro další zpracování ve stejném pořadí, jak se stávaly aktivními (fronta - FIFO) O dalším vrcholem vybraným pro zpracování je poslední zaktivněný vrchol (zásobník - LIFO). V prvním případě hovoříme o prohledávání do šířky, ve druhém o prohledávání do hloubky. □ s Na první pohled je zřejmá role volby vhodných datových struktur pro uchovávání údajů o grafu. Hranový seznam umožňuje projít všechny hrany vycházející z právě zpracovávaného vrcholu v čase lineárně úměrném jejich počtu. Každou hranu přitom diskutujeme nejvýše dvakrát, protože má právě dva konce. Zjevně tedy platí: □ s Na první pohled je zřejmá role volby vhodných datových struktur pro uchovávání údajů o grafu. Hranový seznam umožňuje projít všechny hrany vycházející z právě zpracovávaného vrcholu v čase lineárně úměrném jejich počtu. Každou hranu přitom diskutujeme nejvýše dvakrát, protože má právě dva konce. Zjevně tedy platí: Celkový čas realizace vyhledávání do šířky i do hloubky Je 0{{n + m) * K), kde n Je počet vrcholů v grafu, m Je počet hran v grafu a K Je čas potřebný na zpracování Jedné hrany, resp. Jednoho vrcholu. □ s Ilustrace prohledávání do šířky: □ s - = ■€. -o<\(y Ilustrace prohledávání do šířky: Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: * <*. Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: * <*. Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: •........• •........• Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Ilustrace prohledávání do šířky: . 1*'^ / \ f"'®, : \ ?"t : \ f"t í •........• •........• •........• •........• Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za první bereme směr kolmo dolů. □ s Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. n S - = -E -00*0 Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® • •........• •........• □ s - = ■€. -o<\(y Totéž postupem do hloubky. Všimněte si, že první krok je stejný jako v předchozím případě. -® •........ číslu aktuálního vrcholu). Poznámka Základ algoritmu tkví v tom, že pomocné číslo každého vrcholu je pořadovým číslem vrcholu z téže souvislé komponenty. Pokud je pomocné číslo menší než pořadové (museli jsme se někdy pokusit jít po hraně do již navštíveného vrcholu - tedy uzavřít orientovanou smyčku), pak vrchol do něhož se vracíme bude ve stejně silně souvislé komponentě jako aktuální vrchol. □ s Pamatujme si zejména: • Při snaze jít do již navštíveného vrcholu, aktualizujeme jeho pořadovým číslem. • Při návratu k předchůdci aktualizujeme vždy pomocným číslem. • Ve chvíli, kdy už z daného vrcholu nevede nepoužitá hrana a obě čísla jsou stejná, uzavíráme komponentu a to tak, že odebíráme všechny vrcholy za zásobníku, doku nenarazíme na současný (ekvivalentně: v komponentě leží všechny vrcholy s pomocným číslem > číslu aktuálního vrcholu). • Je vhodné si kreslit graf průchodu (postup do hloubky znázorníme např. kreslením doprava či dolů), aby bylo jasné, kterými hranami se vracíme. Poznámka Základ algoritmu tkví v tom, že pomocné číslo každého vrcholu je pořadovým číslem vrcholu z téže souvislé komponenty. Pokud je pomocné číslo menší než pořadové (museli jsme se někdy pokusit jít po hraně do již navštíveného vrcholu - tedy uzavřít orientovanou smyčku), pak vrchol do něhož se vracíme bude ve stejně silně souvislé komponentě jako aktuální vrchol. □ s Q Stupně uzlů a skóre grafu Q Algoritmy a reprezentace grafů • Grafové algoritmy C\ PrnhlpHáx/ání \/ crrafprh • Prohledávání do šířky a do hloubky • Souvislé komponenty grafu Q Nejkratší cesty • Metrika na grafech • Dijkstruv algoritmus pro hledání nejkratších cest □ g - = ^ -00*0 Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo c1g(v, w), která je rovna počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme Óg{v, w) = oo. ooooooooooooo Metrika na grafech Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo c1g(v, w), která je rovna počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme Óg{v, w) = oo. Budeme v dalším uvažovat pouze souvislý graf G. Pak pro takto zadanou funkci cIg '■ V x V —> N platí obvyklé tři vlastnosti vzdálenosti: • dc(v, w) > 0 a přitom dc(v, w) = 0 právě tehdy, když v = w; 9 vzdálenost je symetrická, tj dc(v, w) = dc(w, v); • platí trojúhelníková nerovnost, tj. pro každou trojici vrcholů v, w,z platí ddv, z) < ddv, w) + ddw, z). ooooooooooooo Metrika na grafech Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo c1g(v, w), která je rovna počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme Óg{v, w) = oo. Budeme v dalším uvažovat pouze souvislý graf G. Pak pro takto zadanou funkci cIg '■ V x V —> N platí obvyklé tři vlastnosti vzdálenosti: • dc(v, w) > 0 a přitom dc(v, w) = 0 právě tehdy, když v = w; 9 vzdálenost je symetrická, tj dc(v, w) = dc(w, v); • platí trojúhelníková nerovnost, tj. pro každou trojici vrcholů v, w,z platí dG(v, z) < ddv, w) + ddw, z). Říkáme, že dG je metrika na grafu G. ooooooooooooo Nejkratší cesty o«ooooooooc Metrika na grafu splňuje navíc: • dc{v, w) má vždy nezáporné celočíselné hodnoty; • je-li d^v, w) > 1, pak existuje nějaký vrchol z různý od v a w a takový, že d^v, w) = dc(v,z) + d^z, w). Každá funkce de s výše uvedenými pěti vlastnostmi na V x V je metrikou nějakého grafu s vrcholy V. □ s Nejkratší cestu v grafu, která vychází z daného uzlu v a končí v jiném uzlu w můžeme hledat pomocí prohledávání grafu do šířky. Při tomto typu prohledávání totiž postupně diskutujeme vrcholy, do kterých se umíme dostat z výchozího vrcholu po jediné hraně, poté projdeme všechny, které mají vzdálenost nejvýše 2 atd. Na této jednoduché úvaze je založen jeden z nejpoužívanějších grafových algoritmů - tzv. Dijkstrův algoritmus. Nejkratší cestu v grafu, která vychází z daného uzlu v a končí v jiném uzlu w můžeme hledat pomocí prohledávání grafu do šířky. Při tomto typu prohledávání totiž postupně diskutujeme vrcholy, do kterých se umíme dostat z výchozího vrcholu po jediné hraně, poté projdeme všechny, které mají vzdálenost nejvýše 2 atd. Na této jednoduché úvaze je založen jeden z nejpoužívanějších grafových algoritmů - tzv. Dijkstrův algoritmus. Tento algoritmus hledá nejkratší cesty za (reálného) předpokladu, kdy jednotlivé hrany e jsou ohodnoceny vzdálenostmi, tj. kladnými reálnými čísly w(e). Kromě aplikace na hledání vzdáleností v silničních nebo jiných sítích to mohou být také výnosy, toky v sítích atd. 17 • Vstupem algoritmu je graf G počáteční vrchol vq. (V, E) s ohodnocením hran a n S - = -E -00*0 • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol i/o- • Výstupem je ohodnocení vrcholů čísly dw(v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu i/o do vrcholu v. Všimněte si, že místo původní úlohy (nalézt nejkratší cestu mezi dvěma vrcholy) řešíme i něco navíc - nalezneme nejkratší cestu z v do všech vrcholů. Postup dobře funguje v orientovaných i neorientovaných grafech. □ s • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol i/o- • Výstupem je ohodnocení vrcholů čísly dw(v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu i/o do vrcholu v. Všimněte si, že místo původní úlohy (nalézt nejkratší cestu mezi dvěma vrcholy) řešíme i něco navíc - nalezneme nejkratší cestu z v do všech vrcholů. Postup dobře funguje v orientovaných i neorientovaných grafech. Je skutečně podstatné, že všechna naše ohodnocení jsou kladná. Zkusme si rozmyslet třeba cestu P3 se záporně ohodnocenou prostřední hranou. Při procházení sledu mezi krajními vrcholy bychom vzdálenost zmenšovali každým prodloužením sledu o průchod prostřední hranou tam a zpět. □ s Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: • U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d{v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu vq. □ s Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: • U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d{v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu vq. • Množina již zpracovaných vrcholů bude v každém okamžiku obsahovat ty vrcholy, u kterých již nejkratší cestu známe, tj. d (v) = dw(v). □ S Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: • U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d{v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu vq. • Množina již zpracovaných vrcholů bude v každém okamžiku obsahovat ty vrcholy, u kterých již nejkratší cestu známe, tj. d (v) = dw(v). • Do množiny aktivních (právě zpracovávaných) vrcholů W zařadíme vždy právě ty vrcholy y z množiny spících vrcholů Z, pro které je d{y) = min{c/(z); z G Z}. □ s ooooooooooooo Nejkratší cesty ooo«ooooo Dijkstrův algoritmus Předpokládáme, že graf G má alespoň dva vrcholy. • Inicializační krok: Nastavíme hodnoty u všech v G V, d (v) nastavíme Z = V, W = 0 pro v = vq OO pro V ^ Vq, □ s - ooooooooooooo Nejkratší cesty ooo«ooooo Dijkstrův algoritmus Předpokládáme, že graf G má alespoň dva vrcholy. • Inicializační krok: Nastavíme hodnoty u všech v G V, d (v) 0 pro v = vo oo pro v ^ vq, nastavíme Z = V, W = 0. • Test cyklu: Pokud není ohodnocení všech vrcholů y G Z rovno oo, pokračujeme dalším krokem, v opačném případě algoritmus končí. □ s • Aktualizace stavu vrcholů: • Najdeme množinu N všech vrcholů v G Z, pro které d(v) nabývá nejmenší možné hodnoty ô = min{c/(y); y G Z}; • posledně zpracované aktivní vrcholy 1/1/ přesuneme do množiny zpracovaných a za nové aktivní vrcholy zvolíme 1/1/ = N a odebereme je ze spících, tj. množina spících bude nadále Z\N. □ s • Aktualizace stavu vrcholů: • Najdeme množinu N všech vrcholů v G Z, pro které d(v) nabývá nejmenší možné hodnoty ô = min{c/(y); y G Z}; • posledně zpracované aktivní vrcholy 1/1/ přesuneme do množiny zpracovaných a za nové aktivní vrcholy zvolíme 1/1/ = N a odebereme je ze spících, tj. množina spících bude nadále Z\N. • Tělo hlavního cyklu: Pro všechny hrany v množině Ewz všech hran vycházejících z některého aktivního vrcholu v a končících ve spícím vrcholu y opakujeme: • Vybereme dosud nezpracovanou hranu e{x,y} G Ewz', • Pokud je d(x) + w(e) < d{y), nahradíme d(y) touto menší hodnotou. □ s Pro všechny vrcholy v ležící v souvislé komponentě vrcholu s najde Dijsktrův algoritmus vzdálenosti dw{v). Vrcholy ostatních souvislých komponent zůstanou ohodnoceny d (v) = oo. Algoritmus lze implementovat tak, že ukončí svoji práci v čase 0{n log n + m), kde n je počet vrcholů a m je počet hran v grafu G. Důkaz. • během celého algoritmu platí d(v) > dw{v) pro všechna ve V. Pro všechny vrcholy v ležící v souvislé komponentě vrcholu s najde Dijsktrův algoritmus vzdálenosti dw{v). Vrcholy ostatních souvislých komponent zůstanou ohodnoceny d (v) = oo. Algoritmus lze implementovat tak, že ukončí svoji práci v čase 0{n log n + m), kde n je počet vrcholů a m je počet hran v grafu G. Důkaz. během celého algoritmu platí d(v) > dw{v) pro všechna ve V. po skončení algoritmu platí d(v) < dw{v) pro všechna v G V (Prostřednictvím silnějšího tvrzení: jsou-li 0 = d\ < di < ... < d k < oo všechny různé konečné vzdálenosti vrcholů od s a označíme-li Mi = {v G V; dw{v) = dj}, pak se krok Aktualizace stavu vrcholů provede přesně /(-krát a po jeho /-tém vykonání platí N = Mj,ö = di a V\Z = u'k=1Mj.) ooooooooooooo Nejkratší cesty oooooooo«oo Modifikace algoritmu • Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. □ s ooooooooooooo Modifikace algoritmu Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. Můžeme využít dodatečné informace (při hledání nejkratší cesty z Brna do Prahy v silniční síti asi nepojedeme přes Ostravu) - heuristika h : V —> R splňující w({x>y}) — Hx) ~~ Ky) Pro každou hranu {x,y}. ooooooooooooo Modifikace algoritmu Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. Můžeme využít dodatečné informace (při hledání nejkratší cesty z Brna do Prahy v silniční síti asi nepojedeme přes Ostravu) - heuristika h : V —> R splňující w({x>y}) — Hx) ~~ Ky) Pro každou hranu {x,y}. ooooooooooooo Modifikace algoritmu Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. Můžeme využít dodatečné informace (při hledání nejkratší cesty z Brna do Prahy v silniční síti asi nepojedeme přes Ostravu) - heuristika h : V —> R splňující w({x>y}) — Hx) ~~ Ky) Pro každou hranu {x,y}. Doporučení: h(v) je dolní odhad vzdálenosti v do cílového vrcholu (např. vzdálenost „vzdušnou čarou"). Místo minimalizace d{y) pro y G Z tak v algoritmu minimalizujeme d{y) + h(y). ooooooooooooo Další algoritmy a aplikace Principy Dijkstrova algoritmu se využívají v OSPF (Open Shortest Paths First) routovacím protokolu. □ s ooooooooooooo Další algoritmy a aplikace Principy Dijkstrova algoritmu se využívají v OSPF (Open Shortest Paths First) routovacím protokolu. Bellman-Fordův algoritmus • pracuje na stejném principu jako Dijkstruv; místo postupu po uzlech je zpracovává „naráz" - cyklus relaxace probíhá (\V\ — 1) krát přes všechny hrany • připouští záporné hrany a detekuje záporné cykly o je obvykle časově náročnější než Dijkstruv • distribuovaná verze je (či spíše byla) používána v distance-vector routing protocol □ s Floydův algoritmus (all pairs shortest paths) • v čase 0(n3) vypočte vzdálenosti mezi všemi vrcholy • vychází z matice A délek hran a postupně počítá matice Uo, U\,..., U\v\, kde Uk(iJ) je délka nejkratší cesty z / do j, kde cesta prochází pouze vrcholy z {1,2,..., k}. • výpočet vychází ze vztahu Uk(iJ) = min{tyfc_i(/,j), "fc-i('\ k) + ufc_i(/f,j')}- • je efektivnější než „upravená mocnina" Ac (násobení sčítání, sčítání —> minimum) - ta je totiž 0(n4), resp. (optimalizovaná) O(n3logn).