Matematika III - 8. přednáška Grafy a algoritmy - cesty a souvislost Michal Bulant Masarykova univerzita Fakulta informatiky 6. 11. 2007 • Martin Panák, Jan Slovák, Drsná matematika, e-text. 9 Předmětové záložky v IS MU • Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. • Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ • Donald E. Knuth, The Stanford GraphBase, ACM, New York, 1993 (http://www-es-facuity.stanford.edu/~knuth/sgb.html). 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. 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. Directed Graph (aj Seiotnones HUWfttewaiiii IpAfl.hlm fltůuihlm PiŤYftčr.him CarixinsziK PtůfctAtw ŕ-'-'i'" i1-:" f-todLK- Viťili* CoriacI n^iK ňhx'h'n JViVÄyJrffu PristcK iKjii Ptťjplt JrJpS fnJruhfr»! /■H.-í.t ■! '«i pFVJKľj' r"'.'51 iiť^j fam ~~| Adjacency List Representation (a) Setof nodes Nadas'AtiJiunncv Usts B- -.- [ í~ "T"__ • i ■ Undirected Graph {b) Adjacency List representation (b) Definice (Matice sousednosti grafu) Uvažme (neorientovaný) graf G = (V, E), zvolme uspořádání jeho vrcholů V = (v\,... ,vn) a definujme matici Ac = {a,j) 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 Ac nazýváme matice sousednosti grafu G. Zadání grafu pomocí matice sousednosti potřebuje vždy 0(n2) místa v paměti. Pokud je ale v grafu málo hran, dostáváme tzv. řídkou matici se skoro všemi prvky nulovými. Takové lze naopak reprezentovat pomocí „hranových seznamů" odpovídajících grafů a to i včetně obecných číselných hodnot pro jednotlivé hrany. Příklad pro procvičení - násobení matic pomocí reprezentace hranovým seznamem. Directed Graph <» Undirected Graph (b) a d c u B 1 a y u y y e y y d y ./ y e y y r Adjacency Matrix Representation (a) 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? Jednoduchou aplikací maticového počtu je tvrzení: Nechť G = (V, E) je graf s uspořádanými vrcholy V = (v\,..., vn) a maticísoused nosti Ag- Označme Ag = (a): ) prvky k-té mocniny matice Ag- Pak a/- je počet sledů délky k mezi vrcholy v-, a vj. Důkaz. Indukcí. D Důsledek Jsou-li G = (V, E) a Ag jako v předchozí větě, pak lze všechny dvojice vrcholů G spojit cestou právě tehdy, když má matice (A + In)"_1 samé nenulové členy (zde In označuje jednotkovou matici s n řádky a sloupci). Algoritmy bývají založeny na postupném prohledávání všech vrcholů v grafu. Zpravidla máme zadaný počáteční vrchol nebo si jej na začátku procesu zvolíme. V průběhu procesu pak v každém okamžiku jsou vrcholy • již zpracované, tj. ty, kterými jsme již při běhu algoritmu prošli a definitivně je zpracovali; • aktivní, tj. ty vrcholy, které jsou detekovány a připraveny pro zpracování; • spící, tj. ty vrcholy, na které teprve dojde. Zároveň si udržujeme přehled o již zpracovaných hranách. V každém okamžiku musí být množiny vrcholů a/nebo hran v těchto skupinách disjunktním rozdělením množin vrcholů V a množin E hran grafu G a některý z aktivních vrcholů je aktuálně zpracováván. Základní postup: • Na počátku máme jeden aktivní vrchol a všechny ostání vrcholy jsou spící. • 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í. 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) Q 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. Na první pohled je zřejmá role volby vhodných datových struktur pro uchovávání údajů o grafu. Hranový seznam umožňuje projít všechny hrany vycházející z právě zpracovávaného vrcholu v čase lineárně úměrném jejich počtu. Každou hranu přitom diskutujeme nejvýše dvakrát, protože má právě dva konce. Zjevně tedy platí: Celkový čas realizace vyhledávání do šířky i do hloubky je 0{{n + m) * K), kde n je počet vrcholů v grafu, m je počet hran v grafu a K je čas potřebný na zpracování jedné hrany, resp. jednoho vrcholu. Ilustrace prohledávání do šířky: . W"\ > \ ř"®. / \ f't / \ W"t (' •........• •........• •........• •........• Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za „první" bereme směr „kolmo dolů". Totéž postupem „do hloubky". Všimněte si, že první krok je stejný jako v předchozím případě. -® tfrf •........<é •........• •........• •........• 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). 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). 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. Pro orientované grafy postupujeme stejně, pouze u ~ požadujeme aby cesta existovala z uzlu v do uzlu w nebo naopak z uzlu w do uzlu v. Jinými slovy: Každý graf G = (V, E) se přirozeně rozpadá na disjunktní podgrafy G; takové, že vrcholy v G Gj a w € Gj jsou spojeny nějakou cestou právě, když / =_/'. To jsou právě souvislé komponenty grafu G. 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 — l vrcholů; • hranově /c-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ů). 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. Pro graf G = (V, E) s alespoň třemi vrcholy jsou následující podmínky ekvivalentní: 9 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"): 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. Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo (Jg(v, w), která je rovna počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme Óg{v, w) = oo. Budeme v dalším uvažovat pouze souvislý graf G. Pak pro takto zadanou funkci Óg '■ V x V —> N platí obvyklé tři vlastnosti vzdálenosti: • (Jg(v, w) > 0 a přitom (Jg(v, w) = 0 právě tehdy, když v = w; • vzdálenost je symetrická, tj (Jg(v, w) = (Jg(w, v); • platí trojúhelníková nerovnost, tj. pro každou trojici vrcholů v, w,z platí c1g(v, z) < Čg{v, w) + dc(w, z). Říkáme, že óg je metrika na grafu G. Metrika na grafu splňuje navíc: • dc{v, w) má vždy nezáporné celočíselné hodnoty; • je-li d^v, w) > 1, pak existuje nějaký vrchol z různý od v a w a takový, že d^v, w) = dc(v,z) + dg(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. Nejkratší cestu v grafu, která vychází z daného uzlu v a končí v jiném uzlu w můžeme hledat pomocí prohledávání grafu do šířky. Při tomto typu prohledávání totiž postupně diskutujeme vrcholy, do kterých se umíme dostat z výchozího vrcholu po jediné hraně, poté projdeme všechny, které mají vzdálenost nejvýše 2 atd. Na této jednoduché úvaze je založen jeden z nejpoužívanějších grafových algoritmů - tzv. Dijkstrův algoritmus. Tento algoritmus hledá nejkratší cesty za (reálného) předpokladu, kdy jednotlivé hrany e jsou ohodnoceny „vzdálenostmi", tj. kladnými reálnými čísly w(e). Kromě aplikace na hledání vzdáleností v silničních nebo jiných sítích to mohou být také výnosy, toky v sítích atd. • Vstupem algoritmu je graf G = (V, E) s ohodnocením hran a počáteční vrchol i/o- » Výstupem je ohodnocení vrcholů čísly dw(v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu i/o do vrcholu v. Všimněte si, že místo původní úlohy (nalézt nejkratší cestu mezi dvěma vrcholy) řešíme i něco navíc - nalezneme nejkratší cestu z 1/ 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. 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}. Předpokládáme, že graf G má alespoň dva vrcholy. • Inicializační krok: Nastavíme hodnoty u všech v G V, ÍO pro v = vQ d{v) = i I oo pro v 7t vq , nastavíme Z = V, W = 0. • Test cyklu: Pokud není ohodnocení všech vrcholů y G Z rovno 00, pokračujeme dalším krokem, v opačném případě algoritmus končí. • 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 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} G Ewz', • Pokud je d(x) + w(e) < d(y), nahradíme d(y) touto menší hodnotou. 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 0 = d\ < d-i < ... < d k < oo všechny různé konečné vzdálenosti vrcholů od s a označíme-li M; = {v G V; dw{v) = d;}, pak se krok Aktualizace stavu vrcholů provede přesně /c-krát a po jeho /-tém vykonání platí N = Mi,ö = di a V\Z = u'k=1Mj.) • Pokud nás skutečně zajímá jen nejkratší cesta do konkrétního vrcholu, pak samozřejmě výpočet ukončíme poté, co tento vrchol přejde do množiny již zpracovaných. • Můžeme využít dodatečné informace (při hledání nejkratší cesty z Brna do Prahy v silniční síti asi nepojedeme přes Ostravu) - heuristika h : V —> R splňující w({x>y}) — Hx) ~~ Ky) Pro každou hranu {x,y}. Doporučení: h(v) je dolní odhad vzdálenosti v do cílového vrcholu (např. vzdálenost „vzdušnou čarou"). Místo minimalizace d{y) pro y G Z tak v algoritmu minimalizujeme d{y) + h{y). 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 Floydův algoritmus (all pairs shortest paths) 9 v čase 0(n3) vypočte vzdálenosti mezi všemi vrcholy • vychází z matice A délek hran a postupně počítá matice Uo, I/l, ..., U\v\, kde Uk(iJ) je délka nejkratší cesty z / doj, kde cesta prochází pouze vrcholy z {1,2,..., /c}. • výpočet vychází ze vztahu Uk(iJ) = min{ufc_i(/J), í/fc-i(/, /c) + t/fe_i(/c,j)}. • je efektivnější než „upravená mocnina" Aq (násobení —> sčítání, sčítání —> minimum) -ta je totiž 0(n4), resp. (optimalizovaná) 0(n3 log n).