 \input ../lecnotes.tex

\prednaska{10}{Prùchod grafem}{(zapsali T. Hubík, V. Kolomièenko, L. Slinták)}

\h{1. do hloubky (DFS)}

\>in(v), out(v)

\>Hrany rozdìlíme do nekolika tøíd
\itemize\ibull
\:{\I stromové} postupují do neoznaèených vrcholù
\:{\I zpìtné} vedou do u¾ oznaèených vrcholù
\:{\I dopøedné} vedou do vrcholù, odkud ji¾ jsme se vrátili
\:{\I pøíèné} pouze zprava doleva
\endlist

\>{\I Pozn.: u neorientovaných grafù mohou být pouze stromové a zpìtné hrany}

{\I Slo¾itost O(m+n), n ... poèet vrcholù, m ... poèet hran}

\h{2. do ¹íøky (BFS)}
{\I Slo¾itost O(m+n)}

\s{Definice:} Lineární uspoøádání $<$ vrcholù grafu G je topologické $\Longleftrightarrow \forall (u,v) \in E(G) : u < v$

\>{\I Pozorování: Pro cyklické grafy topologické uspoøádání neexistuje.}

\s{Vìta:} Libovolný acyklický orientovaný graf (DAG) má topologické uspoøádání a lze ho sestrojit v O(m+n).

\proof
Spustíme DFS, u$<$v právì tehdy, kdy¾ out(u)$>$out(v)

hrany:
\itemize\ibull
\:stromová - out(u) $>$ out(v)
\:zpìtná - existuje cyklus a to je spor
\:dopøedná - out(u) $>$ out(v)
\:pøíèná - out(u) $>$ in(u) $>$ out(v)
\endlist
\>{\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.
\qed


\h{Nejdel¹í cesta v DAGU:}

(z $S$ do ka¾dého vrcholu)

\algo
\:Zvolíme topologické uspoøádání na $G$, BÚNO $S$ je minimum.
\:$\forall v: D(v)=-inf ; D(S)=0$
\:Postupnì procházíme vrcholy $v \in V(G)$ v topologickém poøadí a pro $\forall v$ spoèítáme $D(v)$
\:$D(v)=max(D(n))+1$

$u:(u,v) \in E(G)$
\endalgo

\>{\I Pozorování:} Ka¾dý DAG obsahuje zdroj (vycházejí z nìj cesty) a stok (cesty do nìj vstupují)

\s{Rozkládání orientovaných grafù na komponenty souvislosti} 

\s{Definice:} $R$ bude relace na $V(G)$ tak, ¾e $uRv \Longleftrightarrow$ existuje orientovaná cesta v $G$ z $u$ do $v$ a opaène ???

\s{Definice:} $G$ je silnì souvislý $\Longleftrightarrow \forall (u,v) \in V(G) : uRv$

\>{\I Pozorování:} $R$ je ekvivalence, $u...v$ $v...w$ je $u$-$w$ sled $\Rightarrow$ existuje $u$-$v$ cesta

{\narrower
\s{Definice:} Komponenty silné souvislosti grafu $G \Longleftrightarrow$ ekvivalence tøídy relace $R$
}

\s{Lemma:} $\forall (G)$ a $\forall (u,v) \in V(G)$: existuje $u$-$v$ sled $\Longleftrightarrow$ existuje $u$-$v$ cesta

\proof
Buï $S$ $u$-$v$ sled, na kterém se opakuje vrchol $z$.
Uva¾me sled $u...z$ $z...v$, co¾ je také $u$-$v$ sled, ale je krat¹í.
Iterujeme $\Rightarrow$ zbude cesta.
\qed

\s{Definice:} Graf komponent $C(G)$

$V(C(G))$: SSK grafu $G$

$(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) $ 

\s{Lemma:} $\forall (G) : C(G)$ je DAG.

\proof
obrázkem a sporem, existuje cyklus $c_1, c_2, ..., c_k$ v $C(G)$.
\qed

\h{Algoritmus hladání silnì souvislých komponent grafu v O(n)} 

\>{\I Pozorování 1:} DFS z vrcholu $v$ projde $\{w, \exists v$-$w$ cesta$ \}$.

\>{\I Pozorování 2:} Je-li $C$ stoková komponenta a $v \in  V(C)$, pak DFS z $v$ projde právì $C$.

\>{\I Pozorování 3:} Spustíme-li DFS na celý $G$, pak vchol $v$ s maximální $out(v)$ le¾í ve zdrojové SSK.

\>{\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)\}$.

\>{\I Pozorování 4:} $G$ a $G^R$ mají stejné SSK ($G^R$ má proti $G$ otoèené hrany).

\s{Algoritmus:}

\algo
\:Sestrojíme $G^R$,  $O(m+n)$
\:DFS na $G^R$ $\rightarrow$ $out(v)$,  $O(m+n)$
\:$T$ bude uspoøádání vrcholù podle klesajících $out(v)$,  $O(n)$
\:$\forall v \in V(G)$ v poøadí podle $T$,  $O(m+n)$
\:pokud $v$ je¹tì nepatøí do ¾ádné komponenty, tak
\::spustím DFS z $v$ a dosa¾ené vrcholy prohlásím za dal¹í SSK,  $O(m+n)$
\endalgo

\s{Vìta:} Ka¾dý orientovaný graf lze rozlo¾it na SSK v èase $O(m+n)$

\proof
Pozorovani 3*:
\itemize\ibull
\: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)$. 
\: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)$.
\endlist

\bye

