\documentclass{article}
\usepackage{slovak}
\begin{document}
\centerline{\Large\sc Prednáška: Depth-first search}
\medskip
\centerline{\copyright MišoF., jeseň 2005}
\medskip\hrule\bigskip

\begin{itemize}
\item DFS: keď sa dá, idem hlbšie, keď sa nedá, vrátim sa,
pre každý vrchol si pamätám, odkiaľ som doň prvýkrát prišiel.

\item Terminológia: koreň, podstrom, parent/rodič/otec, children/deti/synovia.

\item Implementácia s vlastným stackom je netriviálna, treba si pre
každý vrchol v ňom pamätať aj spracúvanú hranu.

\item Čo si vieme navyše pamätať? Čas objavu d (discovery)
a čas ukončenia spracovania f (finish) pre každý vrchol -- čísla od 1 do $2N$.
\item Poradiu discovery a finish eventov zodpovedá dobre uzátvorkovaný výraz.
Inými slovami $[d(u),f(u)]$ a $[d(v),f(v)]$ sú buď disjunktné, alebo jeden
je podmnožinou druhého.

\item Klasifikácia hrán: stromové, spätné, dopredné a priečne.
Ak robíme DFS neorientovaného grafu, všetky hrany sú stromové alebo
spätné.

\item Topologický sort: kým máme vrcholy, púšťame DFS, output finished.

\item Mosty: Hrana je most iff neleží na kružnici iff ak odstrihneme hranu
z parenta do childa, nevieme sa dostať z podstromu von. 

\item Artikulácie: Koreň je artikulácia, ak má viac ako 1 dieťa.
Iný vrchol je artikulácia, ak z jeho podstromu (okrem neho) nevedie
žiadna spätná hrana do nejakého jeho predka. (Spätné hrany dole v podstrome
môžu byť.) 

\item
Úprava DFS na počítanie artikulácií a mostov: pre každý vrchol $v$ si pamätáme
$l(v)$ -- najmenšie číslo vrcholu, kam sa vieme dostať postupnosťou 
$k\geq 0$ tree-hrán a jednou back-hranou.

Pre mosty pozeráme na $l(child)$, pre artikulácie na $l(.)$ pre deti daného
vrcholu.

Až na triviálny prípad (izolovaný vrchol) platí, že koncové vrcholy
mosta sú artikulácie. Opačná implikácia neplatí, existujú artikulácie, z
ktorých nevedú mosty.

\item Blokovo-artikulačný graf, 2-súvislé komponenty.

\item Silno súvislé komponenty. Začneme transponovaným grafom
$G^T$ -- otočené smery hrán. Transpozíciou sa silne súvislé komponenty nezmenia.

Všimnime si, že {\em komponentový graf} -- graf, v ktorom silne súvislé komponenty scucneme
do vrcholov -- je acyklický.

\item
Algoritmus pre silno súvislé komponenty:
\begin{enumerate}
\item $DFS(G)$, pre každý vrchol máme $f(.)$.
\item Spočítať $G^T$.
\item CountSort vrcholov podľa $f(.)$ zostupne.
\item V tomto poradí spracúvame vrcholy, zakaždým, keď nájdeme 
nespracovaný, pustíme z neho DFS v $G^T$, ofarbí nám jeden komponent.
\end{enumerate}

\item

Dôkaz algoritmu: Všimnime si pre každý silne súvislý komponent, ktorý vrchol 
z neho $DFS(G)$ navštívi ako prvý, toho nazveme reprezentantom komponentu 
a jeho $d(.)$ bude čas začiatku spracúvania komponentu.
Tento vrchol bude zároveň mať z neho najväčšie $f(.)$, toto bude koniec spracúvania komponentu.

Takto definované začiatky a konce zjavne zodpovedajú korektnému DFS v komponentovom grafe.
(Keď sa vraciame z vrcholu, je už ofarbené všetko, kam sme sa chceli dostať, a teda každý
komponent, kam sme sa vedeli dostať, je ofarbený celý.)

Jeho komponenty by to teda vypísalo v lexikografickom poradí (!)

No a teraz keď spracúvame v 4. kroku jednotlivé vrcholy, tak ako prvého z komponentu nájdeme jeho
reprezentanta. V tej chvíli sú už spracované všetky komponenty, ktoré boli v lexikografickom poradí
pred ním, a teda všetky, ktoré boli v $G$ nad ním, t.j. sú v $G^T$ pod ním. Preto keď z
reprezentanta začneme ofarbovať v $G^T$, ofarbíme práve jeho komponent.
\end{itemize}

\end{document}