4-dfs/4-dfs.tex

   1 \input ../lecnotes.tex
   2 \let\la\leftarrow
   3
   4 \prednaska{4}{Aplikace DFS}{}
   5
   6 \h{Nejdel¹í cesta v ohodnoceném DAG-u (v grafu bez orientovaných cyklù)}
   7
   8 \s{Definice:} Pro $u,v \in V$ bude $D(u,v)$ délka nejdel¹í cesty z $u$ do $v$.
   9 $D^R(u,v)$ bude délka nejdel¹í cesty v grafu s otoèenými hranami.
  10
  11 Neexistuje-li cesta z $u$ do $v$, nech» $D(u,v) = -\infty$.
  12 %Zvolme pak $D(u)$ jako nejdel¹í cestu zaèínající v $u$. Pak platí: $$D(u) = \max_{v\in V} D(u,v)$$
  13
  14 \s{Algoritmus:}
  15
  16 \algo
  17 \algin Graf $G$, v nìm vrchol $u$.
  18 \:Zvolíme topologické uspoøádání $w_1 \dots w_n$ na $G$. Nech» $w_k=u$.
  19 \:Pøedpoèítáme si ke ka¾dému vrcholu v¹echny jeho pøedchùdce, tedy mno¾inu
  20 $W_i = \{w_j\mid(w_j,w_i)\in E\}$.
  21 \: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$.
  22 \: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)$.
  23 $$D(u,w_i)=\max_{w_j \mid (w_j, w_i) \in E} (D(u,w_j)+ e(w_i,w_j))$$
  24 \algout $\left\{\strut D(u,w_i)\right\}$.
  25 \endalgo
  26 \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)$.
  27
  28 \s{Pamì»ová slo¾itost:} Pøedpoèet pøedchùdcù zabere $\O(n+m)$ pamìti.
  29
  30 \h{Hledání kritických hran v ohodnoceném DAG-u}
  31 \s{Definice:} Hrana je kritická právì tehdy, kdy¾ le¾í na nìkteré z nejdel¹ích cest.
  32
  33 \s{Pozorování:} Hrana $(x,y)$ je kritická právì tehdy, kdy¾ $D(u,x) + e(x,y) = D(u,y)$.
  34
  35 \s{Algoritmus:}
  36 \algo
  37 \algin Graf $G$, v nìm vrchol $u$.
  38 \:Nalezneme v grafu $G$ nejdel¹í cesty z $u$ pøedchozím algoritmem
  39 \:Vybereme ty hrany, které splòují rovnost $D(u,x) + e(x,y) = D(u,y)$ -- kritické
  40 \algout Seznam kritických hran.
  41 \endalgo
  42 \s{Èasová a pamì»ová slo¾itost:} $\O(n+m)$
  43
  44 %\>{\I Pozorování:} $e = (x,y)$ kritická kdy¾ $D(x) + D^R(y) + e(x,y) = D(v)$
  45 % MQ: Toto pozorování mì mate. Co tam má být doopravdy?
  46
  47 %%%%%%
  48 %
  49 %\s{Definice:} $e \in E(G)$ je most v neorientovaném grafu $G$ právì tehdy, kdy¾ $G-e$ má více komponent ne¾ $G$.
  50 %
  51 %\h{Hledání mostu}
  52 %
  53 %\>{\I Pozorování:} Zpìtná hrana není most.
  54 %
  55 %Jak to poznat o stromové?
  56 %
  57 %\s{Definice:} $\<low>(v) := \min\{\<in>(w) \mid \exists x \in T_v: (x, w) \hbox{ je zpìtná}\}$
  58 %
  59 %\>{\I Pozorování:} ${u, v}$, $\<in>(u) < \<in>(v)$ není most právì tehdy kdy¾ existuje zpìtná hrana z $T_v$ do $w$ "nad $u$" (t.j. $\<in>(w) < \<in>(u)$)
  60 %
  61 %$\<low>(v) < \<in>(u)$
  62 %
  63 %$\<low>(s_1) \dots \<low>(sk)$ známe
  64 %
  65 %\>{\I Pozorování:} $\<low>(v) = \min\{\<low>(s_1) \dots \<low>(s_k), in(v), \min\{\<in>(w) \mid (v, w) \hbox{ je zpìtná}\}\}$
  66 %
  67 %%%%%%
  68
  69 \h{Rozkládání orientovaných grafù na komponenty silné souvislosti}
  70
  71 \s{Definice:} $R$ bude relace na $V(G)$ tak, ¾e $uRv$ znamená, ¾e existuje orientovaná cesta v~$G$ z~$u$ do~$v$ a opaènì.
  72
  73 % WTF?
  74 %\>{\I Pozorování:} Pokud $R$ je ekvivalence a $u...v$ $v...w$ je $u$-$w$ sled $\Rightarrow$ existuje $u$-$w$ cesta.
  75
  76 \s{Definice:} $G$ je silnì souvislý právì tehdy, kdy¾ $\forall (u,v) \in V(G): uRv$.
  77
  78 \s{Definice:} Komponenty silné souvislosti grafu $G$ jsou tøídy ekvivalence relace $R$.
  79
  80 \s{Definice:} Graf komponent $C(G)$
  81
  82 $V(C(G))$: Komponenty silné souvislosti grafu $G$
  83
  84 $(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)$
  85
  86 \smallskip
  87
  88 \s{Lemma:} Graf komponent $C(G)$ ka¾dého grafu $G$ je DAG.
  89
  90 \proof
  91 Sporem: Nech» $C_1, C_2, \dots C_k$ tvoøí cyklus v~$C(G)$. Potom existují
  92 vrcholy $x_1 \dots x_k \in C_i$ a $y_1 \dots y_k \in C_{i+1}$ takové, ¾e $(x_i,
  93 y_i)$ jsou hrany grafu~$G$.
  94
  95 V¹echny $C_i$ jsou silnì souvislé, tedy existuje cesta z~$y_{i-1}$ do~$x_i$
  96 v~$C_i$. Slepením vznikne cyklus v~$G$, co¾ je spor, nebo» v¹echny vrcholy
  97 v~cyklu musí le¾et v jedné komponentì souvislosti.
  98 \qed
  99
 100 \smallskip
 101
 102 \s{Definice:} {\it Zdrojová komponenta} grafu $G$ je taková komponenta silné
 103 souvislosti, která tvoøí zdroj v $C(G)$.
 104
 105 \s{Trik:} Uva¾ujme graf $G^R$ (graf $G$, ve kterém otoèíme orientace v¹ech hran). Pokud
 106 $v$~le¾í ve zdrojové komponentì grafu $G$, pak $\<DFS>(v)$ v $G^R$ projde právì
 107 komponenty~$G$.
 108
 109 Pustíme-li $\<DFS>(G)$, pak vrchol s maximálním $\<out>(v)$ le¾í nutnì ve zdrojové
 110 komponentì (laskavý ètenáø doká¾e samostatnì).
 111
 112 \s{Tvrzeníèko:} Dále pokud $(C_1, C_2) \in E(C(G))$, pak $$\max_{x \in C_1} \<out>(x) > \max_{x \in C_2} \<out>(x).$$
 113
 114 \proof
 115 \itemize\ibull
 116 \: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í.
 117 \: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í.
 118 \endlist
 119 \qed
 120
 121 \s{Algoritmus:}
 122
 123 \algo
 124 \algin Graf $G$
 125 \:Sestrojíme $G^R$
 126 \:$Z$ prázdný zásobník, $\<komp>(*) \la$ ?
 127 \: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)$.
 128 \:Postupnì pro $v \in Z$:
 129 \::Pokud $\<komp>(v)=~?$
 130 \:::pustíme $\<DFS>(v)$ v $G^R$, nav¹tíveným vrcholùm $w$ nastavíme $\<komp>(w) \la v$.
 131 \algout Pro ka¾dý vrchol $v$ vrátíme jeho komponentu $\<komp>(v)$.
 132 \endalgo
 133
 134 \h{Detekce cyklù v grafu}
 135
 136 Algoritmus na vypsání {\I v¹ech} cyklù v grafu si neuká¾eme, nebo» tento
 137 problém je tì¾¹í, ne¾ se zdá. Zde probíráme nalezení {\I nìjakého} cyklu v grafu.
 138
 139 \s{Lemma:} Cyklus je v grafu $G$ právì tehdy, kdy¾ $\<DFS>(G)$ oznaèí nìjakou
 140 hranu jako zpìtnou.
 141
 142 \proof Nech» je v grafu $G$ cyklus $v_1,v_2,\dots,v_k,v_1$, nech» $\<DFS>(G)$ urèí
 143 nìjakou funkci $\<out>$. Nech» je oznaèení vrcholù takové, ¾e $\<out>(v_1)$ je
 144 maximální pøes celý cyklus. Pak jistì $\<out>(v_k) < \<out>(v_1)$.
 145
 146 Nyní uva¾me poøadí opou¹tìní vrcholù na rùzných typech hran $(x,y)$. Na
 147 stromové, dopøedné a pøíèné hranì platí $\<out>(x) > \<out>(y)$, na zpìtné
 148 $\<out>(x) < \<out>(y)$. Tedy $(v_k,v_1)$ musí být nutnì zpìtná.
 149
 150 Opaèná implikace je triviální.
 151 \qed
 152
 153 Dùkaz nám sám dává zpùsob, jak najít cyklus v grafu.
 154
 155 \s{Algoritmus:}
 156 \algo
 157 \algin Graf $G$
 158 \:$Z$ budi¾ prázdný zásobník.
 159 \:Spustíme $\<DFS>(G)$ a pøi nalezení první zpìtné hrany $(u,v)$ zastavíme.
 160 \:Postupnì pro v¹echny otevøené vrcholy $w$ v poøadí, ve kterém by se z~nich DFS vracelo
 161 \::vlo¾íme $w$ na zásobník $Z$
 162 \::Pokud $w = v$ (nalezli jsme konec zpìtné hrany)
 163 \:::ukonèíme cyklus
 164 \algout Obsah zásobníku $Z$ (nalezený cyklus).
 165 \endalgo
 166
 167 \h{Hledání mostù v neorientovaném grafu}
 168
 169 \s{Definice:} Hrana $uv \in E(G)$ je {\I most}, pokud se jejím odebráním
 170 z~grafu $G$ zvý¹í poèet komponent souvislosti tohoto grafu.
 171
 172 \s{Pozorování:} Hrana, která je v nìjakém cyklu, nemù¾e být mostem. Z cyklu
 173 toti¾ lze libovolnì odebrat jednu hranu a pøesto zùstane souvislý. V¹echny
 174 ostatní hrany naopak mosty jsou.
 175
 176 Mù¾e být mostem jiná hrana ne¾ stromová? Zpìtné hrany nutnì tvoøí cyklus.
 177 Pøíèné a dopøedné se v neorientovaném DFS neobjeví.
 178
 179 Hledáme tedy v¹echny stromové hrany, které nejsou v ¾ádném cyklu. Projdeme graf
 180 zase pomocí upraveného DFS.
 181
 182 Kdy je hrana $uv$ v nìjakém cyklu? Kdy¾ existuje cesta $v\dots w$ (a nebo
 183 $v=w$), zpìtná hrana $wx$ a cesta $x\dots u$ (a nebo $x=u$).
 184
 185 \smallskip
 186 \s{Algoritmus} bude je¹tì trochu více upravené DFS. Pro ka¾dý vrchol~$v$ si
 187 budeme kromì hloubky je¹tì pamatovat $z(v)$. To bude nejmen¹í \<in> vrcholu,
 188 do kterého se dá dostat po zpìtných hranách z~vrcholu $v$ nebo podstromu pod ním.
 189
 190 \algo
 191 \:Vstoupíme do vrcholu $u$ jako DFS.
 192 \:$x \la $~minimum z $\<in>(v)$ pøes v¹echny zpìtné hrany $uv$
 193 \:$y \la $~minimum ze $z(w)$ pøes v¹echny stromové hrany $uw$
 194 \:$z(u) \la \min xy$
 195 \:Pokud $z(u) \ge \<in>(u)$,
 196 \::je jistì mostem hrana, po které jsme vstoupili do $u$.
 197 \endalgo
 198
 199 \qed
 200
 201 \bye