Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo Matematika III - 9. přednáška Grafy a algoritmy - cesty a souvislost Michal Bulant Masarykova univerzita Fakulta informatiky 14. 11. 2012 Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest • Metrika na grafech • Dijkstrův algoritmus pro hledání nejkratších cest • Nejkratší cesty mezi všemi dvojicemi vrcholů Q Eulerovské grafy a hamiltonovské kružnice Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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. m uni.cz/~hlineny/Vyuka/GT/ Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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. m uni.cz/~hlineny/Vyuka/GT/ • 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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. m uni.cz/~hlineny/Vyuka/GT/ • 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo Plán 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 Hledání nejkratších cest • Metrika na grafech • Dijkstrův algoritmus pro hledání nejkratších cest • Nejkratší cesty mezi všemi dvojicemi vrcholů Q Eulerovské grafy a hamiltonovské kružnice Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice •oooooo ooooooooooooo oooooooooooo Grafy jsou jazykem, ve kterém často formulujeme algoritmy. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice •oooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice •oooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice •oooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice •oooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice •oooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice •oooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice o»ooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice o»ooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice oo»oooo ooooooooooooo oooooooooooo ► 1 -O^O Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice 000*000 ooooooooooooo oooooooooooo Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (1/1,..., vn) a definujme matici Ag = (a/,-) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto: 1 jestliže je hrana e-,j = {1//, vj} v E O jestliže není hrana e-,j = {1//, vj} v E Matici Ag nazýváme matice sousednosti grafu G (obdobně v případě orientovaných grafů či multigrafů). Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooo#ooo ooooooooooooo oooooooooooo Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (1/1,..., vn) a definujme matici Aq = (a/,-) nad Z2 (tj. zaplněnou jen nulami a jedničkami) takto: Matici Ag nazýváme matice sousednosti grafu G (obdobně v případě orientovaných grafů či multigrafů). 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. 1 jestliže je hrana e-,j = {1//, vj} v E 0 jestliže není hrana e-,j = {1//, vj} v E Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice oooo»oo ooooooooooooo oooooooooooo Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooo»o ooooooooooooo oooooooooooo Základní operace nad grafem ^ • odebrání hrany « přidání hrany « přidání vrcholu » odebrání vrcholu « 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice 000000» ooooooooooooo oooooooooooo Jednoduchou aplikací maticového počtu je tvrzení: Věta Necht G = (V, E) je graf s uspořádanými vrcholy V = (vi,... ,vn) a maticísousednosti Ag- Označme AkG = (aj^) prvky k-té mocniny (k) matice Aq. Pak a- je počet sledů délky k mezi vrcholy v, a vj. Důkaz. Indukcí._□ J Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice 000000» ooooooooooooo oooooooooooo Jednoduchou aplikací maticového počtu je tvrzení: Věta Necht G = (V, E) je graf s uspořádanými vrcholy V = (vi,... ,vn) a maticísousednosti Ag- Označme AkG = (aj^) prvky k-té mocniny (k) 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 Ag jako v předchozí větě, pak lze všechny dvojice vrcholů G spojit cestou právě tehdy, když má matice (A + I,,)"-1 samé nenulové členy (zde I„ označuje jednotkovou matici s n řádky a sloupci). Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo Plán 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 Hledání nejkratších cest • Metrika na grafech • Dijkstrův algoritmus pro hledání nejkratších cest • Nejkratší cesty mezi všemi dvojicemi vrcholů Q Eulerovské grafy a hamiltonovské kružnice Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO »000000000000 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. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO »000000000000 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. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo o»ooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo o»ooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo o»ooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo o»ooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oosoooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooo»ooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooo»ooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooo«oooooooo oooooooooooo Ilustrace prohledávání do šířky: Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooo«oooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooo«oooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooo«oooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooo«oooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooo«oooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooo«oooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooo«oooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooo»ooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooo»ooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooo»ooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooo»ooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooo»ooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooo»ooooooo oooooooooooo Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooo»ooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooo»ooooooo oooooooooooo 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 - 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooo«oooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooo«oooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooo«oooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooo«oooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooo«oooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooo«oooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO 0000000*00000 oooooooooooo 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 i/i/. 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^j c G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G^j říkáme souvislé komponenty grafu G. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooo»ooooo oooooooooooo 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 i/i/. 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^j c G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G^j ří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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooo»ooooo oooooooooooo 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 i/i/. 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^j c G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G^j ří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 Gf- 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. 4 □ ► 4 S ► 4 1 -00.0 Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooooo»oooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooooo»oooo oooooooooooo 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ě) /c-souvislý, jestliže má alespoň k + 1 vrcholů a bude souvislý po odebrání libovolné podmnožiny k — 1 vrcholů; » hranově /c-souvislý, jestliže bude souvislý po odebrání libovolné podmnožiny k — 1 hran. Hranu (resp. vrchol), jejímž odebráním se zvýší počet souvislých komponent grafu G, nazýváme mostem (resp. artikulací) tohoto grafu. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooooo»oooo oooooooooooo 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ě) /c-souvislý, jestliže má alespoň k + 1 vrcholů a bude souvislý po odebrání libovolné podmnožiny k — 1 vrcholů; » hranově /c-souvislý, jestliže bude souvislý po odebrání libovolné podmnožiny k — 1 hran. Hranu (resp. vrchol), jejímž odebráním se zvýší počet souvislých komponent grafu G, nazýváme mostem (resp. artikulací) tohoto grafu. 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ů<(£j> Y^ljojů^ < Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooo»ooo oooooooooooo 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í: • G je (vrcholově) 2-souvislý; • každé dva vrcholy v a w grafu G leží na společné kružnici; • 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooo»ooo oooooooooooo 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í: • G je (vrcholově) 2-souvislý; • každé dva vrcholy v a w grafu G leží na společné kružnici; • 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooooooo»oo oooooooooooo 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^j C G (disjunktní sjednocení těchto podgrafů už nemusí tvořit původní graf G). Podgrafům G^j říkáme silně souvislé komponenty grafu G. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo oooooooooo»oo oooooooooooo 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^j C G (disjunktní sjednocení těchto podgrafů už nemusí tvořit původní graf G). Podgrafům G^j ří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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooo»o oooooooooooo 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í pořadí, pořadí a vložíme do zásobníku. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooo»o oooooooooooo 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í pořadí, pořadí a vložíme do zásobníku. Q Pokud existuje hrana do dosud nenavštíveného vrcholu, jdi do něj. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooo»o oooooooooooo 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í pořadí, pořadí a vložíme do zásobníku. Q 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooo»o oooooooooooo 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í pořadí, pořadí a vložíme do zásobníku. Q 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooo»o oooooooooooo 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í pořadí, pořadí a vložíme do zásobníku. Q 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ší). O 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooo»o oooooooooooo 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í pořadí, pořadí a vložíme do zásobníku. Q 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ší). O 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ší). O 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO 000000000000» oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO 000000000000» oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO 000000000000» oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO 000000000000» oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo Plán přednášky Q Algoritmy a reprezentace grafů • Grafové algoritmy Prohledávání v grafech • Prohledávání do šířky a do hloubky • Souvislé komponenty grafu Q Hledání nejkratších cest • Metrika na grafech • Dijkstrův algoritmus pro hledání nejkratších cest • Nejkratší cesty mezi všemi dvojicemi vrcholů Q Eulerovské grafy a hamiltonovské kružnice Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO OOOOOOOOOOOOO »00000000000 Metrika na grafech Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo dc(v, w), které je rovno 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO OOOOOOOOOOOOO »00000000000 Metrika na grafech Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo dG(v, w), které je rovno počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme dG(v, w) = oo. Budeme v dalším uvažovat pouze souvislý graf G. Pak pro takto zadanou funkci de : V x V —> N platí obvyklé tři vlastnosti vzdálenosti: • dc(v, w) > O a přitom dc(v, w) = O právě tehdy, když v = w; • 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í cIg{v,z) < dG(v, w) + dG(w,z). Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO OOOOOOOOOOOOO »00000000000 Metrika na grafech Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo dG(v, w), které je rovno počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme dG(v, w) = oo. Budeme v dalším uvažovat pouze souvislý graf G. Pak pro takto zadanou funkci de : V x V —> N platí obvyklé tři vlastnosti vzdálenosti: • dc(v, w) > O a přitom dc(v, w) = O právě tehdy, když v = w; • 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í cIg{v,z) < dG(v, w) + dG(w,z). Říkáme, že dG je metrika na grafu G. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo o^oooooooooo Metrika na grafu splňuje navíc: • dc(v, w) má vždy nezáporné celočíselné hodnoty; • je-li dc(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 de 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oo»ooooooooo Dijkstrův algoritmus Nej kratší cestu v grafu, která vychází z daného uzlu vo a končí v jiném uzlu v, 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oo»ooooooooo Dijkstrův algoritmus Nej kratší cestu v grafu, která vychází z daného uzlu vo a končí v jiném uzlu v, 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 reprezenta' ooooooo Prohledávání v grafec ooooooooooooo Hledání nejkratších cest ooosoooooooo • Vstupem algoritmu je graf G počáteční vrchol vq. (V, E) s ohodnocením hran a Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooosoooooooo • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol vq. • Výstupem je ohodnocení vrcholů čísly dVQ(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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooosoooooooo • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol vq. • Výstupem je ohodnocení vrcholů čísly dVQ(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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooo»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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooo»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 vo. • 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) = dV0(v). Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooo»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) = dV0(v). 9 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) = m\n{d(z); z G Z}. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooooo»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 = vq oo pro v ^ vq, Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooooo»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 G 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooo»ooooo • Aktualizace stavu vrcholů: • Najdeme množinu N všech vrcholů v E Z, pro které d(v) nabývá nejmenší možné hodnoty S — m\n{d(y); y e Z}; » posledně zpracované aktivní vrcholy W přesuneme do množiny zpracovaných a za nové aktivní vrcholy zvolíme W — 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooo»ooooo • Aktualizace stavu vrcholů: • Najdeme množinu N všech vrcholů v E Z, pro které d(v) nabývá nejmenší možné hodnoty S — m\n{d(y); y e Z}; » posledně zpracované aktivní vrcholy W přesuneme do množiny zpracovaných a za nové aktivní vrcholy zvolíme W — 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} e 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooooooo«oooo Věta Pro všechny vrcholy v ležící v souvislé komponentě vrcholu vq najde Dijsktrův algoritmus vzdálenosti dVQ(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. t Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooooooo«oooo Věta Pro všechny vrcholy v ležící v souvislé komponentě vrcholu vq najde Dijsktrův algoritmus vzdálenosti dVQ(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) > dVQ(v) pro všechna v G V. n 00.0 Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooooooo«oooo Pro všechny vrcholy v ležící v souvislé komponentě vrcholu vq najde Dijsktrův algoritmus vzdálenosti dVQ(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) > dVQ(v) pro všechna v G V. po skončení algoritmu platí d(v) < dVQ(v) pro všechna v G V (Prostřednictvím silnějšího tvrzení: jsou-li 0 = di < d2 < ... < dk < oo všechny různé konečné vzdálenosti vrcholů od vo a označíme-li M; = {v G V; dVQ(v) = dj}, pak se krok Aktualizace stavu vrcholů provede přesně /c-krát a po jeho /-tém vykonání platí N = M,, 5 = d-, a V \ Z = U^=1M,-.) 00.0 Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooo»ooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooo»ooo 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 —> M splňující w/({x,y}) > h(x) — h(y) 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). Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooooooooo»oo Další algoritmy a aplikace Principy Dijkstrova algoritmu se využívají v OSPF (Open Shortest Paths First) routovacím protokolu. Jhttp: //www. ibiblio. org/links/applets/appindex/graphthegry . Irfcml Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo ooooooooo»oo Další algoritmy a aplikace Principy Dijkstrova algoritmu se využívají v OSPF (Open Shortest Paths First) routovacím protokolu. Bellman-Fordův algoritmus1 • 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 • použití možné jen na orientovaných grafech • 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 Jhttp: //www.ibiblio.org/links/applets/appindex/graphtheory.html = Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooo»o Upravené násobení matic (all pairs shortest paths) • v čase 0(n3 logn) vypočte vzdálenosti mezi všemi vrcholy • vychází z matice A délek hran a postupně počítá matice Ui, U2, • • •, _i|, kde Up(i,j) je délka nejkratší cesty z / do j, která má nejvýše p hran. • výpočet vychází ze vztahu uP{iJ) = min{up_i(/, k) + akJ}. k • jde vlastně o „upravené umocňování" Aq (násobení —> sčítání, sčítání —> minimum) Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice OOOOOOO OOOOOOOOOOOOO 00000000000» Floyd-Warshallů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 Uq, Ui, ..., U\v\, kde u/<(i,j) 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{i,j) = min{íyfe_i(/,7'), k) + u/,_i(/c,_/')}. • je efektivnější než „upravená mocnina" Ag - ta je totiž 0(n4), resp. (optimalizovaná) 0(n3logn). Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo Plán přednášky Q Algoritmy a reprezentace grafů • Grafové algoritmy Prohledávání v grafech • Prohledávání do šířky a do hloubky • Souvislé komponenty grafu Q Hledání nejkratších cest • Metrika na grafech • Dijkstrův algoritmus pro hledání nejkratších cest • Nejkratší cesty mezi všemi dvojicemi vrcholů Q Eulerovské grafy a hamiltonovské kružnice Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo hem 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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._1 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo Příklad O Určete nejmenší počet mostů, které je třeba v Královci přistavět, aby byl graf eulerovský. Q 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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. 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,T), kde E = Ux'y}; (x>y)£f nebo (y,x) e £}■ Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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řípadě. □ Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 (BondyChvátal (1972)) Graf G je hamiltonovský, právě když je cl(G) hamiltonovský. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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 (BondyChvá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. Algoritmy a reprezentace grafů Prohledávání v grafech Hledání nejkratších cest Eulerovské grafy a hamiltonovské kružnice ooooooo ooooooooooooo oooooooooooo 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ý. Je vidět, že Oreho (a tedy i Diracova) věta je triviálním důsledkem této věty. Důkaz. Zřejmě stačí dokázat, že pokud je G hamiltonovský po přidání hrany {u, v} takové, že u, v nejsou sousední a deg(u) + deg(v) > n, pak je hamiltonovský i bez této hrany. Předpokládejme, že G + uv je hamiltonovský a G nikoliv. Pak existuje hamiltonovská cesta v G z u do v. Pro každý vrchol sousedící s u platí, že jeho předchůdce na této cestě nemůže sousedit s v (jinak bychom měli hamiltonovskou kružnici v G). Tedy deg(u) + deg(v) < n — 1. □ ■0 0.O