8-grafy/8-grafy.tex

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