\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}
