4-dfs/4-dfs.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{4}{Aplikace DFS}{}
   4
   5 \h{Opakování DFS}
   6
   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:
   9
  10 \itemize\ibull
  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é,
  13 dopøedné a pøíèné.}
  14 \endlist
  15
  16 Pokud není celý graf dosa¾itelný z~$v_0$, èasto se nám hodí volat
  17 DFS opakovanì, dokud existují nedosa¾itelné vrcholy:
  18
  19 \algo
  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$.
  23 \endalgo
  24
  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ù.)
  28
  29 \h{Detekce cyklù v orientovaném grafu}
  30
  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).
  34
  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.
  37
  38 \proof
  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.
  41
  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ì.
  45 \qed
  46
  47 %\s{Algoritmus:}
  48 %\algo
  49 %\algin Graf $G$
  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í.
  53 %\:jinak
  54 %\::Graf je acyklický.
  55 %\endalgo
  56
  57 \s{Èasová i pamì»ová slo¾itost} je $\O(m+n)$, nebo» se jedná o triviálnì upravené DFS.
  58
  59 \h{Topologické uspoøádání DAGu (grafu bez orientovaných cyklù)}
  60
  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$.
  64
  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)$.
  67
  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.
  72
  73 \h{Nejdel¹í cesta v ohodnoceném DAGu}
  74
  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
  77 z~$u$ do~$v$.
  78
  79 \s{Algoritmus:}
  80
  81 \algo
  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$.
  85 \::Jinak:
  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ì
  88 je rovno $-\infty$.)
  89 \endalgo
  90
  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$.
  93
  94 \s{Èasová slo¾itost:} Topologické uspoøádání trvá $\Theta(n+m)$,
  95 projití grafu s~výpoètem vzdáleností takté¾.
  96
  97 \s{TODO:} Kritické hrany.
  98
  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.
 101 %
 102 %\s{Pozorování:} Hrana $(x,y)$ je kritická právì tehdy, kdy¾ $D(u,x) + e(x,y) = D(u,y)$.
 103 %
 104 %\s{Algoritmus:}
 105 %\algo
 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.
 110 %\endalgo
 111 %\s{Èasová a pamì»ová slo¾itost:} $\O(n+m)$
 112
 113 \h{Hledání mostù v neorientovaném grafu}
 114
 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.
 117
 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.
 120
 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
 125 \uv{zleva doprava}.)
 126
 127 \s{Pozorování:} Ka¾dý most je stromová hrana. Zpìtné hrany toti¾ le¾í
 128 na cyklech.
 129
 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.
 134
 135 \s{Definice:} $\<low>(v) = \min\{ \<in>(w) \mid \hbox{z~$T_v$ vede zpìtná
 136 hrana do~$w$} \}$.
 137
 138 \s{Dùsledek:} Stromová hrana~$uv$ je most právì tehdy, kdy¾ $\<low>(v) > \<in>(u)$.
 139
 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
 143 nezpomalíme.
 144
 145 \h{Komponenty silné souvislosti}
 146
 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$.
 149
 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$.
 153
 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$.
 157
 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.)
 160
 161 \s{Lemma:} Graf komponent ${\cal C}(G)$ ka¾dého grafu~$G$ je acyklický.
 162
 163 \proof
 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$.
 168
 169 V¹echny komponenty $C_i$ jsou silnì souvislé, tedy existuje cesta z~$y_{i-1}$
 170 do~$x_i$ v~$C_i$.
 171
 172 Slepením tìchto hran a cest vznikne cyklus v~grafu~$G$ tvaru
 173 $$
 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.
 176 $$
 177 To je ov¹em spor s~tím, ¾e vrcholy~$x_i$ le¾í v~rùzných komponentách.
 178 \qed
 179
 180 \s{Definice:} Buï~$G^R$ graf, který vznikne z~$G$ otoèením orientace v¹ech hran.
 181
 182 \s{Pozorování:} $G^R$ má tyté¾ komponenty jako~$G$. Navíc ${\cal C}(G^R) = ({\cal C}(G))^R$.
 183
 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.
 186
 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.
 189
 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
 192 z~jiných komponent.)
 193
 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$.
 196
 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í:
 201
 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).$$
 203
 204 \proof
 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í.
 206
 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í.
 208 \qed
 209
 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
 213
 214 \goodbreak
 215 \s{Algoritmus:}
 216 \algo
 217 \algin Graf $G$
 218 \:Sestrojíme $G^R$
 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)$.
 225 \endalgo
 226
 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)$.
 230
 231 \bye