3 \prednaska{10}{Prùchod grafem}{(zapsali T. Hubík, V. Kolomièenko, L. Slinták)}
5 \h{1. do hloubky (DFS)}
9 \>Hrany rozdìlíme do nekolika tøíd
11 \:{\I stromové} postupují do neoznaèených vrcholù
12 \:{\I zpìtné} vedou do u¾ oznaèených vrcholù
13 \:{\I dopøedné} vedou do vrcholù, odkud ji¾ jsme se vrátili
14 \:{\I pøíèné} pouze zprava doleva
17 \>{\I Pozn.: u neorientovaných grafù mohou být pouze stromové a zpìtné hrany}
19 {\I Slo¾itost O(m+n), n ... poèet vrcholù, m ... poèet hran}
24 \s{Definice:} Lineární uspoøádání $<$ vrcholù grafu G je topologické $\Longleftrightarrow \forall (u,v) \in E(G) : u < v$
26 \>{\I Pozorování: Pro cyklické grafy topologické uspoøádání neexistuje.}
28 \s{Vìta:} Libovolný acyklický orientovaný graf (DAG) má topologické uspoøádání a lze ho sestrojit v O(m+n).
31 Spustíme DFS, u$<$v právì tehdy, kdy¾ out(u)$>$out(v)
35 \:stromová - out(u) $>$ out(v)
36 \:zpìtná - existuje cyklus a to je spor
37 \:dopøedná - out(u) $>$ out(v)
38 \:pøíèná - out(u) $>$ in(u) $>$ out(v)
40 \>{\I Dùsledek:} Orientovaný graf $G$ je cyklický $\Longleftrightarrow$ DFS najde zpìtnou hranu, existuje zpìtná hrana $\Rightarrow$ existuje cyklus, neexistuje zpìtná hrana $\Rightarrow$ existuje topologické uspoøádání $\Rightarrow$ neexistuje cyklus.
44 \h{Nejdel¹í cesta v DAGU:}
46 (z $S$ do ka¾dého vrcholu)
49 \:Zvolíme topologické uspoøádání na $G$, BÚNO $S$ je minimum.
50 \:$\forall v: D(v)=-inf ; D(S)=0$
51 \:Postupnì procházíme vrcholy $v \in V(G)$ v topologickém poøadí a pro $\forall v$ spoèítáme $D(v)$
57 \>{\I Pozorování:} Ka¾dý DAG obsahuje zdroj (vycházejí z nìj cesty) a stok (cesty do nìj vstupují)
59 \s{Rozkládání orientovaných grafù na komponenty souvislosti}
61 \s{Definice:} $R$ bude relace na $V(G)$ tak, ¾e $uRv \Longleftrightarrow$ existuje orientovaná cesta v $G$ z $u$ do $v$ a opaène ???
63 \s{Definice:} $G$ je silnì souvislý $\Longleftrightarrow \forall (u,v) \in V(G) : uRv$
65 \>{\I Pozorování:} $R$ je ekvivalence, $u...v$ $v...w$ je $u$-$w$ sled $\Rightarrow$ existuje $u$-$v$ cesta
68 \s{Definice:} Komponenty silné souvislosti grafu $G \Longleftrightarrow$ ekvivalence tøídy relace $R$
71 \s{Lemma:} $\forall (G)$ a $\forall (u,v) \in V(G)$: existuje $u$-$v$ sled $\Longleftrightarrow$ existuje $u$-$v$ cesta
74 Buï $S$ $u$-$v$ sled, na kterém se opakuje vrchol $z$.
75 Uva¾me sled $u...z$ $z...v$, co¾ je také $u$-$v$ sled, ale je krat¹í.
76 Iterujeme $\Rightarrow$ zbude cesta.
79 \s{Definice:} Graf komponent $C(G)$
81 $V(C(G))$: SSK grafu $G$
83 $(c_1,c_2) \in E(C(G)) \Longleftrightarrow \exists v_1 \in c_1, v_2 \in c_2 : (v_1, v_2) \in E(G) $
85 \s{Lemma:} $\forall (G) : C(G)$ je DAG.
88 obrázkem a sporem, existuje cyklus $c_1, c_2, ..., c_k$ v $C(G)$.
91 \h{Algoritmus hladání silnì souvislých komponent grafu v O(n)}
93 \>{\I Pozorování 1:} DFS z vrcholu $v$ projde $\{w, \exists v$-$w$ cesta$ \}$.
95 \>{\I Pozorování 2:} Je-li $C$ stoková komponenta a $v \in V(C)$, pak DFS z $v$ projde právì $C$.
97 \>{\I Pozorování 3:} Spustíme-li DFS na celý $G$, pak vchol $v$ s maximální $out(v)$ le¾í ve zdrojové SSK.
99 \>{\I Pozorování 3*:} Nech» $C_1, C_2$ jsou SSK a $C_1, C_2 \in E(C(G)$, pak max$\{out(u), u \in V(C_1)\} >$ max$\{out(v), v \in V(C_2)\}$.
101 \>{\I Pozorování 4:} $G$ a $G^R$ mají stejné SSK ($G^R$ má proti $G$ otoèené hrany).
106 \:Sestrojíme $G^R$, $O(m+n)$
107 \:DFS na $G^R$ $\rightarrow$ $out(v)$, $O(m+n)$
108 \:$T$ bude uspoøádání vrcholù podle klesajících $out(v)$, $O(n)$
109 \:$\forall v \in V(G)$ v poøadí podle $T$, $O(m+n)$
110 \:pokud $v$ je¹tì nepatøí do ¾ádné komponenty, tak
111 \::spustím DFS z $v$ a dosa¾ené vrcholy prohlásím za dal¹í SSK, $O(m+n)$
114 \s{Vìta:} Ka¾dý orientovaný graf lze rozlo¾it na SSK v èase $O(m+n)$
119 \:1. DFS vstoupí nedøíve do $C_1$: Z $C_2$ vyleze urèitì døív ne¾ z $C_1$ $\Rightarrow$ $out(C_1)>out(C_2)$.
120 \:2. nejdøíve do $C_2$: Nejdøív se vrátím z celé $C_2$, a¾ pak nìkdy zase vlezu do $C_1$ $\Rightarrow$ $out(C_1)>out(C_2)$.