3-grafy/3-grafy.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{3}{Prohledávání grafù}{}
   4
   5 \h{Prohledání do~¹íøky {\I Breadth-First Search -- BFS} }
   6
   7 Jde o grafový algoritmus, který postupnì prochází v¹echny vrcholy v~dané komponentì souvislosti.
   8 Algoritmus nejprve projde v¹echny sousedy poèáteèního vrcholu, poté sousedy sousedù, atd\dots
   9 Díky tomuto zpùsobu procházení se nìkdy té¾ nazývá \uv{\I algoritmus vlny}, nebo» se z~poèáteèního vrcholu ¹íøí pomyslná vlna, která v~ka¾dém kroku nalezne v¹echny uzly, které mají od~poèáteèního vrcholu stejnou vzdálenost. Algoritmus se tedy skvìle hodí napøíklad pro hledání nejkrat¹í cesty mezi dvìma vrcholy v~grafu.
  10
  11 Zatím pøedpokládejme, ¾e graf, se kterým pracujeme, je orientovaný.
  12 Orientovanou hranu $(u,v)$ z~$u$ do~$v$ budeme obvykle zkracovat jako $uv$.
  13 Pro neorientované grafy bude v¹e obdobné.
  14
  15 \figure{praseci-graf.eps}{Praseèí graf a prùchod vlny skrz nìj}{55mm}
  16
  17 \s{Popis algoritmu:}
  18 Na zaèátku vlo¾íme do~fronty $Q$ poèáteèní vrchol $v_0$. Dále si v~poli~$Z$
  19 budeme pro ka¾dý vrchol pamatovat znaèku, zda jsme ho ji¾ nav¹tívili ($Z[v]=1$), èi
  20 nikoli ($Z[v]=0$). Na poèátku jsou v¹echny znaèky nulové, jen vrchol~$v_0$, který
  21 je oznaèen a vlo¾en do fronty.
  22
  23 V~ka¾dém dal¹ím kroku pak zkoumáme frontu $Q$: pokud není prázdná, vezmeme
  24 z~ní první vrchol~$u$ a podíváme se na~v¹echny vrcholy~$v$, do nich¾ z~$u$
  25 vede hrana. Pokud sousedi je¹tì nejsou oznaèení, tak je oznaèíme a pøidáme je do~fronty
  26 k~následnému zpracování. Toto opakujeme, dokud není fronta prázdná.
  27
  28 \s{Algoritmus:}
  29
  30 \algo
  31 \:$Q \leftarrow \{v_0\}$.
  32 \:$Z[*] \leftarrow 0, Z[v_0] \leftarrow 1$.
  33 \:Dokud $Q \not= \emptyset $ opakujeme:
  34 \::Vyzvedneme vrchol $u$ z~$Q$.
  35 \::$\forall v: uv\in E$:
  36 \:::Je-li $Z[v]=0 \Rightarrow Z[v] \leftarrow 1$, pøidáme $v$ do~$Q$.
  37 \endalgo
  38
  39 \s{Pozorování:} {\I BFS} se zastaví.
  40
  41 \proof Zpracováváme jen vrcholy, které byly ve~frontì. Ka¾dý vrchol se dostane do~fronty maximálnì jednou. (Ka¾dý je oznaèen max. jednou, znaèky neodstraòujeme.)
  42
  43 \s{Lemma:} BFS($v_0$) oznaèí $v$ právì tehdy, kdy¾ existuje cesta z~$v_0$ do~$v$.
  44
  45 \proof
  46 \uv{$\Longrightarrow$}:
  47 Platí jako invariant po celou dobu bìhu algoritmu. To doká¾eme indukcí dle doby
  48 bìhu algoritmu:
  49
  50 První krok indukce je triviální, nebo» cesta z~$v_0$ do~$v_0$ existuje v¾dy.
  51 Nyní si pøedstavme, ¾e oznaèujeme vrchol~$v$ pøes hranu~$uv$. To znamená, ¾e
  52 vrchol~$u$ ji¾ musel být oznaèený. Dle indukèního pøedpokladu tedy existuje
  53 cesta z~$v_0$ do~$u$, a tudí¾ pokud k~této cestì \uv{pøilepíme} hranu~$uv$,
  54 dostáváme sled z~$v_0$ do~$v$, který lze v¾dy zredukovat na cestu.
  55
  56 \uv{$\Longleftarrow$} Sporem: Nech» existuje neoznaèený vrchol $v$ dosa¾itelný
  57 po nìjaké cestì z~$v_0$. Uva¾me nejkrat¹í cestu $(v_0, v)$: $v_0, v_1 \dots,
  58 v_k = v$ a vezmìme minimální~$i$ takové, ¾e~$v_i$ není oznaèený. Víme, ¾e~$i>0$
  59 (nebo»~$v_0$ je urèitì oznaèen u¾ na zaèátku algoritmu). Tudí¾~$v_{i-1}$ je
  60 oznaèený. Pøi oznaèení jsme ho ov¹em pøidali do fronty, tak¾e jsme ho z~fronty
  61 museli pozdìji zase vyjmout. Pøi tom jsme ov¹em museli objevit hranu $v_{i-1}v_i$
  62 a oznaèit vrchol~$v_i$, co¾ je spor.
  63 \qed
  64
  65 Nyní tedy víme, ¾e algoritmus je správný, a máme pøedstavu o tom, jak funguje.
  66 Podíváme-li se na~nìj podrobnìji, zjistíme, ¾e je hodnì závislý na~tom, jak si
  67 budeme graf pamatovat. Zanedlouho zároveò zjistíme, ¾e nám reprezentace grafu
  68 v~pamìti znatelnì ovlivní èasovou (i pamì»ovou) slo¾itost celého algoritmu.
  69
  70 \h{Reprezentace grafu v~pamìti}
  71
  72 Mìjme nìjaký orientovaný graf~$G$ s~$n$ vrcholy a $m$~hranami. Jak ho reprezentovat?
  73
  74 Vrcholy mù¾eme oèíslovat od~1 do~$n$. Pro ulo¾ení hran máme na~výbìr hned nìkolik zpùsobù.
  75 Pøedvedeme si je na grafu z~následujícího obrázku:
  76 \figure{imgn_o4.eps}{Ukázkový graf}{\epsfxsize}
  77
  78 \s{1. matice sousednosti}
  79
  80 Matice sousednosti pro graf $G$ na~$n$ vrcholech je ètvercová matice $A$ o~rozmìrech $n \times n$,
  81 taková, ¾e $A_{i,j}$ popisuje, jestli z~vrcholu~$i$ do vrcholu~$j$ vede hrana ($A_{i,j}=1$)
  82 nebo nikoliv ($A_{i,j}=0$).
  83
  84 Ná¹ graf z~obrázku vý¹e by tedy v~maticové reprezentaci vypadal takto:
  85
  86 $$\bordermatrix{
  87   & A & B & C & D\cr
  88 A & 0 & 1 & 1 & 0\cr
  89 B & 0 & 0 & 0 & 1\cr
  90 C & 0 & 0 & 0 & 1\cr
  91 D & 1 & 1 & 0 & 0\cr
  92 }$$
  93
  94 S touto maticí se pracuje velmi snadno, napø. v¹echny sousedy $i$-tého vrcholu
  95 zjistíme jednodu¹e tak, ¾e projdeme $i$-tý øádek matice a najdeme v¹echny jednièky.
  96 Má ov¹em dvì zøejmé nevýhody: èasovou a pamì»ovou slo¾itost. Projití sousedù
  97 jednoho vrcholu trvá v¾dy $\Theta(n)$, projití sousedù pro v¹echny vrcholy (co¾
  98 potøebujeme v~BFS) pak trvá $\Theta(n^2)$. Velikost matice je v¾dy $n \times
  99 n$, bez ohledu na~to, jak \uv{øídký} je graf. U grafu s mnoha vrcholy, ale
 100 s malým poètem hran, tedy budeme zbyteènì plýtvat místem v~pamìti. Tato
 101 reprezentace je tedy nevýhodná pøedev¹ím pro tøídy grafù, jako jsou stromy,
 102 které mají $n-1$ hran, nebo rovinné grafy, které mají nejvý¹e $3n-6$ hran.
 103
 104 \s{Pozorování:} BFS s reprezentací maticí sousednosti bì¾í v~èase: $\Theta(n^2)$.
 105
 106 \proof
 107 U¾ jsme si uvìdomili, ¾e ka¾dý vrchol se dostane do~fronty $Q$ nejvý¹e jednou. Pro ka¾dý vrchol ve~frontì potøebujeme projít jeho sousedy, co¾ nám trvá s~reprezentací maticí sousednosti $\Theta(n)$. Vrcholù je celkem $n$, tedy èasová slo¾itost je $\Theta(n^2)$.
 108 \qed
 109
 110 \smallskip
 111 \s{2. seznam sousedù}
 112
 113 V~matici sousednosti jsme museli procházet jak hrany, tak nehrany, co¾ bylo zbyteèné. Bylo by tedy výhodnìj¹í pamatovat si pro ka¾dý vrchol pouze jeho sousedy. To mù¾eme zaøídit napøíklad jedním ze~dvou následujících zpùsobù:
 114
 115 Uchovávejme pole indexované vrcholy tak, ¾e v~ka¾dém prvku pole je ukazatel
 116 na~spojový seznam sousedù tohoto vrcholu. Tedy $L(v)=\{w: vw \in E(G)\}$.
 117
 118 Pokud se nám nebude chtít pracovat se spojovými seznamy, mù¾eme vyu¾ít
 119 reprezentaci pomocí dvou polí. První pole~$V$ bude opìt indexované vrcholy.
 120 V~druhém poli~$E$ budou pro ka¾dý vrchol ulo¾eni jeho sousedé. V~poli~$V$ si
 121 pamatujeme pro ka¾dý vrchol~$i$ index do~pole~$E$, kde zaèínají jeho sousedé,
 122 a navíc dodefinujeme, ¾e $V[n+1]=m+1$.
 123 K sousedùm vrcholu~$i$ se pak ji¾ dostaneme snadno -- nalezneme je na pozicích
 124 $V[i], \dots, V[i+1]-1$.
 125
 126 \figure{sousedi.eps}{Znázornìní polí seznamu sousedù}{40mm}
 127
 128 Na tuto reprezentaci u¾ staèí prostor $\Theta(n + m)$, co¾ u¾ je, na~rozdíl
 129 od~pøedchozího kvadratického prostoru, docela pøíjemné.
 130
 131 \s{Pozorování:} BFS s~reprezentací seznamem sousedù bì¾í v~èase $\Theta(n+m)$.
 132
 133 \proof
 134 Algoritmus zpracuje ka¾dý vrchol nejvý¹e jednou a stráví jím èas lineární
 135 v~poètu odchozích hran, tedy $\Theta({\rm deg}^-(v))$. Èasová slo¾itost celého
 136 algoritmu tedy èiní:
 137 $$\Theta\left(n+\sum_{v\in V(G)} {\rm deg}^-(v)\right) = \Theta(n+m).$$
 138 \qed
 139
 140 \s{3. orákulum}
 141
 142 Dal¹í mo¾ností reprezentace je jakési orákulum, které nám na po¾ádání øekne (spoèítá),
 143 kam vedou hrany z~daného vrcholu. To se hodí napøíklad tehdy, pokud graf vznikl
 144 výpoètem a nechceme plýtvat pamìtí na jeho ulo¾ení. To se hodí napøíklad u~u¾
 145 zmínìného hlavolamu \uv{Lloydova osmièka}.
 146
 147 \smallskip
 148 \s{Neorientované grafy}
 149
 150 Chceme-li reprezentovat neorientovaný graf, ulo¾íme ka¾dou hranu v~obou orientacích.
 151
 152 \h{Výpoèet vzdáleností}
 153
 154 Abychom mohli vyu¾ít toho, ¾e algoritmus prochází vrcholy grafu ve~vlnì,
 155 k~výpoètu vzdáleností, doplníme do nìj dvì pomocná pole:
 156 $D[v]$ bude øíkat, na~kolik krokù jsme se do~$v$ dostali,
 157 $P[v]$ bude obsahovat {\I pøedchùdce} vrcholu~$v$, toti¾ vrchol~$u$,
 158 ze~kterého jsme se do~$v$ dostali po hranì a jeho¾ $D[u]=D[v]-1$.
 159
 160 \smallskip
 161 \s{Roz¹íøený algoritmus:}
 162 \algo
 163 \:$Q \leftarrow \{v_0\}$.
 164 \:$Z[*] \leftarrow 0, Z[v_0] \leftarrow 1$.
 165 \:$D[*] \leftarrow \infty, D[v_0] \leftarrow 0$.
 166 \:Dokud $Q \not= \emptyset $ opakujeme:
 167 \::Vyzvedneme vrchol $u$ z~$Q$.
 168 \::Pro ka¾dý vrchol $v$, do~kterého vede hrana z~vrcholu $u$:
 169 \:::Je-li $Z[v]=0$:
 170 \::::$Z[v] \leftarrow 1, D[v] \leftarrow D[u]+1, P[v] \leftarrow u$
 171 \::::Pøidáme $v$ do~$Q$.
 172 \endalgo
 173
 174 \s{Definice: {\I Fáze bìhu algoritmu}:} Ve~fázi $F_0$ je zpracováván vrchol $v_0$. Ve~fázi $F_{i+1}$ jsou zpracovávány vrcholy ulo¾ené do~fronty $Q$ bìhem fáze $F_i$.
 175
 176 \s{Pozorování:} Ka¾dý vrchol~$v$ dosa¾itelný z~$v_0$ se úèastní právì jedné fáze,
 177 a to té s~èíslem~$D[v]$.
 178
 179 \s{Lemma:} Po zastavení BFS pro v¹echny vrcholy dosa¾itelné z~$v_0$ platí, ¾e $D[v]$
 180 je rovno $d(v_0,v)$, toti¾ vzdálenosti (délce nejkrat¹í cesty) z~$v_0$ do~$v$.
 181
 182 \proof
 183 Nejprve si uvìdomíme, ¾e kdykoliv je~$v$ oznaèen, vede do nìj z~$v_0$ nìjaký
 184 sled délky~$v$ (indukcí, stejnì jako jsme pøed chvílí dokazovali, ¾e BFS projde
 185 v¹echny dosa¾itelné vrcholy). Proto nemù¾e být $D[v]$ men¹í ne¾ $d(v_0,v)$.
 186
 187 Sporem doká¾eme, ¾e nemù¾e být ani vìt¹í. Pøedpokládejme, ¾e existuje nìjaký
 188 \uv{¹patný} vrchol~$v$, pro který je $D[v] > d(v_0,v)$. Nech» $P$ je nìkterá z~nejkrat¹ích
 189 cest z~$v_0$ do~$v$. Z~mo¾ných ¹patných vrcholù si vyberme takový, jeho¾ $P$ je nejkrat¹í
 190 mo¾ná. Jeliko¾ pro vrchol~$v_0$ je zajisté $D[v_0] = d(v_0,v_0) = 0$, musí být $v$
 191 rùzný od~$v_0$, tak¾e má na~$P$ nìjakého pøedchùdce~$u$. Pro toho ov¹em je vzdálenost
 192 spoèítána správnì: $D[u] = d(v_0,u) = d(v_0,v)-1$.
 193
 194 Uva¾ujme nyní, co se stalo v~okam¾iku, kdy jsme~$D[u]$ nastavili. Tehdy jsme~$u$
 195 ulo¾ili do fronty, po èase jsme ho z~fronty zase vytáhli a prozkoumali jsme v¹echny
 196 vrcholy, do ní¾ vede z~$u$ hrana. Tedy i vrchol~$v$, tak¾e $D[v]$ v~tomto okam¾iku
 197 nemù¾e být vìt¹í ne¾ $D[u]+1 = d(v_0,v)$, a~to je spor.
 198 \qed
 199
 200 Víme tedy, ¾e BFS správnì spoèítá délky nejkrat¹ích cest do v¹ech vrcholù grafu.
 201 Pomocí pøedchùdcù v~poli~$P$ mù¾eme tyto cesty dokonce snadno rekonstruovat:
 202 pøedposledním vrcholem na nejkrat¹í cestì do~vrcholu~$v$ musí být vrchol $P[v]$,
 203 jeho pøedchùdcem $P[P[v]]$, \dots, a¾ do~vrcholu~$v_0$.
 204
 205 Pøedchùdci nám tedy kódují strukturu nejkrat¹ích cest do~v¹ech vrcholù.
 206 Mù¾eme se na nì dívat také následovnì:
 207
 208 \s{Definice:} Strom nejkrat¹ích cest je orientovaný strom $(W,F)$ s~mno¾inou vrcholù
 209 $W=\{ v\in V(G) \mid \hbox{$v$ dosa¾itelný z~$v_0$} \}$
 210 a hranami $F=\{ (P(v),v) \mid v\in W, v\ne v_0 \}$.
 211
 212 \s{Pozorování:} Koøenem stromu nejkrat¹ích cest je vrchol~$v_0$, cesta v~tomto
 213 stromu z~$v_0$ do~$v$ (jednoznaènì urèená, je to strom) je pak jednou z~nejkrat¹ích
 214 cest z~$v_0$ do~$v$ v~pùvodním grafu.
 215
 216 \smallskip
 217 \s{Komponenty souvislosti}
 218
 219 V~neorientovaných grafech mù¾eme BFS jednodu¹e pou¾ít na nalezení komponent souvislosti.
 220 Ji¾ víme, ¾e BFS spu¹tìné z~vrcholu~$v_0$ projde právì ty vrcholy, které jsou z~$v_0$
 221 dosa¾itelné, co¾ jsou v~neorientovaném grafu pøesnì ty, které le¾í v~té¾e komponentì.
 222
 223 Staèí opakovanì spou¹tìt BFS z~dosud neoznaèených vrcholù, poka¾dé nám oznaèí
 224 jednu komponentu.
 225
 226 \s{Algoritmus:}
 227 \algo
 228 \:Pro v¹echny vrcholy $v \in V(G)$ opakujeme:
 229 \::Pokud je vrchol $v$ neoznaèený:
 230 \:::Spustíme $\<BFS>(v)$ a pøiøadíme objevené vrcholy nové komponentì.
 231 \endalgo
 232
 233 To, co jsme o~BFS zjistili, mù¾eme shrnout do následující vìty:
 234
 235 \s{Vìta:} $\<BFS>(v_0)$ v~èase $\Theta(n + m)$ spoète:
 236 \itemize\ibull
 237 \:vrcholy dosa¾itelné z~$v_0$
 238 \:vzdálenosti tìchto vrcholù od~$v_0$
 239 \:strom nejkrat¹ích cest z~$v_0$
 240 \endlist
 241
 242 \>Prohledávání do~¹íøky ale není jediný algoritmus, který nìjak systematicky
 243 prochází graf. Jak u¾ název kapitoly napovídá, budeme se zabývat je¹tì druhým
 244 algoritmem, prohledáváním do~hloubky. Podívejme se, jak bude vypadat \dots
 245
 246 \h{Prohledávání do~hloubky {\I Depth-First Search -- DFS }}
 247
 248 Tento algoritmus neprochází graf ve~vlnì jako BFS, nýbr¾ rekurzivnì. V¾dy se
 249 zanoøí co nejhloubìji a¾ do~listu a pak se o~kus vrátí a opìt se sna¾í zanoøit.
 250 Vrcholy, ve kterých u¾ byl, ignoruje.
 251
 252 Opìt uva¾me nejdøíve graf orientovaný. Následnì si uká¾eme, ¾e v~neorientovaném grafu budou pouze malé zmìny.
 253
 254 Budeme pou¾ívat podobné znaèení jako u~BFS. V~poli $Z$ si budeme pamatovat, zda
 255 jsme vrchol ji¾ nav¹tívili (hodnota 1), nebo ne (hodnota 0). Aby se nám algoritmus
 256 lépe analyzoval, zavedeme promìnnou~$T$, která bude fungovat jako hodiny -- v~ka¾dém
 257 kroku algoritmu se zvìt¹í o~jednièku. Do~polí $\<in>$ a $\<out>$ si budeme ukládat èas
 258 prvního a posledního prùchodu vrcholem.
 259
 260 \s{Algoritmus:}
 261
 262 \algo
 263 \:Inicializace: $Z[*] \leftarrow 0, T \leftarrow 1, \<in>[*] \leftarrow ?, \<out>[*] \leftarrow ?$
 264 \:$\<DFS>(v)$:
 265 \::$Z[v] \leftarrow 1$, $\<in>[v] \leftarrow T$, $T\leftarrow T+1$
 266 \::Pro $w$: $vw \in E(G)$:
 267 \:::Pokud $Z[w]=0$, zavoláme $\<DFS>(w)$
 268 \::$out[v] \leftarrow T$, $T\leftarrow T+1$
 269 \endalgo
 270
 271 \s {Vìta:} DFS($v_0$) v~èase $\Theta(m+n)$ oznaèí právì v¹echny vrcholy dosa¾itelné z~$v_0$.
 272
 273 \proof
 274 Korektnost doká¾eme stejným argumentem, jako u~BFS.
 275
 276 V~analýze èasové slo¾itosti si pak opìt uvìdomíme, ¾e algoritmus zavoláme
 277 na~ka¾dý vrchol nejvý¹e jednou (pak u¾ je oznaèený) a zpracováním vrcholu
 278 strávíme èas lineární v~poètu hran, které z~nìj vedou. Celkem tedy prozkoumáme
 279 ka¾dou hranu nejvý¹e jednou a strávíme tím konstantní èas.
 280 \qed
 281
 282 Vyzkou¹ejme si DFS na grafu z~následujícího obrázku:
 283
 284 \figure{dfs.eps}{Znázornìní prùbìhu DFS a typù hran}{\epsfxsize}
 285
 286 Graf je reprezentován tak, ¾e v~ka¾dém vrcholu jsou hrany uspoøádány zleva doprava.
 287 Èísla u~vrcholù ukazují jejich \<in> a \<out>.
 288
 289 Mù¾eme si v¹imnout, ¾e k~rùzným hranám se DFS chová rùznì. Po~nìkterých projde,
 290 jiné vedou do u¾ prozkoumaných vrcholù, ale nìkdy do~takových, ze~kterých jsme
 291 se je¹tì nevrátili, jindy do u¾ zpracovaných. Za chvíli uvidíme, ¾e mohou nastat
 292 ètyøi rùzné situace. Nejsnáze se poznávají podle hodnot \<in> a \<out>.
 293
 294 \s{Pozorování:} Chod algoritmu mù¾eme popsat posloupností závorek: $(_v$ bude
 295 znaèit \uv{vstoupili jsme do~vrcholu~$v$} (a nastavili $\<in>(v)$), $)_v$ budi¾
 296 opu¹tìní vrcholu (nastavení $\<out>(v)$). Tato posloupnost bude správnì uzávorkovaná,
 297 èili páry závorek se nebudou køí¾it.
 298
 299 \s{Klasifikace hran:} DFS dìlí hrany na následující ètyøi druhy. Hrana $uv$ je:
 300
 301 \itemize\ibull
 302 \:{\I Stromová} (na na¹em obrázku plná) pokud po ní DFS pro¹lo do neoznaèeného vrcholu. V¹imnìte si,
 303   ¾e stromové hrany spoleènì tvoøí strom orientovaný od koøene~$v_0$. (Je to
 304   strom, jeliko¾ vzniká postupným pøidáváním listù.) Tomuto stromu se øíká DFS strom.
 305 \:{\I Zpìtná} (teèkovaná) -- taková hrana vede do~vrcholu, do kterého jsme
 306   vstoupili, ale je¹tì jsme ho neopustili (to je vrchol, který máme pøi rekurzi na zásobníku).
 307   Odpovídá uzávorkování $(_v \dots (_u \dots )_u \dots )_v$.
 308 \:{\I Dopøedná} (èárkovaná) -- vede do vrcholu, který jsme u¾ opustili, ale který je
 309   potomkem aktuálního vrcholu: $(_u \dots (_v \dots )_v \dots )_u$.
 310 \:{\I Pøíèná} (èerchovaná) -- vede do vrcholu, který jsme u¾ opustili, ale který ve~stromu
 311   nele¾í pod aktuálním vrcholem. Musí tedy vést do vrcholù \uv{nalevo} od stromové cesty
 312   z~$v_0$ do~$u$. Napravo toti¾ le¾í vrcholy, které v~okam¾iku opou¹tìní~$u$ je¹tì nebyly
 313   prozkoumané, tak¾e hrana $uv$ by se stala stromovou. Pøíèné hrany poznáme podle
 314   uzávorkování $(_v \dots )_v \dots (_u \dots )_u$.
 315 \:Jiné druhy hran nemohou existovat, probrali jsme toti¾ v¹echny mo¾nosti, v~jakém
 316   vztahu mohou být páry závorek $(_u )_u$ a $(_v )_v$.
 317 \endlist
 318 Kterého typu hrana je, mù¾eme tedy poznat podle znaèky $Z[v]$ a podle hodnot \<in> a \<out>
 319 vrcholù $u$ a~$v$.
 320
 321 \s{Neorientované grafy:} V~neorientovaných grafech (ka¾dou hranu vidíme jako dvì orientované
 322 hrany) je situace daleko jednodu¹¹í. Buïto hranu objevíme jako stromovou (a v~opaèném smìru
 323 ji vidíme jako zpìtnou), nebo ji objevíme jako zpìtnou (a~v~opaèném smìru se jeví dopøednou).
 324 Pøíèné hrany nemohou existovat, proto¾e k~nim opaèná hrana by byla pøíèná vedoucí zleva
 325 doprava, co¾ víme, ¾e nenastane.
 326
 327 \bye