4-dfs/4-dfs.tex

   1 \input ../lecnotes.tex
   2 \let\la\leftarrow
   3
   4 \prednaska{4}{Aplikace DFS}{do pou¾itelné podoby dokopal Jan \uv{Moskyto} Matìjka}
   5
   6 \h{Detekce cyklù v orientovaném grafu}
   7
   8 Algoritmus na vypsání {\I v¹ech} cyklù v grafu si neuká¾eme, nebo» tento
   9 problém je tì¾¹í, ne¾ se zdá. Mimo jiné proto, ¾e cyklù mù¾e být a¾
  10 exponenciálnì mnoho. Zde probíráme nalezení {\I nìjakého} cyklu v orientovaném
  11 grafu.
  12
  13 \s{Definice:} $\<DFS>(G)$ znaèíme spu¹tìní DFS tak, aby pro¹el v¹echny vrcholy.
  14
  15 Realizace pøedchozí definice je jednoduchá.
  16 \algo
  17 \:Dokud existuje nenav¹tívený vrchol $v$:
  18 \::Spustíme $\<DFS>(v)$.
  19 \endalgo
  20
  21 \s{Lemma:} Cyklus je v grafu $G$ právì tehdy, kdy¾ $\<DFS>(G)$ oznaèí nìjakou
  22 hranu jako zpìtnou.
  23
  24 \proof Buï $v_1,v_2,\dots,v_k,v_1$ cyklus v grafu $G$ a $v_1$ buï BÚNO vrchol s
  25 max. $\<out>(v_i)$. Pak jistì $\<out>(v_k) < \<out>(v_1)$. Jakého typu je hrana
  26 $(v_k,v_1)$?
  27
  28 Uva¾me poøadí opou¹tìní vrcholù na rùzných typech hran $(x,y)$. Na
  29 stromové, dopøedné a pøíèné hranì platí $\<out>(x) > \<out>(y)$, na zpìtné
  30 $\<out>(x) < \<out>(y)$. Tedy $(v_k,v_1)$ musí být nutnì zpìtná.
  31
  32 V opaèném smìru nalezneme pro zpìtnou hranu $(x,y)$ cestu z $y$ do $x$ po
  33 stromových hranách.  \qed
  34
  35 \s{Algoritmus:}
  36 \algo
  37 \algin Graf $G$
  38 \:Spustíme $\<DFS>(G)$ a pøi nalezení první zpìtné hrany $(u,v)$ zastavíme.
  39 \:Pokud jsme nalezli zpìtnou hranu:
  40 \::Vypí¹eme v¹echny vrcholy mezi $(u,v)$ ze zásobníku onoho DFS v opaèném poøadí.
  41 \:jinak
  42 \::Graf je acyklický.
  43 \endalgo
  44
  45 \s{Èasová i pamì»ová slo¾itost} je $\O(m+n)$, nebo» se jedná o triviálnì upravené DFS.
  46
  47 \h{Topologické uspoøádání DAGu (grafu bez orientovaných cyklù)}
  48
  49 \s{Definice:} {\it Topologické uspoøádání} acyklického orientovaného grafu $G$ o $k$
  50 vrcholech je ohodnocení vrcholù èísly $1\dots k$ tak, ¾e $(u,v) \in E(G)
  51 \Rightarrow f(u) < f(v)$.
  52
  53 \s{Pozorování:} Vhodné topologické uspoøádání nám dá napøíklad $\<out>$ z
  54 $\<DFS>(G^R)$.  $G^R$~budi¾ graf $G$, ve kterém otoèíme orientace v¹ech hran.
  55
  56 \h{Hledání mostù v neorientovaném grafu}
  57
  58 \s{Definice:} Hrana $uv \in E(G)$ je {\I most}, pokud se jejím odebráním
  59 z~grafu $G$ zvý¹í poèet komponent souvislosti tohoto grafu.
  60
  61 \s{Pozorování:} Hrana, která je v nìjakém cyklu, nemù¾e být mostem. Z cyklu
  62 toti¾ lze libovolnì odebrat jednu hranu a pøesto zùstane souvislý. V¹echny
  63 ostatní hrany naopak mosty jsou.
  64
  65 Mù¾e být mostem jiná hrana ne¾ stromová? Zpìtné hrany nutnì tvoøí cyklus.
  66 Pøíèné a dopøedné se v neorientovaném DFS neobjeví.
  67
  68 Hledáme tedy v¹echny stromové hrany, které nejsou v ¾ádném cyklu. Projdeme graf
  69 zase pomocí upraveného DFS.
  70
  71 Kdy je hrana $uv$ v nìjakém cyklu? Kdy¾ existuje cesta $v\dots w$ (a nebo
  72 $v=w$), zpìtná hrana $wx$ a cesta $x\dots u$ (a nebo $x=u$).
  73
  74 \smallskip
  75 \s{Algoritmus} bude je¹tì trochu více upravené DFS. Pro ka¾dý vrchol~$v$ si
  76 budeme kromì hloubky je¹tì pamatovat $z(v)$. To bude nejmen¹í \<in> vrcholu,
  77 do kterého se dá dostat po zpìtných hranách z~vrcholu $v$ nebo podstromu pod ním.
  78
  79 \algo
  80 \:Vstoupíme do vrcholu $u$ jako DFS.
  81 \:$x \la $~minimum z $\<in>(v)$ pøes v¹echny zpìtné hrany $uv$
  82 \:$y \la $~minimum ze $z(w)$ pøes v¹echny stromové hrany $uw$
  83 \:$z(u) \la \min xy$
  84 \:Pokud $z(u) \ge \<in>(u)$,
  85 \::je jistì mostem hrana, po které jsme vstoupili do $u$.
  86 \endalgo
  87
  88 \s{Èasová i pamì»ová slo¾itost} tohoto upraveného DFS jsou $\O(m+n)$.
  89
  90 \qed
  91
  92 \h{Nejdel¹í cesta v ohodnoceném DAGu}
  93
  94 \s{Definice:} Pro $u,v \in V$ bude $D(u,v)$ délka nejdel¹í cesty z $u$ do $v$.
  95 $D^R(u,v)$ bude délka nejdel¹í cesty v grafu s otoèenými hranami.
  96
  97 Neexistuje-li cesta z $u$ do $v$, nech» $D(u,v) = -\infty$.
  98 %Zvolme pak $D(u)$ jako nejdel¹í cestu zaèínající v $u$. Pak platí: $$D(u) = \max_{v\in V} D(u,v)$$
  99
 100 \s{Algoritmus:}
 101
 102 \algo
 103 \algin Graf $G$, v nìm vrchol $u$.
 104 \:Zvolíme topologické uspoøádání $w_1 \dots w_n$ na $G$. Nech» $w_k=u$.
 105 \:Pøedpoèítáme si ke ka¾dému vrcholu v¹echny jeho pøedchùdce, tedy mno¾inu
 106 $W_i = \{w_j\mid(w_j,w_i)\in E\}$.
 107 \:Pro v¹echny vrcholy $w_i$ pøed $u$ ($\forall w_i: i<k$) nastavíme délku cesty $D(u,w_i)=-\infty$, pro $u$ pak $D(u,u)=0$.
 108 \:Postupnì procházíme vrcholy $w_i \in V(G)$ v topologickém poøadí a pro ka¾dý z nich spoèítáme $D(u,w_i)$.
 109 $$D(u,w_i)=\max_{w_j \mid (w_j, w_i) \in E} (D(u,w_j)+ e(w_j,w_i))$$
 110 \algout $\left\{\strut D(u,w_i)\right\}$.
 111 \endalgo
 112 \s{Èasová slo¾itost:} Sestrojení topologického uspoøádání a pøedpoèet v $\O(n+m)$. Postupné poèítání $D(u,w)$ také v $\O(n+m)$, celkem $\O(n+m)$.
 113
 114 \s{Pamì»ová slo¾itost:} Pøedpoèet pøedchùdcù zabere $\O(n+m)$ pamìti.
 115
 116 \h{Hledání kritických hran v ohodnoceném DAG-u}
 117 \s{Definice:} Hrana je kritická právì tehdy, kdy¾ le¾í na nìkteré z nejdel¹ích cest.
 118
 119 \s{Pozorování:} Hrana $(x,y)$ je kritická právì tehdy, kdy¾ $D(u,x) + e(x,y) = D(u,y)$.
 120
 121 \s{Algoritmus:}
 122 \algo
 123 \algin Graf $G$, v nìm vrchol $u$.
 124 \:Nalezneme v grafu $G$ nejdel¹í cesty z $u$ pøedchozím algoritmem
 125 \:Vybereme ty hrany, které splòují rovnost $D(u,x) + e(x,y) = D(u,y)$ -- kritické
 126 \algout Seznam kritických hran.
 127 \endalgo
 128 \s{Èasová a pamì»ová slo¾itost:} $\O(n+m)$
 129
 130 \h{Rozkládání orientovaných grafù na komponenty silné souvislosti}
 131
 132 \s{Definice:} $R$ bude relace na $V(G)$ taková, ¾e $uRv$ právì tehdy, kdy¾ existuje orientovaná cesta v~$G$ z~$u$ do~$v$ a souèasnì z~$v$ do~$u$.
 133
 134 % WTF?
 135 %\>{\I Pozorování:} Pokud $R$ je ekvivalence a $u...v$ $v...w$ je $u$-$w$ sled $\Rightarrow$ existuje $u$-$w$ cesta.
 136
 137 \s{Definice:} $G$ je {\I silnì souvislý} právì tehdy, kdy¾ $\forall (u,v) \in V(G): uRv$.
 138
 139 \s{Definice:} {\I Komponenty silné souvislosti} grafu $G$ jsou ekvivalenèní tøídy relace $R$.
 140
 141 \s{Poznámka:} Je $R$ vùbec ekvivalence? Ano, zkuste si v definici prohodit $u$ a $v$.
 142
 143 \s{Definice:} {\I Graf komponent} $C(G)$
 144
 145 $V(C(G))$: Komponenty silné souvislosti grafu $G$
 146
 147 $(C_1,C_2) \in E(C(G)) \Leftrightarrow \exists v_1 \in C_1, v_2  \in C_2: (v_1, v_2) \in E(G)$
 148
 149 \smallskip
 150
 151 \s{Lemma:} Graf komponent $C(G)$ ka¾dého grafu $G$ je DAG.
 152
 153 \proof
 154 Sporem: Nech» $C_1, C_2, \dots C_k$ tvoøí cyklus v~$C(G)$. Podle definice grafu
 155 komponent tedy musí existovat vrcholy $x_1 \dots x_k \in C_i$ a $y_1 \dots y_k
 156 \in C_{i+1}$ takové, ¾e $(x_i, y_i)$ jsou hrany grafu~$G$.
 157
 158 V¹echny $C_i$ jsou silnì souvislé, tedy existuje cesta z~$y_{i-1} \pmod k$ do~$x_i$
 159 v~$C_i$. Slepíme nyní v¹echny tyhle cesty a hrany za sebe.
 160 {\catcode`\@\active\let@\rightarrow$$x_1@y_1@\dots@x_2@y_2@\dots@x_3@y_3@\dots\,\dots\,\dots@x_k@y_k@\dots@x_1$$}
 161
 162 Slepením vznikne cyklus v~$G$, co¾ je spor, nebo» v¹echny vrcholy
 163 v~cyklu musí le¾et v jedné komponentì souvislosti.
 164 \qed
 165
 166 \smallskip
 167
 168 \s{Definice:} {\it Zdroj} v grafu $G$ je takový vrchol, do kterého nevedou ¾ádné hrany
 169
 170 \s{Definice:} {\it Zdrojová komponenta} grafu $G$ je taková komponenta silné
 171 souvislosti, která tvoøí zdroj v $C(G)$.
 172
 173 \s{Trik:} Uva¾ujme graf $G^R$ (graf $G$, ve kterém otoèíme orientace v¹ech hran). Pokud
 174 $v$~le¾í ve zdrojové komponentì grafu $G$, pak $\<DFS>(v)$ v $G^R$ projde právì
 175 komponenty~$G$.
 176
 177 Pustíme-li $\<DFS>(G)$, pak vrchol s maximálním $\<out>(v)$ le¾í nutnì ve zdrojové
 178 komponentì (laskavý ètenáø doká¾e samostatnì).
 179
 180 \s{Tvrzeníèko:} Pokud $(C_1, C_2) \in E(C(G))$, pak $$\max_{x \in C_1} \<out>(x) > \max_{x \in C_2} \<out>(x).$$
 181
 182 \proof
 183 \itemize\ibull
 184 \: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í.
 185 \: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í.
 186 \endlist
 187 \qed
 188
 189 Vybereme si tedy vrchol $v_1$ ve zdrojové komponentì grafu $G$ (ten s maximálním $\<out>(v_1)$), spustíme
 190 $\<DFS>(v)$ v $G^R$ a v¹echny dosa¾ené vrcholy $w$ oznaèkujeme -- $\<komp>(w) \la v$.
 191
 192 Nyní si vybereme vrchol $v_2$ ve zdrojové komponentì neoznaèkované èásti $G'$
 193 grafu $G$ (ten s maximálním $\<out>(v_2)$) \dots\ a algoritmus analogicky opakujeme, dokud
 194 existují neoznaèkované vrcholy.
 195
 196 \s{Pozorování:} Neoznaèkovaná èást $G'$ grafu $G$ je prázdná, nebo má zdrojovou
 197 komponentu. Kdyby zdrojovou komponentu nemìla, tak nemá zdroj ani $C(G')$, tedy
 198 $C(G')$ buïto obsahuje cyklus (spor s definicí), nebo je prázdný.
 199
 200 \goodbreak
 201 \s{Algoritmus:}
 202 \algo
 203 \algin Graf $G$
 204 \:Sestrojíme $G^R$
 205 \:$Z \la$ prázdný zásobník, $\<komp>(*) \la$ ?
 206 \: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)$.
 207 \:Postupnì pro $v \in Z$:
 208 \::Pokud $\<komp>(v)=~?$
 209 \:::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) \la v$.
 210 \algout Pro ka¾dý vrchol $v$ vrátíme jeho komponentu $\<komp>(v)$.
 211 \endalgo
 212
 213 \s{Èasová a pamì»ová slo¾itost} bude $\O(m+n)$, nebo» první DFS má $\O(m+n)$,
 214 ka¾dé dal¹í DFS se omezí jen na svoji komponentu silné souvislosti a souèet
 215 velikostí v¹ech komponent souvislosti je $\O(m+n)$.
 216
 217 \bye