2007/8-grafy/8-grafy.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{8}{Základní grafové algoritmy}{(Zapsali M. Petr, O.Tichý, ¥. Magic)}
   4
   5 \h{Reprezentace grafu}
   6 Oznaème vrcholy grafu na následujícím obrázku písmeny A, B, C, D.
   7 Pokud bychom chtìli tento graf uchovat v pamìti poèítaèe, máme na výbìr
   8 hned nìkolik zpùsobù, jak to udìlat.
   9 \figure{img1_stvorec.eps}{}{\epsfxsize}
  10
  11 \s{1. seznam hran}
  12
  13 Jednodu¹e vypí¹eme seznam v¹ech dvojic vrcholù grafu spojených hranou.
  14
  15 AB, BC, DC, CA, BC
  16 \medskip
  17
  18 \s{2. matice sousednosti}
  19
  20 Matice sousednosti je pole $A$ o velikosti $n \times n$, jeho¾ prvky na
  21 souøadnicích $i, j$ jsou dány následujícím pøedpisem:
  22
  23 $$ A_{i,j} = \left\{ \matrix {0 \Leftrightarrow \{i,j\} \notin E \cr
  24                                 1 \Leftrightarrow \{i,j\} \in E  \cr
  25                                 }
  26 \right.$$
  27
  28 Ná¹ graf z obrázku vý¹e by tedy v maticové reprezentaci vypadal takto:
  29
  30 $$\bordermatrix{
  31   & A & B & C & D\cr
  32 A & 0 & 1 & 1 & 0\cr
  33 B & 1 & 0 & 1 & 1\cr
  34 C & 1 & 1 & 0 & 1\cr
  35 D & 0 & 1 & 1 & 0\cr
  36 }$$
  37
  38 S touto matici se pracuje velmi snadno (napø. v¹echny sousedy i-tého vrcholu
  39 zjistíme jednodu¹e tak, ¾e projdeme i-tý øádek matice, co¾ pøedstavuje èasovou
  40 slo¾itost $O(n)$), ale má i jednu zøejmou nevýhodu: její velikost je v¾dy
  41 kvadratická bez ohledu na to, jak "øídký" je graf. U grafu s mnoha vrcholy, ale
  42 s malým poètem hran, tedy budeme zbyteènì plýtvat místem v pamìti.
  43
  44 Nabízí se proto tøetí, úspornìj¹í, zpùsob, a to:
  45 \medskip
  46
  47 \s{3. seznam sousedù}
  48
  49 %$$\matrix{
  50 %A&\rightarrow&BC\quad \cr
  51 %B&\rightarrow&ACD\cr
  52 %C&\rightarrow&ABD\cr
  53 %D&\rightarrow&BC\quad \cr
  54 %}$$
  55
  56 V pamìti poèítaèe by se dal seznam sousedù uchovávat dvìma poli: polem vrcholù
  57 $V$ grafu, jeho¾ prvky postupnì pro ka¾dý vrchol udávají index na zaèátek
  58 odpovídajícího úseku v poli $E$, ve kterém by byli ulo¾eni jeho sousedé.
  59 \figure{img4_susedia.eps}{Znázornìní polí seznamu sousedù.}{\epsfxsize}
  60
  61 Na tuto reprezentaci u¾ staèí prostor $O(n + m)$, co¾ u¾ je, na rozdíl od
  62 pøedchozího kvadratického prostoru, docela pøíjemné.
  63
  64 Je¹tì dodejme, ¾e aèkoliv jsme jednotlivé reprezentace ukazovali na pøíkladì
  65 neorientovaného grafu, orientované grafy se dají reprezentovat prakticky stejnì. U
  66 orientovaných grafù je toti¾ jediný rozdíl: existuje-li hrana z vrcholu $u$ do
  67 vrcholu $v$, neznamená to, ¾e existuje i hrana z $v$ do $u$ (tedy $(u, v)$ a $(v, u)$
  68 tvoøí uspoøádané dvojice).
  69
  70 \h{Prùchod grafem}
  71
  72 \s{Definice:} Vrchol je dosa¾itelný, pokud do nìj vede cesta z poèáteèního vrcholu.
  73
  74 \s{Efektivní prùchod by mìl splòovat tyto podmínky:}
  75 \itemize\ibull
  76 \:ka¾dou hranu projdu právì jednou (resp. maximálnì dvakrát - 1x tam, 1x zpìt)
  77 \:hranou se vracím zpìt, a¾ kdy¾ u¾ z vrcholu, na kterém momentálnì jsem, nevede
  78   dosud neprozkoumaná hrana
  79 \:pokud jsem do¹el po hranì do ji¾ døíve nav¹tíveného vrcholu, hned se vrátím
  80 \endlist
  81
  82 \s{Koneènost}
  83
  84 \proof
  85 Plyne z prvního bodu.
  86 \qed
  87
  88 \s{Korektnost} (algoritmus projde celý graf)
  89
  90 \proof
  91 Sporem: Nech» existuje vrchol, který je dosa¾itelný, ale algoritmus ho nepro¹el.
  92 Pak jsme ale pøi prùchodu narazili na $\{u, v\}\in E$ takovou, ¾e vrchol $u$ je
  93 dosa¾itelný a $w$ dosa¾itelný není. Tzn., ¾e $\{u, w\}$ tvoøí neprozkoumanou
  94 hranu $\Rightarrow$ spor s druhým bodem.
  95 \qed
  96
  97 \s{Èasová slo¾itost}
  98
  99 Z toho, ¾e ¾ádná hrana ani vrchol se neprojde vícekrát (první podmínka
 100 efektivního prùchodu), plyne èasová slo¾itost $O(n + m)$.
 101
 102 \>Nyní si nìco povíme o dvou zpùsobech, kterak mù¾eme procházet grafy.
 103
 104 \s{Prùchod do hloubky} (Depth First Search, DFS)
 105
 106 Prùchod do hloubky je prvním základním postupem pøi procházení grafem. Pokud bychom
 107 chtìli DFS trochu pøiblí¾it, mohli bychom ho pøirovnat k Théseovì postupu
 108 pøi prùchodu Minotaurovho bludi¹te za pomoci Ariadniny nitì.
 109
 110 \s{Prùchod do ¹íøky} (Breadth First Search, BFS)
 111
 112 Na rozdíl od prohledávání do hloubky vyu¾ívá prohledávání do ¹íøky namísto zásobníku
 113 frontu. Motivaèní úlohou by mohlo být napø. hledání nejkrat¹í cesty mezi dvìma vrcholy
 114 v grafu, nebo známý pøevozníkùv problém.
 115 \figure{img6_BFS.eps}{}{\epsfxsize}
 116
 117 \s{Pø.} Koza, vlk a zelí
 118 \figure{img8_kvz.eps}{}{\epsfxsize}
 119
 120 Øe¹ení ulohy by se dalo popsat jako hledání cesty grafem stavù od poèáteèního stavu
 121 (koza, vlk i zelí jsou na jednom bøehu) do koncového (v¹ichni byli bez újmy pøevezeni
 122 na druhý bøeh øeky).
 123
 124 \h{DFS na neorientovaném grafu}
 125
 126 Pøi prùchodu grafu do hloubky pou¾íváme zásobník. Na zaèátku se v nìm nachází pouze
 127 vstupní vrchol v. Dokud není zásobník prázdný, tak z nìj odebíráme vrchol; ten oznaèíme
 128 jako zpracovaný (abychom ho v budoucnu, kdybychom na nìj je¹tì nìkdy narazili,
 129 nezpracovávali znovu) a do zásobníku pøidáme v¹echny jeho sousedy takové, kteøí
 130 je¹tì nebyli oznaèeni jako zpracovaní.
 131
 132 \>Vrcholy znaèíme tìmito barvami
 133 \itemize\ibull
 134 \:bílá - dosud nenav¹tívìné vrcholy (na zaèátku jsou tedy bílé v¹echny)
 135 \:¹edá - oznaèuje právì zpracovávaný vrchol
 136 \:èerná - u¾ zpracované vrcholy
 137 \endlist
 138
 139 \>U ka¾dého vrcholu si dále také zapamatujeme èas pøíchodu a èas odchodu
 140 ($in[v]$, $out [v]$).
 141
 142 \s{Algoritmus}
 143
 144 \algo
 145 \:procedure Projdi(v)
 146 \::color[v] := ¹edá
 147 \::time := time + 1
 148 \::in[v] := time
 149 \::$\forall$ w $\in$ Sousedi(v):
 150 \:::if color[w] = bílá $\Rightarrow$
 151 \::::Projdi(w)
 152 \::color[v] := èerná
 153 \::time := time + 1
 154 \::out[v] := time
 155 \::
 156 \:procedure DFS()
 157 \::$\forall$ v: color[v] := bílá
 158 \::time := 0
 159 \::$\forall$ v $\in$ V :
 160 \:::if color[v] = bílá $\Rightarrow$
 161 \::::Projdi(v)
 162 \endalgo
 163
 164 Implementaci zásobníku jsme v tomto meta-algoritmu nahradili pou¾itím rekurze
 165 (která ale funguje na podobném principu, kdy se na zásobník vkládají jednotlivá
 166 volání rekurzivní funkce).
 167
 168 Na následujících obrázcích je znázornìno, jak probíhá prùchod grafu pomocí DFS:
 169
 170 \figure{img2_dfs.eps}{}{\epsfxsize}
 171 \figure{img3_dfs.eps}{Znázornìní prùbìhu algoritmu.}{\epsfxsize}
 172
 173 \s{Hrany v tomto znázornìní dìlíme na:}
 174 \itemize\ibull
 175 \:stromové - v momentì prùchodu vedou do dosud nenav¹tíveného, bílého, vrcholu
 176 \:zpìtné - ostatní hrany
 177 \endlist
 178
 179 \s{Pozorování:} plné hrany tvoøí strom (DFS strom, strom prùchodu do hloubky).
 180
 181 \s{Aplikace:}
 182 \item{(1)} hledání kostry
 183 \item{(2)} hledání komponent souvislosti
 184
 185 Èasová slo¾itost tìchto aplikací DFS je stejná jako slo¾itost pùvodního
 186 meta-algoritmu, tedy $O(n + m)$.
 187
 188 \item{(3)} hledání artikulací
 189
 190 Tuto aplikaci si teï rozebereme tro¹ku podrobnìji. Nejprve v¹ak nìkolik definic.
 191
 192 \s{Definice:} {\I Artikulace} je vrchol v grafu, jeho¾ odebráním se graf rozpadne na alespoò
 193 dvì komponenty souvislosti.
 194
 195 \s{Definice:} {\I Most} je hrana v grafu, jejím¾ odebráním se graf rozpadne na dvì
 196 komponenty souvislosti.
 197
 198 \s{Definice:} Graf je {\I 2-souvislý,} jestli¾e po odstranìní libovolného vrcholu
 199 zùstane souvislý.
 200
 201 \s{Definice:} {\I 2-souvislá komponenta} je maximální 2-souvislý podgraf.
 202
 203 Jak bychom tedy pøi hledání artikulací v grafu mohli postupovat? Jako první
 204 se nabízí tento algoritmus:
 205
 206 \s{Hloupý algoritmus}
 207
 208 Berme si postupnì v¹echny vrcholy grafu; pro ka¾dý zjistíme, jestli se jeho
 209 odebráním zvý¹il poèet komponent. K tomu bychom mohli pou¾ít prùchod do hloubky,
 210 který jsme si u¾ ukázali. Procedura Projdi(v) projde a oznaèí v¹echny vrcholy
 211 dosa¾itelné z v, tedy v¹echny vrcholy komponenty obsahující vrchol v. Mù¾eme
 212 tedy udìlat takovou zmìnu, ¾e si budeme nav¹tívené vrcholy oznaèovat èíslem
 213 komponenty.
 214
 215 Takový algoritmus by mìl slo¾itost $n \times O(n + m))$ (pro ka¾dý vrchol grafu
 216 bychom n-krát spou¹tìli DFS), co¾ se nám vùbec nelíbí. Pokusme se tedy najít
 217 nìco lep¹ího. Nejprve uèiòmì toto pozorování:
 218
 219 \s{Pozorování:} v je artikulace $\Leftrightarrow$ v je koøen DFS stromu a má
 220 alespoò dva potomky nebo v není koøen a má syna w takového, ¾e ze ¾ádného
 221 jeho potomka nevede hrana do pøedchùdce v.
 222
 223 \s{Definice:} Pøípustná cesta je taková cesta, pokud vede pøes stromové hrany
 224 DFS stromu (mù¾e konèit i skokem zpìt).
 225
 226 \figure{img7_hrany.eps}{Pøíklady pøípustných cest.}{\epsfxsize}
 227
 228 \>Dále si definujme funkci low pro ka¾dý vrchol v, takto:
 229
 230 \s{low(v)} = min(in[w], z v do w vede pøípustná cesta)
 231
 232 \s{Pozorování:} v je artikulace $\Leftrightarrow$ v je koøen DFS stromu a má
 233 alespoò dva potomky nebo má syna w takového, ¾e platí $low(w) \geq in[w]$.
 234
 235 \s{Jak ale hodnotu funkce low(w) spoèítat?}
 236
 237 low(v) = min(x, y, z)
 238
 239 x = in[v]
 240
 241 y = min(in[w],  $\{w, v\}$ je zpìtná hrana)
 242
 243 z = min(low(w), $\{v, w\}$ je stromová hrana)
 244
 245 \h{DFS na orientovaném grafu}
 246
 247 \figure{img5_dfso.eps}{Graf a znázornení prùbehu:}{\epsfxsize}
 248
 249 \s{Hrany v dìlíme na: }
 250 \itemize\ibull
 251 \:stromové $\{A,B\}$, $\{B,C\}$, $\{B,D\}$
 252 \:zpìtné: vedou do pøedchùdce v DFS stromì (do ¹edého vrcholu)
 253 \:pøíèné: vedou do vrcholu v jiném podstromì (do èerného vrcholu)
 254 \:dopøedné: vedou do svého potomka (do èerného vrcholu v tém¾e podstromì)
 255 \endlist
 256 \bigskip
 257
 258 \>Na závìr nìkolik \s{pozorování:}
 259
 260 Intervaly (in[v], out[v]) $\forall v \in V $ tvoøí dobré uzávorkování.
 261
 262 v je následník u $\Leftrightarrow (in[v], out[v]) \subseteq (in[u], out[u]) $
 263
 264 $\{u,v\}$ je zpìtná hrana $\Leftrightarrow (in[u], out[u]) \leq (in[v], out[v])$
 265
 266 $\{u,v\}$ je pøíèná hrana $\Leftrightarrow in[v] < out[v] < in[u] < out[u]$
 267 \bye