Proch´ azen´ı graf˚ u
Aplikace
TGH04 - proch´azky po grafech Jan Bˇrezina Technical University of Liberec
24. bˇrezna 2015
Proch´ azen´ı graf˚ u
Aplikace
Theseus v labyrintu
• Theseus chce v labyrintu naj´ıt M´ınotaura. K dispozici m´ a Ariadninu
nit a kˇr´ıdu. Jak m´a postupovat?
Proch´ azen´ı graf˚ u
Aplikace
Theseus v labyrintu
• Theseus chce v labyrintu naj´ıt M´ınotaura. K dispozici m´ a Ariadninu
nit a kˇr´ıdu. Jak m´a postupovat? • Odv´ıjen´ım a nav´ıjen´ım niti si pamatuje cestu od vchodu.
Proch´ azen´ı graf˚ u
Aplikace
Theseus v labyrintu
• Theseus chce v labyrintu naj´ıt M´ınotaura. K dispozici m´ a Ariadninu
nit a kˇr´ıdu. Jak m´a postupovat? • Odv´ıjen´ım a nav´ıjen´ım niti si pamatuje cestu od vchodu. • Aby proˇsel vˇsechny chodby bludiˇstˇ e, dˇel´a kˇr´ıˇzky tam kde uˇz byl.
Proch´ azen´ı graf˚ u
Aplikace
Theseus v grafu
• Labyrint je obyˇ cejn´y neorientovan´y souvisl´y graf. • Nit je z´ asobn´ık vrchol˚ u. • Pˇr´ıchod do vrcholu - je tam nit. • Odchod z vrcholu - kˇr´ıˇ zek.
Proch´ azen´ı graf˚ u
Aplikace
Proch´azen´ı do hloubky - rekurzivn´ı
DFS - deep first search Pr˚ uchod vrcholu: 1. oznaˇc´ım vrchol za navˇst´ıven´y 2. pro vˇsechny hrany vedouc´ı do nenevˇst´ıven´eho sousedn´ıho vrcholu projdu sousedn´ı vrchol 3. oznaˇc´ım vrchol za uzavˇren´y
Proch´ azen´ı graf˚ u
Aplikace
Proch´azen´ı do hloubky - zad´an´ı
Vstup algoritmu: (orientovan´y) graf G dan´y vrcholy V a seznamem soused˚ u Adj[v] kaˇzd´eho vrcholu v. V´ystup: • d[v] - “ˇ cas” previzity, prvn´ıho navˇst´ıven´ı vrcholu, zˇsedivˇen´ı • f [v] - “ˇ cas” postvizity, opuˇstˇen´ı vrcholu, zˇcern´an´ı • π[v] - pˇredci ve lese pr˚ uchodu Gπ
Proch´ azen´ı graf˚ u
Aplikace
Proch´azen´ı do hloubky - algoritmus 1 2 3 4 5 6 7 8 9
for u ∈ V do color[u] = W hite, π[u] = N U LL time = 1 for u ∈ V do if color[u] == W hite then DFSVisit (u) procedure DFSVisit (u) color[u] = Gray, d[u] = time++ for v ∈ Adj[u] do if color[v] == W hite then π[v] = u DFSVisit (v)
// previsit
10 11
color[u] = Black, f [u] = time++
// postvisit
Barvy jsou pouze didaktick´e, potˇreba je pouze odliˇsen´ı b´ıl´ych vrcholu a ty lze poznat vhodnou inicializac´ı π[v], nebo d[v].
Proch´ azen´ı graf˚ u
Aplikace
Proch´azen´ı do hloubky - anal´yza
Koneˇcnost a korektnost • Kaˇ zdou hranu projdeme pr´avˇe jednou (ˇr´adek 6). Proˇc? • Kaˇ zd´y vrchol provede pr´avˇe jednou previzit a jednou postvizit. • Zobrazen´ı π d´ av´a les obsahuj´ıc´ı vˇsechny vrcholy.
Sloˇzitost: • ˇr´ adky 1–3 O(V ) • DFS-Visit volan´ a pro kaˇzd´y vrchol jednou • cyklus 6– 8 pr´ avˇe jednou pro kaˇzdou hranu
dohromady: O(V + E)
Proch´ azen´ı graf˚ u
Aplikace
Z´avorkovac´ı vˇeta Theorem Pro libovoln´e dva vrcholy u a v jsou jajich itervaly otevˇrenosti (d[u], f [u]) a (d[v], f [v]) bud’ disjunktn´ı, nebo do sebe vnoˇren´e, t.j. pokud d[u] < d[v] pak plat´ı bud’ d[u] < d[v] < f [v] < f [u]
vnoˇren´e
nebo d[u] < f [u] < d[v] < f [v]
disjunktn´ı.
Nem˚ uˇze tedy nastat situace d[u] < d[v] < f [u] < f [v].
Proch´ azen´ı graf˚ u
Aplikace
D˚ ukaz
• Pˇredpokl´ ad´ame d[u] < d[v] • pokud d[v] < f [u]: vrchol u je ˇsed´ y pˇri otevˇren´ı v a z˚ ustane ˇsed´y do
uzavˇren´ı v, tj. f [v] < f [u] m´ame tedy vnoˇren´e intervaly jelikoˇz d[v] < f [v]. • pokud d[v] > f [u]: vrchol u je ˇ cern´y pˇri otevˇren´ı v a tedy
f [v] > d[v], tedy disjunktn´ı intervaly.
Proch´ azen´ı graf˚ u
Aplikace
Pˇr´ıklad
Proch´ azen´ı graf˚ u
Aplikace
Klasifikace hran Pro orientovan´y graf je hrana (u, v): stromov´a kdyˇz je souˇc´ast´ı vznikl´eho lesa, pˇriˇsli jsme po n´ı do b´ıl´eho vrcholu v zpˇetn´a pokud v je pˇredkem u v lese Gπ pˇriˇsli jsme po n´ı do ˇsediv´eho vrcholu v dopˇredn´a pokud v je potomkem u v Gπ , ale ne bezprostˇredn´ım; nen´ı stromov´a pˇriˇsli jsme po n´ı do ˇcern´eho vrcholu a plat´ı d[u] < d[v]; vnoˇren´e z´avorky d[u] < d[v] < f [v] < f [u] kˇr´ıˇzov´a vˇsechny ostatn´ı hrany pˇriˇsli jsme po n´ı do ˇcern´eho vrcholu a plat´ı d[u] > d[v]; disjunktn´ı z´avorky d[v] < f [v] < d[u] < f [u] Pro neorientovan´y . . . prvn´ı typ kter´y najdeme, tj nejsou kˇr´ıˇzov´e a dopˇredn´e.
Proch´ azen´ı graf˚ u
Aplikace
Pˇr´ıklad
Proch´ azen´ı graf˚ u
Aplikace
CPM - critical path method Motivaˇcn´ı probl´em: • dosaˇ zen´ı sloˇzit´eho c´ıle
(postavit d˚ um, oblekan´ı dvoulet´e dcerky, naps´an´ı bakal´aˇrsk´e pr´ace) • rozdˇ elen´ı na mnoho d´ılˇc´ıch ˇcinnost´ı (vrcholy) • urˇ cen´ı minim´aln´ıho ˇcasu pro jejich splnˇen´ı (ohodnocen´ı vrchol˚ u w[v]) • urˇ cen´ı jejich z´avislost´ı (orientovan´e hrany),
hrana vede z ˇcinnosti u do ˇcinnosti v, pokud v z´avis´ı na u ´ Uloha: Jsou d´any ˇcinnosti jejich doby a z´avislosti. Urˇci minim´aln´ı ˇcas potˇrebn´y k proveden´ı vˇsech ˇcinnost´ı. Pro kaˇzdou ˇcinnost uˇci, kdy nejdˇr´ıve m˚ uˇze skonˇcit a kdy nejpozdˇeji mus´ı skonˇcit, aby z˚ ustal zachov´an celkov´y minim´aln´ı ˇcas. Najdi ˇcinnosti, pro kter´e je rozd´ıl tˇechto ˇcas˚ u nulov´y. Tyto tvoˇr´ı kritickou cestu.
Proch´ azen´ı graf˚ u
Aplikace
Gantt chart
• ˇ cervenˇe: kritick´a cesta • modˇre: nekritick´ e ˇcinnosti • ˇ cernˇe: intervaly mezi minim´aln´ım a mxim´aln´ı ˇcasem dokonˇcen´ı
Proch´ azen´ı graf˚ u
Aplikace
Grafov´a formulace
Orientovan´y acyklick´y graf (DAG) je orientovan´y graf neobsahuj´ıc´ı cykly. Obsahuje alespoˇ n jeden (startovn´ı) uzel bez vstupn´ı hrany a alespoˇ n ´ jeden (c´ılov´y) uzel bez v´ystupn´ı hrany. BUNO jeden startovn´ı a jeden c´ılov´y (spojen´ı startovn´ıch/c´ılov´ych uzlu do jednoho) Grafov´a u ´loha: Pro dan´y orientovan´y acyklick´y graf G(V, E) s ohodnocen´ymi vrcholy w(v) najdi nejmenˇs´ı ˇc´ıslo T tak, aby d´elka kaˇzd´e cesty (souˇcet jej´ıch vrchol˚ u) ze startovn´ıho do c´ılov´eho uzlu byla menˇs´ı neˇz T . Najdi cestu jej´ıˇz d´elka je rovna T .
Proch´ azen´ı graf˚ u
Aplikace
Topologick´e tˇr´ıdˇen´ı - algoritmus Jednoduˇsˇs´ı varianta CPM: Pro orientovan´y graf zjisti jestli je to DAG a setˇrid’ vrcholy tak, aby hrana vˇzdy ˇsla z vrcholu s niˇzˇs´ım ˇc´ıslem do vrcholu s vyˇsˇs´ım ˇc´ıslem. 1. DFS , urˇci f [u] pro vˇsechny vrcholy 2. ukonˇcen´e vrcholy pˇrid´avej na zaˇc´atek seznamu (seznam vrchol˚ u setˇr´ıdˇen´y sestupnˇe podle f [u]) implementace: • nepotˇrebujeme π[] ani f [], d[] pouze kv˚ uli barven´ı • pˇri postvizitˇ e vrcholu u:
order.push_front(u) nebo efektivnˇeji: back_order.push_back(u)
Proch´ azen´ı graf˚ u
Aplikace
Topologick´e tˇr´ıdˇen´ı - d˚ ukaz spr´avnosti
Lemma Graf je DAG pr´avˇe tehdy, pokud DFS nenajde ˇz´adnou zpˇetnou hranu.
Theorem Pro kaˇzdou hranu (u, v) plat´ı f [u] > f [v], t.j. v´ysledn´y seznam bude dobˇre setˇr´ıdˇen´y. D˚ ukaz podle druhu hrany proch´azen´e hrany (u, v), u ˇsed´y: stromov´a a dopˇredn´a - (v b´ıl´y) v je potomkem u, t.j. f [u] > f [v] zpˇetn´a - nem˚ uˇze nastat (lemma) kˇr´ıˇzov´a - disjunktn´ı z´avorky d[v] < f [v] < d[u] < f [u]
Proch´ azen´ı graf˚ u
Aplikace
CPM - algoritmus 1. Proved’ topologick´e setˇr´ıdˇen´ı bez ohledu na ohodnocen´ı. 2. Nastav tstart [:] = 0, minim´aln´ı ˇcasy zaˇc´atk˚ u ˇcinnost´ı. 3. Proch´azej v´ysledn´y seznam dopˇredu a pro kaˇzd´y vrchol u a jeho hranu (u, v) proved’ tstart [v] = max(tstart [v], tstart [u] + w[u]), (maximum z d´elek cest kter´e vedou do v). Pro c´ılov´y vrchol vend dost´av´ame tstart (vend ) = T = tend (vend ).
Proch´ azen´ı graf˚ u
Aplikace
CPM - algoritmus 1. Proved’ topologick´e setˇr´ıdˇen´ı bez ohledu na ohodnocen´ı. 2. Nastav tstart [:] = 0, minim´aln´ı ˇcasy zaˇc´atk˚ u ˇcinnost´ı. 3. Proch´azej v´ysledn´y seznam dopˇredu a pro kaˇzd´y vrchol u a jeho hranu (u, v) proved’ tstart [v] = max(tstart [v], tstart [u] + w[u]), (maximum z d´elek cest kter´e vedou do v). Pro c´ılov´y vrchol vend dost´av´ame tstart (vend ) = T = tend (vend ). 4. Nastav tend [:] = T , maxim´aln´ı ˇcasy ukonˇcen´ı ˇcinnost´ı. 5. Proch´azej seznam pozp´atku a poˇc´ıtej pro kaˇzd´y vrchol u a jeho hranu (u, v) tend [u] = min(tend [u], tend (v) − w(u)), (kdy nejpozdˇeji mus´ım skonˇcit, abych neposunul n´asleduj´ıc´ı ˇcinnosti) 6. Pr˚ ubˇeˇznˇe zaznamenej kritickou cestu tvoˇrenou vrcholy, pro kter´e tend (v) − tstart (v) = w(v).
Proch´ azen´ı graf˚ u
Silnˇe souvisl´e komponenty orientovan´eho grafu
silnˇe souvisl´a komponenta je maxim´aln´ı mnoˇzina vrchol˚ u, kde pro kaˇzdou uspoˇr´adanou dvojici (u, v) existuje cesta kontrakce hrany Splynut´ı jej´ıch vrchol˚ u v grafu. Necht’ W ⊂ VG a indukovan´y podgraf G[W ] je souvisl´y, pak kontrakce mnoˇziny W , je graf G.W kter´y vznikne kontrakc´ı vˇsech hran v G[W ]. metagraf orientovan´eho grafu vznikne kontrakc´ı jeho SSK
Aplikace
Proch´ azen´ı graf˚ u
Aplikace
Pˇr´ıklad
Proch´ azen´ı graf˚ u
Aplikace
Hled´an´ı SSK
Algoritmus (Kosaraj˚ uv algortimus) pro hled´an´ı SSK pomoc´ı DFS: 1. DFS(G) urˇci ˇcasy postvisit f [u] 2. sestav transponovan´y graf GT (opaˇcnˇe orientovan´y) 3. DFS(GT ) hlavn´ı cyklus sestupnˇe podle hodnot f [u] 4. kaˇzd´y strom opov´ıd´a jedn´e komponentˇe Alterantivn´ı m´ırnˇe rychlejˇs´ı jednopruchodov´y, ale sloˇzitˇejˇs´ı : Tarjan˚ uv algoritmus
Proch´ azen´ı graf˚ u
Aplikace
spr´avnost algoritmu
Znaˇcen´ı: d(C) = min{d[u], u ∈ C}, f (C) = max{f [u], u ∈ C}
Lemma (kl´ıˇcov´e) Necht’ C a C 0 jsou SSK a existuje hrana z C do C 0 , pak f (C) > f (C 0 ). (nejvˇetˇs´ı ˇcasy postvisit jejich uzl˚ u v prvn´ım DFS) D˚ ukaz: Neˇz opust´ım C nutnˇe mus´ım proj´ıt C 0 . V druh´em DFS zaˇc´ın´am na komponentˇe s max. f (C), tj. na GT z n´ı nevede hrana po jej´ım pr˚ uchodu jdu do hlavn´ıho cyklu
Proch´ azen´ı graf˚ u
Aplikace
Eulerova cesta
u ´loha: Pro neorientovan´y graf zjistit, zda se d´a nakreslit jedn´ım uzavˇren´ym tahem a naj´ıt takov´y tah.
Lemma V neorientovan´em grafu G existuje uzavˇren´y sled obsahuj´ıc´ı kaˇzdou hranu pr´avˇe jednou pr´avˇe tehdy, kdyˇz stupnˇe vˇsech vrchol˚ u jsou sud´e: ∀v ∈ V : deg(v) = 2n
Proch´ azen´ı graf˚ u
Aplikace
algoritmus
1. Z vrcholu v proch´azej graf (jako do hloubky, ale bez n´avrat˚ u) dokud se nevr´at´ıˇs do v, oznaˇcuj pouˇzit´e hrany. 2. Najdi ve v´ysledn´em sledu vrchol v s neprojitou hranou. Pokud takov´y neexistuje skonˇci. 3. Proved’ bod 1) a vloˇz nov´y sled do v´ysledn´eho sledu na m´ısto vrcholu v. 4. Pokraˇcuj na 2) Pokud se pro ukl´ad´an´ı sledu pouˇzije spojov´y seznam, m´a algoritmus sloˇzitost O(V + E).
Proch´ azen´ı graf˚ u
Aplikace
detaily
Proch´ azen´ı graf˚ u
Aplikace
Proch´azen´ı do ˇs´ıˇrky I Vstup: graf G dan´y vrcholy V a sousednostmi Adj[i], poˇc´ateˇcn´ı vrchol s V´ystup: vzd´alenosti d[i] od s, pˇredci π[i] pr˚ uchodov´eho stromu 1 2 3 4 5 6 7 8 9
for u ∈ V do Color[u] = W hite Color[s] = Gray; d[s] = 0; π[s] = N U LL ClearQueue ; EnQueue(s) while u =DeQueue do for v ∈ Adj[u] do if Color[v] == W hite then Color[v] = Gray; d[v] = d[u] + 1; π[v] = u EnQueue(v) Color[u] = Black
Proch´ azen´ı graf˚ u
Aplikace
Proch´azen´ı do ˇs´ıˇrky II • Breadth First Search (BFS) • pro orientovan´ e i neorientovan´e grafy • vygeneruje koˇrenov´ y strom vrchol˚ u dosaˇziteln´ych z s (stejn´a
komponenta) • ˇ cas: |V | ∗ (vloˇzen´ı a vybr´an´ı z fronty)+kaˇzd´a hrana= Θ(|V | + |E|) • pamˇ et’: reprezentace grafu |V | + |E| • d[v] je d´ elka nejkratˇs´ı cesty z s do v • kostra souvisl´ eho grafu je jeho maxim´aln´ı indukovan´y podstrom • . . . zde strom dan´ y pˇredky π[v] • Vnˇ ejˇs´ı inicializac´ı a cyklem pˇres vˇsechny b´ıl´e vrcholy ⇒ detekov´an´ı
komponent
Proch´ azen´ı graf˚ u
Aplikace
Pˇr´ıˇstˇe
• tˇr´ıdˇ en´ı, pokroˇcil´e datov´e struktury • ˇ casov´a a pamˇet’ov´a sloˇzitost
