Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Matematika III - 8. přednáška Grafy a algoritmy - cesty a souvislost Michal Bulant Masarykova univerzita Fakulta informatiky 10. 11. 2010 Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Obsah přednášky 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 Q Hledání nejkratších cest • Dijkstrův algoritmus pro hledání nejkratších cest a Nejkratší cesty mezi všemi dvojicemi vrcholů Q Eulerovské grafy a hamiltonovské kružnice Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Neš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/~hlineny/Vyuka/GT/ Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Neš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/~hlineny/Vyuka/GT/ • Rensselaer Polytechnic Institute - Graph Theory Applet (http://links.math.rpi.edu/applets/appindex/ graphtheory.html). • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-cs-facuity.Stanford.edu/~knuth/sgb.html). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. » Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Neš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/~hlineny/Vyuka/GT/ • Rensselaer Polytechnic Institute - Graph Theory Applet (http://links.math.rpi.edu/applets/appindex/ graphtheory.html). • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-cs-facuity.Stanford.edu/~knuth/sgb.html). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Plán přednášky Q Algoritmy a reprezentace grafů » Grafové algoritmy O Prohledávání v grafech <* Prohledávání do šířky a do hloubky • Souvislé komponenty grafu O Nejkratší cesty • Metrika na grafech • Dijkstrův algoritmus pro hledání nejkratších cest • Nejkratší cesty mezi všemi dvojicemi vrcholů Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské •oooooo ooooooooooooo oo oooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské •oooooo ooooooooooooo oo oooooooooo 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í, Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské •oooooo ooooooooooooo oo oooooooooo 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 Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské •oooooo ooooooooooooo oo oooooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské •oooooo ooooooooooooo oo oooooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské •oooooo ooooooooooooo oo oooooooooo 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í. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské •oooooo ooooooooooooo oo oooooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské o«ooooo ooooooooooooo oo oooooooooo Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: Abychom mohli algoritmy realizovat pomocí počítače, je třeba umět uvažovaný graf efektivně zadat. Uvedeme dva příklady: 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské o«ooooo ooooooooooooo oo oooooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské oo«oooo ooooooooooooo oo oooooooooo □ s - ■ ► -5 -O^O Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooo«ooo ooooooooooooo oo oooooooooo Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (i/i,..., vn) a definujme matici Aq = (a//) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto: 1 jestliže je hrana e-,j = {V;, vj} v E 0 jestliže není hrana e-,j = {V;, vj} v E Matici Aq nazýváme matice sousednosti grafu G. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooo«ooo ooooooooooooo oo oooooooooo Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (i/i,..., vn) a definujme matici Aq = (a//) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto: 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. 1 jestliže je hrana e-,j = {v,, vj} v E 0 jestliže není hrana e-,j = {V;, vj} v E Matici Aq nazýváme matice sousednosti grafu G. □ s - ■ Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské oooo»oo ooooooooooooo oo oooooooooo Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooo«o ooooooooooooo oo oooooooooo Definice (Základní operace nad grafem) "* • odebrání hrany 9 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? Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské 000000» ooooooooooooo oo oooooooooo Jednoduchou aplikací maticového počtu je tvrzení: Věta Necht G = (V, E) je graf s uspořádanými vrcholy V = (v\,... ,vn) a maticísousednosti 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í. □ Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské 000000» ooooooooooooo oo oooooooooo Jednoduchou aplikací maticového počtu je tvrzení: Věta Necht G = (V, E) je graf s uspořádanými vrcholy V = (v\,... ,vn) a maticísousednosti 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ůsledek Jsou-li G = (V, E) a Aq jako v předchozí větě, pak lze všechny dvojice vrcholů G spojit cestou právě tehdy když má matice (A + In)n_1 samé nenulové členy (zde in označuje jednotkovou matici s n řádky a sloupci). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Plán přednášky Q Algoritmy a reprezentace grafů a Grafové algoritmy Q Prohledávání v grafech c Prohledávání do šířky a do hloubky • Souvislé komponenty grafu 9 Metrika na gratech O Hledání nejkratších cest • Dijkstrův algoritmus pro hledání nejkratších cest • Nejkratší cesty mezi všemi dvojicemi vrcholů Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO «000000000000 oo oooooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO «000000000000 oo oooooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo o»ooooooooooo oo oooooooooo Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo o»ooooooooooo oo oooooooooo 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í. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo o»ooooooooooo oo oooooooooo 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ů. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo o»ooooooooooo oo oooooooooo 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í. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oo«oooooooooo oo oooooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOO0OOOOOOOOO oo oooooooooo 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í: Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOO0OOOOOOOOO oo oooooooooo 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í: Věta 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 0000*00000000 oo oooooooooo Ilustrace prohledávání do šířky: Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooo«oooooooo oo oooooooooo 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ů". Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 0000*00000000 oo oooooooooo 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ů". Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 0000*00000000 oo oooooooooo 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ů". Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 0000*00000000 oo oooooooooo 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ů". Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 0000*00000000 oo oooooooooo 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ů". Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 0000*00000000 oo oooooooooo 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ů". Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooo«oooooooo oo oooooooooo 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ů". Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOO0OOOOOOO oo oooooooooo Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOO0OOOOOOO oo oooooooooo Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOO0OOOOOOO oo oooooooooo Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOO0OOOOOOO oo oooooooooo Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOO0OOOOOOO oo oooooooooo Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOO0OOOOOOO oo oooooooooo Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOO0OOOOOOO oo oooooooooo Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOO0OOOOOOO oo oooooooooo Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. Prohledávání "do hloubky"odpovídá interpretaci rekurze v běžných imperativních jazycích (např. i v Maplu) - v těchto případech je ale stavový graf potenciálně nekonečný a prohledávání do hloubky tak samozřejmě nemusí nalézt všechny vrcholy dostupné z daného vrcholu po cestách konečné délky (narozdíl od prohledávání do šířky). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooo«oooooo oo oooooooooo Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooo«oooooo oo oooooooooo Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooo«oooooo oo oooooooooo Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu • navštívenou místnost označíme, pokud je již označená, tak se ihned vrátíme stejnou chodbou zpět Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooo«oooooo oo oooooooooo Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu • navštívenou místnost označíme, pokud je již označená, tak se ihned vrátíme stejnou chodbou zpět • z dosud nenavštívené místnosti postupujeme dále Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooo«oooooo oo oooooooooo Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu • navštívenou místnost označíme, pokud je již označená, tak se ihned vrátíme stejnou chodbou zpět • z dosud nenavštívené místnosti postupujeme dále • jsou-li již všechny chodby vedoucí z místnosti použity, vracíme se zpět chodbou, která je označena jen jednou čarou Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooo«oooooo oo oooooooooo Prohledávání bludiště Průchod bludištěm (s křídou) prostřednictvím prohledávání do hloubky v neorientovaném grafu - úkolem je najít východ nebo dokázat, že neexistuje: • každou chodbu při prvním průchodu označíme čarou, při návratu přidáme druhou čáru • při východu z místnosti preferujeme neoznačenou chodbu • navštívenou místnost označíme, pokud je již označená, tak se ihned vrátíme stejnou chodbou zpět • z dosud nenavštívené místnosti postupujeme dále • jsou-li již všechny chodby vedoucí z místnosti použity, vracíme se zpět chodbou, která je označena jen jednou čarou • pokud z dané místnosti vedou pouze chodby, které jsou označeny 2 čarami, hledání ukončíme (nutně jde o výchozí místnost, východ neexistuje a můžeme s klidem umřít). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooo»ooooo oo oooooooooo Souvislé komponenty grafu Definice Nechť je G = (V, E) neorientovaný graf. Na množině vrcholů grafu G zavedeme relaci ~ tak, že v ~ w právě když existuje cesta z v do w. Promyslete si, že tato relace je dobře definovaná a že se jedná o ekvivalenci. Každá třída [v] této ekvivalence definuje indukovaný podgraf G[v] C G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G[v] říkáme souvislé komponenty grafu G. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooo»ooooo oo oooooooooo Souvislé komponenty grafu Definice Nechť je G = (V, E) neorientovaný graf. Na množině vrcholů grafu G zavedeme relaci ~ tak, že v ~ w právě když existuje cesta z v do w. Promyslete si, že tato relace je dobře definovaná a že se jedná o ekvivalenci. Každá třída [v] této ekvivalence definuje indukovaný podgraf G[v] C G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G[„] říkáme souvislé komponenty grafu G. Pro orientované grafy postupujeme stejně, pouze u ~ požadujeme aby existovala neorientovaná cesta z uzlu v do uzlu w (tj. můžeme "jít i proti směru šipek"). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooo»ooooo oo oooooooooo Souvislé komponenty grafu Definice Nechť je G = (V, E) neorientovaný graf. Na množině vrcholů grafu G zavedeme relaci ~ tak, že v ~ w právě když existuje cesta z v do w. Promyslete si, že tato relace je dobře definovaná a že se jedná o ekvivalenci. Každá třída [v] této ekvivalence definuje indukovaný podgraf G[v] C G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G[„] říkáme souvislé komponenty grafu G. Pro orientované grafy postupujeme stejně, pouze u ~ požadujeme aby existovala neorientovaná cesta z uzlu v do uzlu w (tj. můžeme "jít i proti směru šipek"). Jinými slovy: Každý graf G = (V, E) se přirozeně rozpadá na disjunktní podgrafy G; takové, že vrcholy v G G; a w G Gj jsou spojeny nějakou cestou právě, když / = j. To jsou právě souvislé komponenty grafu G. □ s Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooooo«oooo oo oooooooooo Pro hledání všech souvislých komponent v grafu lze užít prohledávání — dodatečnou informací, kterou musíme zpracovávat je, kterou komponentu aktuálně procházíme. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooooo«oooo oo oooooooooo Pro hledání všech souvislých komponent v grafu lze užít prohledávání — dodatečnou informací, kterou musíme zpracovávat je, kterou komponentu aktuálně procházíme. Definice Řekneme, že graf G = (V, E) je • souvislý, jestliže má právě jednu souvislou komponentu; • vrcholově /(-souvislý, jestliže má alespoň k + 1 vrcholů a bude souvislý po odebrání libovolné podmnožiny k — l vrcholů; • hranově /(-souvislý, jestliže bude souvislý po odebrání libovolné podmnožiny k — 1 hran. Hranu, jejímž odebráním se zvýší počet souvislých komponent grafu G, nazýváme mostem. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooooo«oooo oo oooooooooo Pro hledání všech souvislých komponent v grafu lze užít prohledávání — dodatečnou informací, kterou musíme zpracovávat je, kterou komponentu aktuálně procházíme. Definice Řekneme, že graf G = (V, E) je • souvislý, jestliže má právě jednu souvislou komponentu; • vrcholově /(-souvislý, jestliže má alespoň k + 1 vrcholů a bude souvislý po odebrání libovolné podmnožiny k — l vrcholů; • hranově /(-souvislý, jestliže bude souvislý po odebrání libovolné podmnožiny k — 1 hran. Hranu, jejímž odebráním se zvýší počet souvislých komponent grafu G, nazýváme mostem. - Silnější souvislost grafu je žádoucí např. u síťových aplikací, kdy požadujeme značnou redundanci poskytovaných služeb v případě výpadku některých linek (tj. hran) nebo uzlů (tj. vrcholů). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooo«ooo oo oooooooooo Speciální případ: 2-souvislý graf je takový souvislý graf o alespoň třech vrcholech, kdy vynecháním libovolného vrcholu nenarušíme jeho souvislost. Věta Pro graf G = (V, E) s alespoň třemi vrcholy jsou následující podmínky ekvivalentní: 9 G je (vrcholově) 2-souvislý; 9 každé dva vrcholy v a w grafu G leží na společné kružnici; 9 graf G je možné vytvořit z trojúhelníku K3 pomocí postupných dělení hran. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooo«ooo oo oooooooooo Speciální případ: 2-souvislý graf je takový souvislý graf o alespoň třech vrcholech, kdy vynecháním libovolného vrcholu nenarušíme jeho souvislost. Věta Pro graf G = (V, E) s alespoň třemi vrcholy jsou následující podmínky ekvivalentní: 9 G je (vrcholově) 2-souvislý; 9 každé dva vrcholy v a w grafu G leží na společné kružnici; 9 graf G je možné vytvořit z trojúhelníku K3 pomocí postupných dělení hran. Obecnější je tzv. Mengerova věta (obd. „vrcholová verze"): Věta 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooooooo«oo oo oooooooooo Silně souvislé komponenty Definice Nechť je G = (V, E) orientovaný graf. Na množině vrcholů grafu G zavedeme relaci ř« tak, že v ř« w právě když existuje orientovaná cesta z v do w i orientovaná cesta z w do v. Zřejmě se opět jedná o ekvivalenci. Každá třída [v] této ekvivalence definuje indukovaný podgraf G[v] C G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G[v] říkáme silně souvislé komponenty grafu G. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo oooooooooo«oo oo oooooooooo Silně souvislé komponenty Definice Nechť je G = (V, E) orientovaný graf. Na množině vrcholů grafu G zavedeme relaci ř« tak, že v ř« w právě když existuje orientovaná cesta z v do w i orientovaná cesta z w do v. Zřejmě se opět jedná o ekvivalenci. Každá třída [v] této ekvivalence definuje indukovaný podgraf G[v] C G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G[„] říkáme silně souvislé komponenty grafu G. Příklad Viz https://is.muni.cz/auth/el/1433/podzim2009/MB103/ um/Tarj an_pr.pdf Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooo«o oo oooooooooo Tarjanův algoritmus Q Každý vrchol označujeme dvojicí čísel, z nichž první určuje pořadí příchodu a druhý pomocné číslo, které se v průběhu aktualizuje a rozhoduje o příslušnosti ke komponentě (zároveň máme u každého vrcholu odkaz na jeho předchůdce). Při prvním příchodu do vrcholu ho označíme dvojicí poradí, poradí a vložíme do zásobníku. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooo«o oo oooooooooo Tarjanův algoritmus Q Každý vrchol označujeme dvojicí čísel, z nichž první určuje pořadí příchodu a druhý pomocné číslo, které se v průběhu aktualizuje a rozhoduje o příslušnosti ke komponentě (zároveň máme u každého vrcholu odkaz na jeho předchůdce). Při prvním příchodu do vrcholu ho označíme dvojicí poradí, poradí a vložíme do zásobníku. O Pokud existuje hrana do dosud nenavštíveného vrcholu, jdi do něj. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooo«o oo oooooooooo Tarjanův algoritmus Q Každý vrchol označujeme dvojicí čísel, z nichž první určuje pořadí příchodu a druhý pomocné číslo, které se v průběhu aktualizuje a rozhoduje o příslušnosti ke komponentě (zároveň máme u každého vrcholu odkaz na jeho předchůdce). Při prvním příchodu do vrcholu ho označíme dvojicí poradí, poradí a vložíme do zásobníku. O Pokud existuje hrana do dosud nenavštíveného vrcholu, jdi do něj. Q Pokud existuje hrana do již navštíveného vrcholu, nahraď pomocné číslo stávajícího vrcholu pořadovým číslem vrcholu, do nějž směřuje hrana (pouze, je-li menší). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooo«o oo oooooooooo Tarjanův algoritmus Q Každý vrchol označujeme dvojicí čísel, z nichž první určuje pořadí příchodu a druhý pomocné číslo, které se v průběhu aktualizuje a rozhoduje o příslušnosti ke komponentě (zároveň máme u každého vrcholu odkaz na jeho předchůdce). Při prvním příchodu do vrcholu ho označíme dvojicí poradí, poradí a vložíme do zásobníku. O Pokud existuje hrana do dosud nenavštíveného vrcholu, jdi do něj. Q Pokud existuje hrana do již navštíveného vrcholu, nahraď pomocné číslo stávajícího vrcholu pořadovým číslem vrcholu, do nějž směřuje hrana (pouze, je-li menší). Q Pokud neexistuje nepoužitá hrana a obě čísla u daného vrcholu jsou stejná, je tento vrchol prvním navštíveným vrcholem své silně souvislé komponenty. Ze zásobníku odeberme všechny vrcholy až po nynější vrchol. Vrať se do předchůdce a aktualizuj jeho pomocné číslo pomocným číslem vrcholu, z nějž se vracíme (je-li menší). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooo«o oo oooooooooo Tarjanův algoritmus Q Každý vrchol označujeme dvojicí čísel, z nichž první určuje pořadí příchodu a druhý pomocné číslo, které se v průběhu aktualizuje a rozhoduje o příslušnosti ke komponentě (zároveň máme u každého vrcholu odkaz na jeho předchůdce). Při prvním příchodu do vrcholu ho označíme dvojicí poradí, poradí a vložíme do zásobníku. O Pokud existuje hrana do dosud nenavštíveného vrcholu, jdi do něj. Q Pokud existuje hrana do již navštíveného vrcholu, nahraď pomocné číslo stávajícího vrcholu pořadovým číslem vrcholu, do nějž směřuje hrana (pouze, je-li menší). Q Pokud neexistuje nepoužitá hrana a obě čísla u daného vrcholu jsou stejná, je tento vrchol prvním navštíveným vrcholem své silně souvislé komponenty. Ze zásobníku odeberme všechny vrcholy až po nynější vrchol. Vrať se do předchůdce a aktualizuj jeho pomocné číslo pomocným číslem vrcholu, z nějž se vracíme (je-li menší). Q Pokud neexistuje nepoužitá hrana a čísla u daného vrcholu jsou různá, vrať se do předchůdce a aktualizuj jeho pomocné číslo pomocným číslem vrcholu, z nějž se vracíme (je-li menší). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooo«o oo oooooooooo Tarjanův algoritmus Q Každý vrchol označujeme dvojicí čísel, z nichž první určuje pořadí příchodu a druhý pomocné číslo, které se v průběhu aktualizuje a rozhoduje o příslušnosti ke komponentě (zároveň máme u každého vrcholu odkaz na jeho předchůdce). Při prvním příchodu do vrcholu ho označíme dvojicí poradí, poradí a vložíme do zásobníku. O Pokud existuje hrana do dosud nenavštíveného vrcholu, jdi do něj. Q Pokud existuje hrana do již navštíveného vrcholu, nahraď pomocné číslo stávajícího vrcholu pořadovým číslem vrcholu, do nějž směřuje hrana (pouze, je-li menší). Q Pokud neexistuje nepoužitá hrana a obě čísla u daného vrcholu jsou stejná, je tento vrchol prvním navštíveným vrcholem své silně souvislé komponenty. Ze zásobníku odeberme všechny vrcholy až po nynější vrchol. Vrať se do předchůdce a aktualizuj jeho pomocné číslo pomocným číslem vrcholu, z nějž se vracíme (je-li menší). Q Pokud neexistuje nepoužitá hrana a čísla u daného vrcholu jsou různá, vrať se do předchůdce a aktualizuj jeho pomocné číslo pomocným číslem vrcholu, z nějž se vracíme (je-li menší). Q Nejsou-li ještě vyčerpány všechny vrcholy a z právě zpracovaného vrcholu již není kam se vrátit, zvol jiný vrchol a pokračuj v algoritmu. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 000000000000» oo oooooooooo Pamatujme si zejména: • Při snaze jít do již navštíveného vrcholu, aktualizujeme jeho pořadovým číslem. 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 000000000000» oo oooooooooo 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. 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 000000000000» oo oooooooooo 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). 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO 000000000000» oo oooooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Plán přednášky Q Algoritmy a reprezentace grafů • Grafové algoritmy » Prohledávání do šířky a do hloubky • Souvislé komponenty grafu Q Nejkratší cesty • Metrika na grafech • Dijkstrův algoritmus pro hledání nejkratších cest a Nejkratší cesty mezi všemi dvojicemi vrcholů O Eulerovské erafv a hamiltonovské kružnice Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo «o oooooooooo 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 dc{v, w) = oo. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo «o oooooooooo 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 dc{v, w) = oo. Budeme v dalším uvažovat pouze souvislý graf G. Pak pro takto zadanou funkci dG '■ 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). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo «o oooooooooo 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 dc{v, w) = oo. Budeme v dalším uvažovat pouze souvislý graf G. Pak pro takto zadanou funkci dG '■ 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); 9 platí trojúhelníková nerovnost, tj. pro každou trojici vrcholů v, w, z platí ddv, z) < ddv, w) + ddw, z). Říkáme, že c/g je metrika na grafu G. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo o» oooooooooo Metrika na grafu splňuje navíc: • dc{v, w) má vždy nezáporné celočíselné hodnoty; • je-li c1g(v, w) > 1, pak existuje nějaký vrchol z různý od v a w a takový, že dc{v, w) = dc{v,z) + dc{z, w). Každá funkce dc s výše uvedenými pěti vlastnostmi na V x V je metrikou nějakého grafu s vrcholy V. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Plán přednášky Q Algoritmy a reprezentace grafů • Grafové algoritmy » Prohledávání do šířky a do hloubky • Souvislé komponenty grafu • IvicLIIftd lid grafech Q Hledání nejkratších cest • Dijkstrův algoritmus pro hledání nejkratších cest a Nejkratší cesty mezi všemi dvojicemi vrcholů Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO »000000000 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 nej používanějších grafových algoritmů - tzv. Dijkstrův algoritmus. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO »000000000 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 nej použí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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo o«oooooooo • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol vq. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo o«oooooooo • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol vo- • Výstupem je ohodnocení vrcholů čísly dw(v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu vo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo o«oooooooo • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol vo- • Výstupem je ohodnocení vrcholů čísly dw(v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu vo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oo»ooooooo 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oo»ooooooo 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). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oo»ooooooo 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}. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo ooo«oooooo 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 = vo oo pro v ^ vq, Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo ooo«oooooo 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, 0 pro v = vq OO pro v ^ Vq, nastavíme Z = V, W = 0. • Test cyklu: Pokud není ohodnocení všech vrcholů y S Z rovno oo, pokračujeme dalším krokem, v opačném případě algoritmus končí. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO OOOO0OOOOO • 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 e 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO OOOO0OOOOO • 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO 00000*0000 Věta 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 v g V. n 90.0- Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO 00000*0000 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 v g 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 O = 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ě k-krát a po jeho /-tém vykonání platí N = Mj,ô = di a V\Z = U^=1M,-.) 00. o- Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO OOOOOO0OOO 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. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO OOOOOO0OOO 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. 9 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}. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO OOOOOO0OOO 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. 9 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}. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO OOOOOO0OOO 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. 9 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 S Z tak v algoritmu minimalizujeme d{y) + h(y). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo ooooooo«oo Další algoritmy a aplikace Principy Dijkstrova algoritmu se využívají v OSPF (Open Shortest Paths First) routovacím protokolu. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo ooooooo«oo 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 Dijkstrův; 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 » je obvykle časově náročnější než Dijkstrův • distribuovaná verze je (či spíše byla) používána v distance-vector routing protocol Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooo»o Upravené násobení matic (a II pairs shortest paths) 9 v čase O(n3logn) vypočte vzdálenosti mezi všemi vrcholy • vychází z matice A délek hran a postupně počítá matice U\, L/2,..., U\n-\\, kde Up(iJ) je délka nejkratší cesty z / do j, která má nejvýše p hran. • výpočet vychází ze vztahu Up(i,j) = min{up_i(/, k) + akJ}. k 9 jde vlastně o "upravené umocňování'Ac (násobení —> sčítání, sčítání —> minimum) Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské OOOOOOO OOOOOOOOOOOOO OO OOOOOOOOO* Floyd-Warshallův algoritmus (a// 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 Ľo, L/i,..., L/|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), k) + ufc_i(/f,j')}. • je efektivnější než "upravená mocnina"Aq (násobení —>■ sčítání, sčítání —> minimum) - ta je totiž 0(n4), resp. (optimalizovaná) O(n3logn). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Plán přednášky Q Algoritmy a reprezentace grafů • Grafové algoritmy » Prohledávání do šířky a do hloubky • Souvislé komponenty grafu *• IVIeulKd lid grafech • Dijkstrův algoritmus pro hledání nejkratších cest a Nejkratší cesty mezi všemi dvojicemi vrcholů Q Eulerovské grafy a hamiltonovské kružnice Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Grafy jedním tahem Jistě se každý setkal s dětskou hříčkou Nakresli obrázek jedním tahem. V řeči grafů to znamená najděte sled, který projde všechny hrany právě jednou a každý vrchol alespoň jednou. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Grafy jedním tahem Jistě se každý setkal s dětskou hříčkou Nakresli obrázek jedním tahem. V řeči grafů to znamená najděte sled, který projde všechny hrany právě jednou a každý vrchol alespoň jednou. Definice Sled, který prochází právě jednou všemi hranami a začíná a končí v jednom vrcholu, se nazývá uzavřený eulerovský tah. Grafům, které takový sled připouští říkáme eulerovské. Hovoříme rovněž o (neuzavřeném) eulerovském tahu, kde vypouštíme požadavek na stejný výchozí a cílový vrchol. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Terminologie odkazuje na klasický příběh o sedmi mostech ve městě Královec (Königsberg, tj. Kaliningrad), které se měly projít na procházce každý právě jednou a důkaz nemožnosti takové procházky od Leonharda Eulera z roku 1736. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Terminologie odkazuje na klasický příběh o sedmi mostech ve městě Královec (Königsberg, tj. Kaliningrad), které se měly projít na procházce každý právě jednou a důkaz nemožnosti takové procházky od Leonharda Eulera z roku 1736. Situace je znázorněna na obrázku. Nalevo dobová mapa, napravo odpovídající (multi)graf. Vrcholy tohoto grafu odpovídají „souvislé pevnině", hrany mostům. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Věta Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. Důkaz. Podmínka je zřejmě nutná. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Věta Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. Důkaz. Podmínka je zřejmě nutná. Dostatečnost podmínky se ukáže sporem uvážením tahu v G maximální možné délky. □ Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Kupodivu je obecné řešení takového problému dosti snadné, jak ukazuje následující věta. Samozřejmě také ukazuje, že se Euler zamýšleným způsobem procházet nemohl. Věta Graf G je eulerovský tehdy a jen tehdy když je souvislý a všechny vrcholy v G mají sudý stupeň. Důkaz. Podmínka je zřejmě nutná. Dostatečnost podmínky se ukáže sporem uvážením tahu v G maximální možné délky. □ Důsledek Graf lze nakreslit jedním tahem právě tehdy když má všechny stupně vrcholů sudé nebo když existují právě dva vrcholy se stupněm lichým. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Příklad O Určete nejmenší počet mostů, které je třeba v Královci přistavět, aby byl graf eulerovský. O Jaká je situace v Kaliningradu nyní (od dob Eulerových doznalo zejména působením válek město mnoho změn)? Byl by dnes schopen Euler svoji procházku realizovat? Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Eulerovské orientované grafy Definice Orientovaný graf (V, E) nazveme eulerovský, jestliže v něm existuje uzavřený orientovaný tah, který obsahuje každou hranu právě jednou a každý vrchol aspoň jednou. Orientované eulerovské grafy lze rovněž velmi dobře charakterizovat. K tomu ovšem potřebujeme některé nové pojmy. Definice Orientovaný graf nazveme vyvážený, jestliže pro každý jeho vrchol v platí deg+(v) = deg_(v). Symetrizacíorientovaného grafu (V, E) nazýváme neorientovaný graf (V,~Ě), kde E = Ux, y}; (x, y) e E nebo (y, x) g E}. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Věta Orientovaný graf G je eulerovský právě když je vyvážený a jeho symetrizace je souvislý graf (tj. graf G je slabě souvislý). Důkaz. Analogický jako v neorientovaném případe. □ Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Problém čínského pošťáka (route inspection problem) Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Problém čínského pošťáka (route inspection problem) Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Zřejmě je v případě, že graf G je eulerovský, nejkratším takovým sledem příslušný eulerovský tah. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Problém čínského pošťáka (route inspection problem) Route inspection problem je zobecněním problému nalezení eulerovského tahu. Úkolem je nalézt nejkratší sled v grafu s ohodnocenými hranami, který obsahuje každou hranu v grafu. Tento problém má v současnosti mnoho praktického využití (analýza DNA, směrování robotů, svoz odpadu, ...). Zřejmě je v případě, že graf G je eulerovský, nejkratším takovým sledem příslušný eulerovský tah. V opačném případě nutně graf obsahuje sudý počet vrcholů lichého stupně. Tento graf je třeba přidáváním hran doplnit na eulerovský (multi)graf (později ukážeme, že v případě stromů to znamená nutnost zdvojení všech hran). Snadno lze ukázat, že to lze udělat v polynomiálním čase jak v orientovaném, tak neorientovaném případě, v případě multigrafů je to však problém NP-úplný. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Zatímco (zdánlivě podobně složitý) problém nalezení eulerovského tahu je triviální, zjistit, zda je daný graf hamiltonovský, je NP-úplný problém. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Hamiltonovské grafy Obdobný požadavek na průchod grafem, ovšem tak, abychom prošli právě jednou každým vrcholem (tj. zároveň nejvýše jednou každou hranou), vede na obtížné problémy. Takový průchod grafem je realizován kružnicí, která obsahuje všechny vrcholy grafu G, hovoříme o hamiltonovských kružnicích v grafu G. Graf se nazývá hamiltonovský, jestliže má hamiltonovskou kružnici. Zatímco (zdánlivě podobně složitý) problém nalezení eulerovského tahu je triviální, zjistit, zda je daný graf hamiltonovský, je NP-úplný problém. V praxi je ovšem problém nalezení hamiltonovské kružnice (či jeho modifikace - např. problém obchodního cestujícího) podstatou mnoha problémů v logistice, je proto často žádoucí nalezení i suboptimálního řešení (v případě problému obchodního cestujícího). Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Příklad (Icosian Game - William Rovan Hamilton) Nalezněte hamiltonovskou kružnici v grafu tvořeném vrcholy a hranami pravidelného dodekaedru (dvanáctistěnu) - viz http:// www.puzzlemuseum.com/month/picm02/200201hamilton.jpg Příklad Existuje hamiltonovská kružnice v Petersenovš grafu? Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Příklad (Icosian Game - William Rovan Hamilton) Nalezněte hamiltonovskou kružnici v grafu tvořeném vrcholy a hranami pravidelného dodekaedru (dvanáctistěnu) - viz http:// www.puzzlemuseum.com/month/picm02/200201hamilton.jpg Příklad Existuje hamiltonovská kružnice v Petersenově grafu? Věta (Dirac (1952)) Má-li v grafu G s n > 3 vrcholy každý vrchol stupeň alespoň n/2 je G hamiltonovský. Věta (Ore (1960)) Má-li v grafu G s n > 4 vrcholy každá dvojice nesousedních vrcholů součet stupňů alespoň n, je G hamiltonovský. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Uzávěrem grafu G v této souvislosti rozumíme graf c/(G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(v) > n. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Uzávěrem grafu G v této souvislosti rozumíme graf c/(G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(v) > n. Věta (Bondy,Chvátal (1972)) Graf G je hamiltonovský, právě když je cl(G) hamiltonovský. Algoritmy a reprezentace grafů Prohledávání v grafech Nejkratší cesty Hledání nejkratších cest Eulerovské grafy a hamiltonovské ooooooo ooooooooooooo oo oooooooooo Uzávěrem grafu G v této souvislosti rozumíme graf c/(G), který dostaneme z G přidáním všech hran u, v takových, že u, v nejsou sousední a deg(u) + deg(v) > n. Věta (Bondy,Chvátal (1972)) Graf G je hamiltonovský, právě když je c/(G) hamiltonovský. Je vidět, že Oreho (a tedy i Diracova) věta je triviálním důsledkem této věty.