3 \prednaska{4}{Aplikace DFS}{}
7 DFS spu¹tìné z~vrcholu~$v_0$ v~èase $\Theta(n+m)$ nalezne podgraf
8 dosa¾itelný z~$v_0$ a pro nìj spoète:
11 \:Èasy pøíchodu $\<in>(v)$ a odchodu $\<out>(v)$ pro v¹echny vrcholy~$v$.
12 \:Klasifikaci v¹ech hran, tedy jejich rozdìlení na {\I stromové, zpìtné,
16 Pokud není celý graf dosa¾itelný z~$v_0$, èasto se nám hodí volat
17 DFS opakovanì, dokud existují nedosa¾itelné vrcholy:
20 \:Pro v¹echny vrcholy~$v$:
21 \::Pokud $v$ je¹tì není oznaèen jako nav¹tívený:
22 \:::Spustíme DFS z~vrcholu~$v$.
25 V¹imnìte si, ¾e tento algoritmus stále pracuje v~èase $\Theta(n+m)$.
26 (Mimochodem, stejného výsledku bychom dosáhli, pokud bychom do grafu
27 pøidali nìjaký nový vrchol a hrany z~nìj do v¹ech ostatních vrcholù.)
29 \h{Detekce cyklù v orientovaném grafu}
31 Mìjme orientovaný graf~$G$. Chceme zjistit, zda se v~nìm nachází orientovaný
32 cyklus (alespoò jeden; najít v¹echny je mnohem obtí¾nìj¹í, mimo jiné proto,
33 ¾e jich mù¾e být exponenciálnì mnoho).
35 \s{Lemma:} Cyklus je v grafu $G$ právì tehdy, kdy¾ DFS provedené na celý
36 graf oznaèí nìjakou hranu jako zpìtnou.
39 Pokud existuje zpìtná hrana z~$u$ do~$v$, pak spolu s~cestou po stromových
40 hranách z~$v$ do~$u$ tvoøí cyklus.
42 A~naopak: mìjme nìjaký cyklus a buï $v$ jeho vrchol s~nejni¾¹ím $\<out>(v)$.
43 Tím pádem na hranì vedoucí z~$v$ do následujícího vrcholu na cyklu roste \<out>,
44 co¾ je ov¹em mo¾né pouze na zpìtné hranì.
50 %\:Spustíme $\<DFS>(G)$ a pøi nalezení první zpìtné hrany $(u,v)$ zastavíme.
51 %\:Pokud jsme nalezli zpìtnou hranu:
52 %\::Vypí¹eme v¹echny vrcholy mezi $(u,v)$ ze zásobníku onoho DFS v opaèném poøadí.
54 %\::Graf je acyklický.
57 \s{Èasová i pamì»ová slo¾itost} je $\O(m+n)$, nebo» se jedná o triviálnì upravené DFS.
59 \h{Topologické uspoøádání DAGu (grafu bez orientovaných cyklù)}
61 \s{Definice:} {\it Topologické uspoøádání} acyklického orientovaného grafu
62 je lineární uspoøádání~$\prec$ na~vrcholech grafu takové, ¾e kdykoliv je $uv$
63 hrana, pak $u\prec v$.
65 \s{Jiný pohled:} Je to prosté oèíslování $f: V(G) \rightarrow {\bb N}$
66 takové, ¾e pro jakoukoliv hranu $uv\in E(G)$ platí $f(u) < f(v)$.
68 \s{Pozorování:} Jak u¾ víme, spustíme-li DFS na acyklický graf, nenajde ¾ádnou
69 zpìtnou hranu. Na v¹ech ostatních typech hran \<out> klesá, tak¾e obrácené poøadí
70 \<out>ù je topologické.
71 Z~toho plyne, ¾e v~èase $\Theta(n+m)$ lze topologicky uspoøádat libovolný DAG.
73 \h{Nejdel¹í cesta v ohodnoceném DAGu}
75 Mìjme DAG~$G$, ohodnocení jeho hran $\ell: E(G) \rightarrow {\bo R}$
76 a nìjaký vrchol~$u$. Pro ka¾dý vrchol~$v$ chceme spoèítat $D(v)$ -- délku nejdel¹í cesty
82 \:Zvolíme topologické uspoøádání $w_1 \dots w_n$ na $G$.
83 \:Pro $v=w_1,\ldots,w_n$ postupnì provádíme:
84 \::Pokud $v=u$, pak $D(u) \= 0$.
86 $$D(v)\=\max_{w: wv \in E} (D(w) + \ell(wv)).$$
87 (Pozor, mù¾e to být maximum z~prázdné mno¾iny, v~takovém pøípadì
91 \s{Pozorování:} V¹imnìte si, ¾e koneèné~$D(v)$ vyjde právì tìm vrcholùm~$v$,
92 které jsou dosa¾itelné z~$u$.
94 \s{Èasová slo¾itost:} Topologické uspoøádání trvá $\Theta(n+m)$,
95 projití grafu s~výpoètem vzdáleností takté¾.
97 \s{TODO:} Kritické hrany.
99 %\h{Hledání kritických hran v ohodnoceném DAG-u}
100 %\s{Definice:} Hrana je kritická právì tehdy, kdy¾ le¾í na nìkteré z nejdel¹ích cest.
102 %\s{Pozorování:} Hrana $(x,y)$ je kritická právì tehdy, kdy¾ $D(u,x) + e(x,y) = D(u,y)$.
106 %\algin Graf $G$, v nìm vrchol $u$.
107 %\:Nalezneme v grafu $G$ nejdel¹í cesty z $u$ pøedchozím algoritmem
108 %\:Vybereme ty hrany, které splòují rovnost $D(u,x) + e(x,y) = D(u,y)$ -- kritické
109 %\algout Seznam kritických hran.
111 %\s{Èasová a pamì»ová slo¾itost:} $\O(n+m)$
113 \h{Hledání mostù v neorientovaném grafu}
115 \s{Definice:} Hrana $uv \in E(G)$ je {\I most,} pokud se jejím odebráním
116 z~grafu~$G$ zvý¹í poèet komponent souvislosti tohoto grafu.
118 \s{Pozorování:} Hrana, která je souèástí nìjakého cyklu, nemù¾e být mostem.
119 A~naopak, pokud nìjaká hrana není mostem, pak le¾í na nìjakém cyklu.
121 \s{DFS klasifikace} pro neorientované grafy: Ka¾dou hranu potkáme v~obou
122 smìrech. Poprvé jí mù¾eme potkat jako stromovou, resp. zpìtnou. Podruhé
123 pak jako zpìtnou, resp. dopøednou. Pøíèné hrany se neobjeví (opaèné k~nim
124 by toti¾ také musely být pøíèné, ale jak víme, pøíèné hrany nikdy nevedou
127 \s{Pozorování:} Ka¾dý most je stromová hrana. Zpìtné hrany toti¾ le¾í
130 Mìjme tedy nìjakou stromovou hranu~$uv$. Mostem není tehdy, vede-li v~grafu
131 $G-uv$ cesta z~$v$ do~$u$. Tato cesta musí nìkudy opustit podstrom strom~$T_v$
132 (to je podstrom obsahující v¹e pod vrcholem~$v$) a mù¾e tak uèinit pouze
133 zpìtnou hranou, které vede do~$u$ nebo kamkoliv blí¾e ke~koøeni.
135 \s{Definice:} $\<low>(v) = \min\{ \<in>(w) \mid \hbox{z~$T_v$ vede zpìtná
138 \s{Dùsledek:} Stromová hrana~$uv$ je most právì tehdy, kdy¾ $\<low>(v) > \<in>(u)$.
140 Staèí domyslet, ¾e bìhem DFS mù¾eme snadno spoèítat \<low> pro v¹echny vrcholy.
141 Kdykoliv opou¹tíme vrchol~$v$, polo¾íme $\<low>(v)$ rovnu minimu z~\<low> jeho
142 synù a \<in> vrcholù, do nich¾ z~$v$ vede zpìtná hrana. Tím DFS asymptoticky
145 \h{Komponenty silné souvislosti}
147 \s{Definice:} Buï $T$ bude relace na $V(G)$ definovaná tak, ¾e $uTv$ právì tehdy,
148 existuje-li orientovaná cesta v~$G$ z~$u$ do~$v$ a souèasnì z~$v$ do~$u$.
150 \s{Pozorování:} $T$ je ekvivalence. Tøídám této ekvivalence se øíká {\I komponenty
151 silné souvislosti} (v~tomto oddílu øíkejme prostì {\I komponenty}). Graf je {\I silnì
152 souvislý,} pokud má právì jednu komponentu, tedy pokud $uTv$ pro ka¾dé dva vrcholu $u,v$.
154 \s{Definice:} {\I Graf komponent} ${\cal C}(G)$ je graf, jeho¾ vrcholy jsou
155 komponenty grafu~$G$ a z~komponenty $C_i$ vede hrana do~$C_j$ právì tehdy,
156 kdy¾ v~pùvodním grafu~$G$ existuje hrana z~nìjakého vrcholu $u\in C_i$ do nìjakého $v\in C_j$.
158 Jiný pohled: ${\cal C}(G)$ je graf, který z~$G$ vznikne kontrakcí ka¾dé komponenty
159 do~jednoho vrcholu. (Násobné hrany pøi kontrakcích odstraòujeme.)
161 \s{Lemma:} Graf komponent ${\cal C}(G)$ ka¾dého grafu~$G$ je acyklický.
164 Sporem: Nech» $C_1, C_2, \dots C_k$ tvoøí cyklus v~${\cal C}(G)$. Podle definice grafu
165 komponent tedy musí existovat vrcholy $x_1, \ldots, x_k$ ($x_i \in C_i$)
166 a $y_1, \ldots, y_k$ ($y_i \in C_{i+1}$, indexujeme modulo~$k$) takové,
167 ¾e $x_i y_i$ jsou hrany grafu~$G$.
169 V¹echny komponenty $C_i$ jsou silnì souvislé, tedy existuje cesta z~$y_{i-1}$
172 Slepením tìchto hran a cest vznikne cyklus v~grafu~$G$ tvaru
174 x_1, y_1, \hbox{cesta v~$C_2$}, x_2, y_2, \hbox{cesta v~$C_3$}, x_3, \ldots,
175 x_k, y_k, \hbox{cesta v~$C_1$}, x_1.
177 To je ov¹em spor s~tím, ¾e vrcholy~$x_i$ le¾í v~rùzných komponentách.
180 \s{Definice:} Buï~$G^R$ graf, který vznikne z~$G$ otoèením orientace v¹ech hran.
182 \s{Pozorování:} $G^R$ má tyté¾ komponenty jako~$G$. Navíc ${\cal C}(G^R) = ({\cal C}(G))^R$.
184 \s{Definice:} {\I Zdroj} øíkáme vrcholu, do~nìj¾ nevedou ¾ádné hrany. Symetricky
185 {\I stok} je vrchol, z~nìj¾ nevedou hrany.
187 \s{Pozorování:} Ka¾dý DAG má alespoò jeden zdroj a alespoò jeden stok.
188 Zdroje v~$G$ jsou stoky v~$G^R$ a naopak.
190 \s{Definice:} {\it Zdrojová komponenta} grafu $G$ je taková komponenta,
191 která tvoøí zdroj v $C(G)$. (Jinými slovy, ani v~$G$ do ní nevedou ¾ádné hrany
194 \s{Trik:} Nech»~$C$ je nìjaká zdrojová komponenta a~$v$ libovolný její vrchol.
195 Potom DFS spu¹tìné v~$G^R$ z~vrcholu~$v$ oznaèí právì vrcholy komponenty~$C$.
197 \s{Plán:} Najdeme vrchol s~maximálním $\<out>(v)$. Ten urèitì le¾í ve~zdrojové
198 komponentì (rozmyslete si). Spustíme z~nìj DFS v~$G^R$, tím oznaèíme jednu
199 komponentu. Odtrhneme ji a postup opakujeme. Dokonce nemusíme pøepoèítávat
200 \<out>y. Staèí toti¾ pou¾ít následujicí:
202 \s{Tvrzeníèko:} Pokud $(C_1, C_2) \in E({\cal C}(G))$, pak $$\max_{x \in C_1} \<out>(x) > \max_{x \in C_2} \<out>(x).$$
205 Buïto DFS vstoupí nejdøíve do $C_1$ -- nìkdy odtamtud dojde do $C_2$ a zase se nìkdy vrátí, rozhodnì ale døíve ne¾ z $C_1$. Pro tento pøípad tvrzeníèko platí.
207 Nebo vstoupí nejdøíve do $C_2$. Odtud nemù¾e nikdy dojít do $C_1$. Vrátí se tedy rozhodnì døíve z celé $C_2$, ne¾ kdy vùbec vstoupí do $C_1$, tedy pro tento pøípad také tvrzeníèko platí.
210 Staèí tedy vybrat vrchol s~nejvìt¹ím \<out>, spustit z~nìj DFS v~$G^R$,
211 èím¾ oznaèíme první komponentu. Pak vybereme vrchol s~nejvìt¹ím \<out>
212 z~tìch, které je¹tì nebyly oznaèeny, a~pokraèujeme\dots
219 \:$Z \=$ prázdný zásobník, $\<komp>(*) \=$ ?
220 \:Spustíme $\<DFS>(G)$, pøi opu¹tení vrcholu jej vlo¾íme do $Z$. Máme tedy vrcholy v zásobníku setøídìné podle $\<out>(v)$.
221 \:Postupnì pro $v \in Z$:
222 \::Pokud $\<komp>(v)=~?$
223 \:::pustíme $\<DFS>(v)$ v $G^R$ s omezením jen na vrcholy $w$, pro které $\<komp>(w) =~?$, v¹em nav¹tíveným vrcholùm $w$ nastavíme $\<komp>(w) \= v$.
224 \algout Pro ka¾dý vrchol $v$ vrátíme jeho komponentu $\<komp>(v)$.
227 \s{Èasová a pamì»ová slo¾itost} bude $\Theta(m+n)$, nebo» první DFS má $\Theta(m+n)$,
228 ka¾dé dal¹í DFS se omezí jen na svoji komponentu a souèet
229 velikostí v¹ech komponent je $\Theta(m+n)$.