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:} Artikulace je vrchol v grafu, jeho¾ odebráním se graf rozpadne na alespoò
 193 dvì komponenty souvislosti.
 194
 195 \s{Definice:} Most je hrana v grafu, jejím¾ odebráním se graf rozpadne na dvì
 196 komponenty souvislosti.
 197
 198 \s{Pozorování}: Most je taková hrana, její¾ oba koncové vrcholy jsou artikulacemi.
 199
 200 \s{Definice:} Graf je 2-souvislý, jestli¾e po odstranìní libovolného vrcholu
 201 zùstane souvislý.
 202
 203 \s{Definice:} 2-souvislá komponenta je maximální 2-souvislý podgraf.
 204
 205 Jak bychom tedy pøi hledání artikulací v grafu mohli postupovat? Jako první
 206 se nabízí tento algoritmus:
 207
 208 \s{Hloupý algoritmus}
 209
 210 Berme si postupnì v¹echny vrcholy grafu; pro ka¾dý zjistíme, jestli se jeho
 211 odebráním zvý¹il poèet komponent. K tomu bychom mohli pou¾ít prùchod do hloubky,
 212 který jsme si u¾ ukázali. Procedura Projdi(v) projde a oznaèí v¹echny vrcholy
 213 dosa¾itelné z v, tedy v¹echny vrcholy komponenty obsahující vrchol v. Mù¾eme
 214 tedy udìlat takovou zmìnu, ¾e si budeme nav¹tívené vrcholy oznaèovat èíslem
 215 komponenty.
 216
 217 Takový algoritmus by mìl slo¾itost $n \times O(n + m))$ (pro ka¾dý vrchol grafu
 218 bychom n-krát spou¹tìli DFS), co¾ se nám vùbec nelíbí. Pokusme se tedy najít
 219 nìco lep¹ího. Nejprve uèiòmì toto pozorování:
 220
 221 \s{Pozorování:} v je artikulace $\Leftrightarrow$ v je koøen DFS stromu a má
 222 alespoò dva potomky nebo v není koøen a má syna w takového, ¾e ze ¾ádného
 223 jeho potomka nevede hrana do pøedchùdce v.
 224
 225 \s{Definice:} Pøípustná cesta je taková cesta, pokud vede pøes stromové hrany
 226 DFS stromu (mù¾e konèit i skokem zpìt).
 227
 228 \figure{img7_hrany.eps}{Pøíklady pøípustných cest.}{\epsfxsize}
 229
 230 \>Dále si definujme funkci low pro ka¾dý vrchol v, takto:
 231
 232 \s{low(v)} = min(in[w], z v do w vede pøípustná cesta)
 233
 234 \s{Pozorování:} v je artikulace $\Leftrightarrow$ v je koøen DFS stromu a má
 235 alespoò dva potomky nebo má syna w takového, ¾e platí $low(w) \geq in[w]$.
 236
 237 \s{Jak ale hodnotu funkce low(w) spoèítat?}
 238
 239 low(v) = min(x, y, z)
 240
 241 x = in[v]
 242
 243 y = min(in[w],  $\{w, v\}$ je zpìtná hrana)
 244
 245 z = min(low(w), $\{v, w\}$ je stromová hrana)
 246
 247 \h{DFS na orientovaném grafu}
 248
 249 \figure{img5_dfso.eps}{Graf a znázornení prùbehu:}{\epsfxsize}
 250
 251 \s{Hrany v dìlíme na: }
 252 \itemize\ibull
 253 \:stromové $\{A,B\}$, $\{B,C\}$, $\{B,D\}$
 254 \:zpìtné: vedou do pøedchùdce v DFS stromì (do ¹edého vrcholu)
 255 \:pøíèné: vedou do vrcholu v jiném podstromì (do èerného vrcholu)
 256 \:dopøedné: vedou do svého potomka (do èerného vrcholu v tém¾e podstromì)
 257 \endlist
 258 \bigskip
 259
 260 \>Na závìr nìkolik \s{pozorování:}
 261
 262 Intervaly (in[v], out[v]) $\forall v \in V $ tvoøí dobré uzávorkování.
 263
 264 v je následník u $\Leftrightarrow (in[v], out[v]) \leq (int[u], out[u]) $
 265
 266 $\{u,v\}$ je zpìtná hrana $\Leftrightarrow (in[u], out[u]) \leq (in[v], out[v])$
 267
 268 $\{u,v\}$ je pøíèná hrana $\Leftrightarrow int[v] < out[v] < in[u] < out[u]$
 269 \bye