Průzkum grafů a grafová souvislost □ Průzkum grafů a grafová souvislost ■ Průzkum do šíTky ■ Průzkum do hloubky ■ Topologické uspořádání ■ Silně souvislé komponenty o 2. května 2016 1/80 Průzkum grafů a grafová souvislost Graf a jeho reprezentace ■ graf G = (V, E) • orientovaný / neorientovaný • ohodnocené hrany / vrcholy • jednoduché / násobné hrany ■ reprezentace grafů • seznam následníků • incidenční matice ■ složitost grafových algoritmů je funkcí počtu vrcholů a hran ■ používáme zjednodušenou notaci, např. 0{V + E) o 2. května 2016 2 / 80 Průzkum grafů a grafová souvislost Incidenční matice 1 2 3 4 1 0 1 1 0 2 1 0 1 0 3 1 1 0 1 4 0 0 1 0 1 2 3 4 1 0 1 1 0 2 0 0 0 0 3 0 1 0 0 4 0 0 1 0 matice A = (a^-) rozměrů \V\ x \V\, kde CL i j 1 pokud (i, j) G E 0 jinak prostorová složitost: 0(V2) vhodné pro husté grafy časová složitost výpisu všech sousedů vrcholu u je Q(V) časová složitost ověření zda (u,v) E E je 0(1) 2. května 2016 3 / Průzkum grafů a grafová souvislost Seznam následníků Adj 1 2 3 4 > 3 / > 3 / > 4 / > 3 / Adj 1 2 3 4 -> 2--> 3 / / -> 2 / 3 / ■ pole Adj velikosti \V\ ■ prostorová složitost: @(V + E) ■ vhodné pro řídké grafy ■ časová složitost výpisu všech sousedů vrcholu u je Q(deg{u)) (deg(u) je stupeň vrcholu u) ■ časová složitost ověření zda (u,v) E E je 0(deg(u)) varianta použít místo pole hašovací tabulku, zřetězené hašování nahradit otevřenou adresací 2. května 2016 4 / Průzkum grafů a grafová souvislost Srovnání incidenční matice seznam následníků hašovací tabulka test {u, v} E E o(i) 0(V) 0(i) test (u, v) E E 0(i) 0(V) 0(i) seznam sousedů vrcholu v 0(V) 0(l + deg(v)) 0{l + deg{v)) seznam hran 0(V2) 0(V + E) O (V + E) přidání hrany 0(1) 0(1) 0(1)* odstranění hrany 0(1) 0{V) 0(1)* očekávaná složitost o 2. května 2016 5 / 80 Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu Everything on earth can be found, if only you do not let yourself be put off searching. Philemon of Syracuse (ca. 360 BC-264 BC) pro daný graf G a vrchol s grafu je cílem • navštívit všechny vrcholy grafu dosažitelné z vrcholu s, resp. • navštívit všechny vrcholy grafu průzkum realizovat maximálně efektivně, tj. se složitostí 0(V + E) (vyhnout se opakovaným návštěvám ) jaké další informace o grafu zjistíme v průběhu průzkumu??? o 2. května 2016 6 / 80 Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu do šírky vs do hloubky Theseus si před bludištěm uváže jeden konec nitě na strom a vsoupí dovnitř. V prvním vrcholu (křižovatce) si vybere jednu možnou cestu / hranu a projde po ní do dalšího vrcholu. Aby Theseus neměl zmatek v tom, které hrany už prošel, tak si všechny hrany, které prochází označuje křídou - a to na obou koncích. V každém vrcholu, do kterého Theseus dorazí, provede následující: ■ Pokud na zemi najde položenou nit, tak ví, že už ve vrcholu byl a že se do něj při namotávání nitě zase vrátí. Odloží tedy další prozkoumávání tohoto vrcholu na později, provede čelem vzad a začne namotávat nit na klubko. To ho dovede zpátky do předchozího vrcholu. ■ Pokud na zemi žádnou nit nenajde, tak se vydá první možnou neprošlou hranou. Pokud by taková hrana neexistovala, tak je vrchol zcela prozkoumán. V tom případě Theseus neztrácí čas a začne namotávat nit na klubko. Tím se dostane zpátky do předchozího vrcholu. Tímto postupem prozkoumá celé bludiště a nakonec se vrátí do výchozího vrcholu.1 Jakub Černý: Základní grafové algoritmy http://kam.mff.cuni.cz/~kuba/ka BM 2. května 2016 7 / 80 0 Průzkum grafu do šírky vs do hloubky implementace křída proměnná označující jestli jsme hranu prošli klubko položená niť vyznačuje cestu z výchozího do aktuálního vrcholu, cestu si pamatujeme jako posloupnost vrcholů na této cestě. Pro uložení cesty použijeme zásobník. Odmotávání nitě odpovídá přidání vrcholu do zásobníka. Namotávání nitě při návratu zpět odpovídá odebrání vrcholu ze zásobníku. o 2. května 2016 8 /8 Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu do šírky vs do hloubky Tento průchod (prohledánígrafu) si můžeme představit tak, že se do výchozího vrcholu postaví miliarda Číňanů a všichni naráz začnou prohledávat graf. Když se cesta rozdělí, tak se rozdělí i dav řítící se hranou. Předpokládáme, že všechny hrany jsou stejně dlouhé. Graf prozkoumáváme „po vlnách''. V první vlně se všichni Číňané dostanou do vrcholů, dokterých vede z výchozího vrcholu hrana. V druhé vlně se dostanou do vrcholů, které jsou ve vzdálenosti 2 od výchozího vrcholu. Podobně v k-té vlně se všichni Číňané dostanou do vrcholů ve vzdálenosti k od výchozího vrcholu. Kvůli těmto vlnám se někdy průchodu do šířky říka algoritmus vlny. 2 implementace V počítači vlny nasimulujeme tak, že při vstupu do nového vrcholu uložíme všechny možné cesty do fronty. Frontu průběžně zpracováváme. Jakub Černý: Základní grafové algoritmy http://kam.mff.cuni.cz/~kuba/ka BM 2. května 2016 9 / 80 0 Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu do šířky a do hloubky průzkum grafu do šířky vs do hloubky se liší pouze použitím fronty a zásobníku NE o 2. května 2016 10 / 80 Průzkum do sirky - strategie cílem je prozkoumat všechny vrcholy dosažitelné z daného iniciálního vrcholu ■ postupujeme od iniciálního vrcholu s po vrstvách ■ nejdříve prozkoumáme všechny vrcholy dosažitelné z s po 1 hraně ■ pak všechny vrcholy dosažitelné po 2 hranách, po 3 hranách atd. ■ pro manipulaci s vrcholy používáme prioritní frontu Q ■ v £ Q právě když byl dosažen (objeven) ale ještě nebyl prozkoumán o 2. května 2016 Průzkum grafů a grafová souvislost Průzkum do šířky Průzkum do sirky - příklad Q: S Q: AD Q: DC Q: CBE c d Q: BE c d Q: E c d Q: 0 2. května Průzkum do sirky - atributy vrcholu v.color ■ v průběhu výpočtu je vrchol postupně objeven (je zařazen do fronty) a prozkoumán (všechny sousedící vrcholy jsou objeveny) ■ vrchol má černou barvu právě když je dosažitelný z iniciálního vrcholu a byl již prozkoumán ■ vrchol má šedivou barvu právě když je dosažitelný z iniciálního vrcholu, byl již objeven, ale nebyl ještě prozkoumán ■ vrchol má bílou barvu právě když není dosažitelný z iniciálního vrcholu anebo ještě nebyl objeven v.7t ■ vrchol, ze kterého byl v objeven v.d ■ délka (počet hran) cesty z s do v, na které byl v objeven (= délka nej kratší cesty z s do v ) o 2. května 2016 13/8 Průzkum grafů a grafová souvislost Průzkum do šířky Průzkum do sirky - implementace BFS(G,s) 1 foreach u G V \ {s} 2 do u.color white] u.d oo; u.tt Nil od 3 s.color gray] s.d 0; s.tt iVzZ 5 Enqueue(Q, s) 6 while Q ^ 0 do 7 1/ Dequeue(Q) 8 foreach i; 1 vrcholy najdi vrchol v, do kterého nevstupuje žádná hrana (kdyby takový neexistoval, tak by jsme mohli z libovolného vrcholu jít donekonečna „pozpátku'' a našli by jsme cyklus) ■ G — v je acyklický (odstranění vrcholu nemůže způsobit vznik cyklu) ■ z indukčního předpokladu G — v má topologické uspořádání ■ topologické uspořádání pro G má na prvním místě v následované uspořádáním pro G — v o 2. května 2016 40 / Průzkum grafů a grafová souvislost Topologické uspořádání Topologické uspořádání - naivní algoritmus Topological_Sort_Visit(G) 1 n <- | V 2 for i = 1 to n do 3 v <(— libovolný vrchol, do kterého nevstupuje žádná hrana S v 5 odstraň z G vrchol v a všechny jeho hrany 6 od 7 return S\l... n ■ algoritmus pro acyklický graf ■ nalezení vrcholu do kterého nevstupuje žádná hrana má složitost ??? ■ celková složitost algoritmu je ??? ■ existuje efektivnější algoritmus (ideálně s lineární složitostí)??? ■ symetricky se dá postupovat podle vrcholů z nichž nevychází žádná hrana BM 2. května 2016 41 / 80 0 Průzkum grafů a grafová souvislost Topologické uspořádání Acyklický graf - testování Lema 4 Orientovaný graf G je acyklický právě když DFS průzkum grafu neoznačí žádnou hranu jako zpětnou. Důkaz ^> zpětná hrana (u,v) spojuje vrchol u s jeho předchůdcem v v DFS stromu, tj. uzavírá cyklus <= ■ nechť v grafu existuje cyklus c, nechť v je první vrchol cyklu c navštívený při DFS průzkumu grafu a nechť (u,v) je hrana cyklu c ■ v čase v.d vrcholy cesty c tvoří bílou cestu z v do u co implikuje, že u je následníkem v v DFS stromu ■ (u,v) je zpětná hrana o 2. května 2016 42 / 80 Topologické uspořádání Topologické uspořádání - algoritmus □ aplikuj DFS na G Q když průzkum označí některou hranu jako zpětnou, tak graf nemá topologické uspořádání Q v opačném případě vypiš vrcholy v uspořádání reverse postorder, tj. podle značky ./ (finishing time) v klesajícím pořadí o 2. května 2016 Průzkum grafů a grafová souvislost Topologické uspořádání Korektnost potřebujeme dokázat, že pro libovolnou dvojici vrcholů u,v platí jestliže G obsahuje hranu (u,v), tak u.f > v. f jaké jsou barvy vrcholů u a v při průzkumu hrany (u,v)l ■ u je šedivý m v je šedivý nemůže nastat, protože (u,v) by v takovém případě byla zpětnou hranou a graf by nebyl acyklický bílý v takovém případě je (u,v) stromová hrana, v je následníkem u v DFS stromu a u.d < v.d < v.f < u.f černý v takovém případě je průzkum vrcholu v ukončený a průzkum vrcholu u ještě není ukončený a proto v.f < u.f o 2. května 2016 44 / 80 Průzkum grafů a grafová souvislost Silně souvislé komponenty Souvislost v orientovaném grafu orientovaný graf G — (V, E) ■ vrchol v je dosažitelný z vrcholu u, značíme u v, právě když v G existuje orientovaná cesta z u do v ■ Reach(u) je množina všech vrcholů dosažitelných z u ■ vrcholy u 3 v jsou silně dosažitelné (strongly connected) právě když u je dosažitelný zua současně v je dosažitelný z ^ ■ silná dosažitelnost - relace ekvivalence ■ silně souvislá komponenta grafu je třída ekvivalence relace silné dosažitelnosti, tj. maximální množina vrcholů C C V taková, že pro každé u,v G C platí u v a současně v ^ u ■ graf nazýváme silně souvislý právě když má jedinou silně souvislou komponentu problém najít všechny silně souvislé komponenty grafu o 2. května 2016 Souvislost v neorientovaném grafu ■ v neorientovaném grafu jsou pojmy dosažitelnosti a silné dosažitelnost totožné ■ pro hledání silně souvislé komponenty grafu můžeme použít BFS nebo DFS ■ jednotlivé DFS (BFS) stromy korespondují s komponentami souvislosti ■ složitost O (V + E) o 2. května 2016 46 / 80 Silně souvislé komponenty v orientovaném grafu výpočet silně souvislé komponenty obsahující daný vrchol u ■ najdi množinu Reach(u) všech vrcholů dosažitelných z u aplikací DFS_Visit(G» ■ najdi množinu Reach~ľ(u) všech vrcholů, ze kterých je dosažitelný u ■ pro výpočet Reach~ľ(u) využijeme transponovaný graf3 rev(G), na který aplikujeme DFS_Visrr(re?;(G), u) ■ silně souvislá komponenta obsahující u je průnikem Reach(u) n Reach~ľ(u) m časová složitost výpočtu je 0(V + E) 3transponovaný graf rev(G) = (V, rev(E)) je graf G s obrácenou orientací hran, rev(E) {(x,y) | (y,x) G E}_ BM 2. května 2016 47 /8 Průzkum grafů a grafová souvislost Silně souvislé komponenty Silně souvislé komponenty v orientovaném grafu výpočet všech silně souvislých komponent grafu ■ můžeme zabalit popsaný postup (podobně jako je DFS_Visit(G, u) zabalené do DFS) ■ v nejhorším případě má graf \V\ komponent souvislosti a detekce každé z nich má časovou složitost O(E) ■ celková časová složitost výpočtu je O (V • E) ■ existuje efektivnější algoritmus, optimálně s lineární časovou složitostí ??? ■ motivace: v čase 0(V + E) dokážeme rozhodnout, zda všechny silně souvislé komponenty grafu jsou jednoduché (obsahují pouze jeden vrchol) o 2. května 2016 48 / 80 Průzkum grafů a grafová souvislost Silně souvislé komponenty Komponentový graf ■ komponentový graf (aka graf silně souvislých komponent) je orientovaný graf, který vznikne kontrakcí každé silně souvislé komponenty grafu do jednoho vrcholu a kontrakcí paralelních hran do jedné hrany, značíme scc{G) ■ scc(G) je orientovaný acyklický graf ■ vrcholy scc(G) můžeme topologicky uspořádat ■ listová komponenta == list grafu scc(G) ■ kořenová komponenta == kořen grafu scc{G) ■ platí rev(scc(G)) = scc{rev(G)) o 2. května 2016 49 / 80 Průzkum grafů a grafová souvislost Silně souvislé komponenty Příklad kořenová komponenta A listové komponenty D, CF, GHIJK o 2. května 2016 50 / 80 Průzkum grafů a grafová souvislost Silně souvislé komponenty Komponentový graf ■ listová komponenta grafu = list grafu scc(G) ■ z každého vrcholu u listové komponenty C jsou dosažitelné všechny vrcholy C, tj. DFS průzkum z u navštíví všechny vrcholy z C ■ naopak, z vrcholu u není dosažitelný žádný vrchol nepatřící do C (C je listová komponenta!!), tj . DFS průzkum z u navštíví pouze všechny vrcholy z C ■ na tomto pozorování můžeme postavit algoritmus pro detekci komponent Strong_Components(G) 1 count 0 2 while G není prázdný do 3 count count + 1 4 v <(— libovolný vrchol z listové komponenty 5 C <— One_Component(í;, count) 6 odstraň z grafu G vrcholy z C a hrany vstupující do C od potřebujeme (efektivně) najít vrchol patřící listové komponentě o 2. května 2016 51 / 80 Průzkum grafů a grafová souvislost Silně souvislé komponenty Komponentový graf potřebujeme (efektivně) najít vrchol patřící listové komponentě umíme (efektivně) najít vrchol patřící kořenové komponentě Věta 5 Vrchol s nejvyšší časovou značkou ./ leží v kořenové komponentě. Důkaz tvrzení je důsledkem následujícího obecnějšího tvrzení o 2. května 2016 52 / 80 Průzkum grafů a grafová souvislost Silně souvislé komponenty Komponentový graf Věta 6 Necht Ci a C2 jsou silně souvislé komponenty takové, že z C\ vede hrana do C2. Potom největší hodnota ./ v komponentě C\ je větší než největší hodnota ./ v komponentě C2. Důkaz mohou nastat dva případy ■ v prvním případě navštíví DFS komponentu C2 jako první; pak ale DFS zůstane v komponentě C2 dokud ji celou neprozkoumá, teprve pak se dostane do d ■ v prvním případě navštíví DFS komponentu C\ jako první; nechť v je vrchol, který byl v C\ navštíven jako první; DFS opustí vrchol v, až když prozkoumá všechny vrcholy, které jsou z v dosažitelné a které dosud nebyly navštíveny; proto nejprve projde celou komponentu C2 a pad se teprve naposledy vrátí do v o 2. května 2016 53 / 80 Průzkum grafů a grafová souvislost Silně souvislé komponenty Algoritmus pro detekci silně souvislých komponent vrcholy grafu uspořádej v obráceném postorder pořadí, tj. podle značky ./ v klesajícím pořadí proveď DFS průzkum z vrcholů v daném pořadí Rao Kosaraju 1978, Micha Sharir 1981 o 2. května 2016 54 / 80 Průzkum grafů a grafová souvislost Silně souvislé komponenty Kosaraju_Sharir(G) 1 foreach U E V do v.color white od 2 foreach U E V do if u.color = white then Rev_Push_DFS(i/) fi od 3 foreach U E V do v.color white od 4 count 0 5 while S ^ 0 do £ ix S.popQ 7 if u.color = white then count count + 1 s Label_One_DFS(m, count) fi od Rev_Push_DFS(» i u.color 6/ac/c £ foreach hranu Rev(G) do 5 if v.color = white then Rev_Push_DFS(^) fi 4 S.push{u) od Label_One_DFS(^, count) i u.color 6/ac/c £ u.label count 3 foreach hranu G do 4 if v.color = white then Label_One_DFS(^, count) fi od o 2. května 2016 55 / 80