\input ../lecnotes.tex

\prednaska{4}{Aplikace DFS}{}

\h{Opakování DFS}

DFS spu¹tìné z~vrcholu~$v_0$ v~èase $\Theta(n+m)$ nalezne podgraf
dosa¾itelný z~$v_0$ a pro nìj spoète:

\itemize\ibull
\:Èasy pøíchodu $\<in>(v)$ a odchodu $\<out>(v)$ pro v¹echny vrcholy~$v$.
\:Klasifikaci v¹ech hran, tedy jejich rozdìlení na {\I stromové, zpìtné,
dopøedné a pøíèné.}
\endlist

Pokud není celý graf dosa¾itelný z~$v_0$, èasto se nám hodí volat
DFS opakovanì, dokud existují nedosa¾itelné vrcholy:

\algo
\:Pro v¹echny vrcholy~$v$:
\::Pokud $v$ je¹tì není oznaèen jako nav¹tívený:
\:::Spustíme DFS z~vrcholu~$v$.
\endalgo

V¹imnìte si, ¾e tento algoritmus stále pracuje v~èase $\Theta(n+m)$.
(Mimochodem, stejného výsledku bychom dosáhli, pokud bychom do grafu
pøidali nìjaký nový vrchol a hrany z~nìj do v¹ech ostatních vrcholù.)

\h{Detekce cyklù v orientovaném grafu}

Mìjme orientovaný graf~$G$. Chceme zjistit, zda se v~nìm nachází orientovaný
cyklus (alespoò jeden; najít v¹echny je mnohem obtí¾nìj¹í, mimo jiné proto,
¾e jich mù¾e být exponenciálnì mnoho).

\s{Lemma:} Cyklus je v grafu $G$ právì tehdy, kdy¾ DFS provedené na celý
graf oznaèí nìjakou hranu jako zpìtnou.

\proof
Pokud existuje zpìtná hrana z~$u$ do~$v$, pak spolu s~cestou po stromových
hranách z~$v$ do~$u$ tvoøí cyklus.

A~naopak: mìjme nìjaký cyklus a buï $v$ jeho vrchol s~nejni¾¹ím $\<out>(v)$.
Tím pádem na hranì vedoucí z~$v$ do následujícího vrcholu na cyklu roste \<out>,
co¾ je ov¹em mo¾né pouze na zpìtné hranì.
\qed

%\s{Algoritmus:}
%\algo
%\algin Graf $G$
%\:Spustíme $\<DFS>(G)$ a pøi nalezení první zpìtné hrany $(u,v)$ zastavíme.
%\:Pokud jsme nalezli zpìtnou hranu:
%\::Vypí¹eme v¹echny vrcholy mezi $(u,v)$ ze zásobníku onoho DFS v opaèném poøadí.
%\:jinak
%\::Graf je acyklický.
%\endalgo

\s{Èasová i pamì»ová slo¾itost} je $\O(m+n)$, nebo» se jedná o triviálnì upravené DFS.

\h{Topologické uspoøádání DAGu (grafu bez orientovaných cyklù)}

\s{Definice:} {\it Topologické uspoøádání} acyklického orientovaného grafu
je lineární uspoøádání~$\prec$ na~vrcholech grafu takové, ¾e kdykoliv je $uv$
hrana, pak $u\prec v$.

\s{Jiný pohled:} Je to prosté oèíslování $f: V(G) \rightarrow {\bb N}$
takové, ¾e pro jakoukoliv hranu $uv\in E(G)$ platí $f(u) < f(v)$.

\s{Pozorování:} Jak u¾ víme, spustíme-li DFS na acyklický graf, nenajde ¾ádnou
zpìtnou hranu. Na v¹ech ostatních typech hran \<out> klesá, tak¾e obrácené poøadí
\<out>ù je topologické.
Z~toho plyne, ¾e v~èase $\Theta(n+m)$ lze topologicky uspoøádat libovolný DAG.

\h{Nejdel¹í cesta v ohodnoceném DAGu}

Mìjme DAG~$G$, ohodnocení jeho hran $\ell: E(G) \rightarrow {\bo R}$
a nìjaký vrchol~$u$. Pro ka¾dý vrchol~$v$ chceme spoèítat $D(v)$ -- délku nejdel¹í cesty
z~$u$ do~$v$.

\s{Algoritmus:}

\algo
\:Zvolíme topologické uspoøádání $w_1 \dots w_n$ na $G$.
\:Pro $v=w_1,\ldots,w_n$ postupnì provádíme:
\::Pokud $v=u$, pak $D(u) \= 0$.
\::Jinak:
$$D(v)\=\max_{w: wv \in E} (D(w) + \ell(wv)).$$
(Pozor, mù¾e to být maximum z~prázdné mno¾iny, v~takovém pøípadì
je rovno $-\infty$.)
\endalgo

\s{Pozorování:} V¹imnìte si, ¾e koneèné~$D(v)$ vyjde právì tìm vrcholùm~$v$,
které jsou dosa¾itelné z~$u$.

\s{Èasová slo¾itost:} Topologické uspoøádání trvá $\Theta(n+m)$,
projití grafu s~výpoètem vzdáleností takté¾.

\s{TODO:} Kritické hrany.

%\h{Hledání kritických hran v ohodnoceném DAG-u}
%\s{Definice:} Hrana je kritická právì tehdy, kdy¾ le¾í na nìkteré z nejdel¹ích cest.
%
%\s{Pozorování:} Hrana $(x,y)$ je kritická právì tehdy, kdy¾ $D(u,x) + e(x,y) = D(u,y)$.
%
%\s{Algoritmus:}
%\algo
%\algin Graf $G$, v nìm vrchol $u$.
%\:Nalezneme v grafu $G$ nejdel¹í cesty z $u$ pøedchozím algoritmem
%\:Vybereme ty hrany, které splòují rovnost $D(u,x) + e(x,y) = D(u,y)$ -- kritické
%\algout Seznam kritických hran.
%\endalgo
%\s{Èasová a pamì»ová slo¾itost:} $\O(n+m)$

\h{Hledání mostù v neorientovaném grafu}

\s{Definice:} Hrana $uv \in E(G)$ je {\I most,} pokud se jejím odebráním
z~grafu~$G$ zvý¹í poèet komponent souvislosti tohoto grafu.

\s{Pozorování:} Hrana, která je souèástí nìjakého cyklu, nemù¾e být mostem.
A~naopak, pokud nìjaká hrana není mostem, pak le¾í na nìjakém cyklu.

\s{DFS klasifikace} pro neorientované grafy: Ka¾dou hranu potkáme v~obou
smìrech. Poprvé jí mù¾eme potkat jako stromovou, resp. zpìtnou. Podruhé
pak jako zpìtnou, resp. dopøednou. Pøíèné hrany se neobjeví (opaèné k~nim
by toti¾ také musely být pøíèné, ale jak víme, pøíèné hrany nikdy nevedou
\uv{zleva doprava}.)

\s{Pozorování:} Ka¾dý most je stromová hrana. Zpìtné hrany toti¾ le¾í
na cyklech.

Mìjme tedy nìjakou stromovou hranu~$uv$. Mostem není tehdy, vede-li v~grafu
$G-uv$ cesta z~$v$ do~$u$. Tato cesta musí nìkudy opustit podstrom strom~$T_v$
(to je podstrom obsahující v¹e pod vrcholem~$v$) a mù¾e tak uèinit pouze
zpìtnou hranou, které vede do~$u$ nebo kamkoliv blí¾e ke~koøeni.

\s{Definice:} $\<low>(v) = \min\{ \<in>(w) \mid \hbox{z~$T_v$ vede zpìtná
hrana do~$w$} \}$.

\s{Dùsledek:} Stromová hrana~$uv$ je most právì tehdy, kdy¾ $\<low>(v) > \<in>(u)$.

Staèí domyslet, ¾e bìhem DFS mù¾eme snadno spoèítat \<low> pro v¹echny vrcholy.
Kdykoliv opou¹tíme vrchol~$v$, polo¾íme $\<low>(v)$ rovnu minimu z~\<low> jeho
synù a \<in> vrcholù, do nich¾ z~$v$ vede zpìtná hrana. Tím DFS asymptoticky
nezpomalíme.

\h{Komponenty silné souvislosti}

\s{Definice:} Buï $T$ bude relace na $V(G)$ definovaná tak, ¾e $uTv$ právì tehdy,
existuje-li orientovaná cesta v~$G$ z~$u$ do~$v$ a souèasnì z~$v$ do~$u$.

\s{Pozorování:} $T$ je ekvivalence. Tøídám této ekvivalence se øíká {\I komponenty
silné souvislosti} (v~tomto oddílu øíkejme prostì {\I komponenty}). Graf je {\I silnì
souvislý,} pokud má právì jednu komponentu, tedy pokud $uTv$ pro ka¾dé dva vrcholu $u,v$.

\s{Definice:} {\I Graf komponent} ${\cal C}(G)$ je graf, jeho¾ vrcholy jsou
komponenty grafu~$G$ a z~komponenty $C_i$ vede hrana do~$C_j$ právì tehdy,
kdy¾ v~pùvodním grafu~$G$ existuje hrana z~nìjakého vrcholu $u\in C_i$ do nìjakého $v\in C_j$.

Jiný pohled: ${\cal C}(G)$ je graf, který z~$G$ vznikne kontrakcí ka¾dé komponenty
do~jednoho vrcholu. (Násobné hrany pøi kontrakcích odstraòujeme.)

\s{Lemma:} Graf komponent ${\cal C}(G)$ ka¾dého grafu~$G$ je acyklický.

\proof
Sporem: Nech» $C_1, C_2, \dots C_k$ tvoøí cyklus v~${\cal C}(G)$. Podle definice grafu
komponent tedy musí existovat vrcholy $x_1, \ldots, x_k$ ($x_i \in C_i$)
a $y_1, \ldots, y_k$ ($y_i \in C_{i+1}$, indexujeme modulo~$k$) takové,
¾e $x_i y_i$ jsou hrany grafu~$G$.

V¹echny komponenty $C_i$ jsou silnì souvislé, tedy existuje cesta z~$y_{i-1}$
do~$x_i$ v~$C_i$.

Slepením tìchto hran a cest vznikne cyklus v~grafu~$G$ tvaru
$$
x_1, y_1, \hbox{cesta v~$C_2$}, x_2, y_2, \hbox{cesta v~$C_3$}, x_3, \ldots,
x_k, y_k, \hbox{cesta v~$C_1$}, x_1.
$$
To je ov¹em spor s~tím, ¾e vrcholy~$x_i$ le¾í v~rùzných komponentách.
\qed

\s{Definice:} Buï~$G^R$ graf, který vznikne z~$G$ otoèením orientace v¹ech hran.

\s{Pozorování:} $G^R$ má tyté¾ komponenty jako~$G$. Navíc ${\cal C}(G^R) = ({\cal C}(G))^R$.

\s{Definice:} {\I Zdroj} øíkáme vrcholu, do~nìj¾ nevedou ¾ádné hrany. Symetricky
{\I stok} je vrchol, z~nìj¾ nevedou hrany.

\s{Pozorování:} Ka¾dý DAG má alespoò jeden zdroj a alespoò jeden stok.
Zdroje v~$G$ jsou stoky v~$G^R$ a naopak.

\s{Definice:} {\it Zdrojová komponenta} grafu $G$ je taková komponenta,
která tvoøí zdroj v $C(G)$. (Jinými slovy, ani v~$G$ do ní nevedou ¾ádné hrany
z~jiných komponent.)

\s{Trik:} Nech»~$C$ je nìjaká zdrojová komponenta a~$v$ libovolný její vrchol.
Potom DFS spu¹tìné v~$G^R$ z~vrcholu~$v$ oznaèí právì vrcholy komponenty~$C$.

\s{Plán:} Najdeme vrchol s~maximálním $\<out>(v)$. Ten urèitì le¾í ve~zdrojové
komponentì (rozmyslete si). Spustíme z~nìj DFS v~$G^R$, tím oznaèíme jednu
komponentu. Odtrhneme ji a postup opakujeme. Dokonce nemusíme pøepoèítávat
\<out>y. Staèí toti¾ pou¾ít následujicí:

\s{Tvrzeníèko:} Pokud $(C_1, C_2) \in E({\cal C}(G))$, pak $$\max_{x \in C_1} \<out>(x) > \max_{x \in C_2} \<out>(x).$$

\proof
Buïto DFS vstoupí nejdøíve do $C_1$ -- nìkdy odtamtud dojde do $C_2$ a zase se nìkdy vrátí, rozhodnì ale døíve ne¾ z $C_1$. Pro tento pøípad tvrzeníèko platí.

Nebo vstoupí nejdøíve do $C_2$. Odtud nemù¾e nikdy dojít do $C_1$. Vrátí se tedy rozhodnì døíve z celé $C_2$, ne¾ kdy vùbec vstoupí do $C_1$, tedy pro tento pøípad také tvrzeníèko platí.
\qed

Staèí tedy vybrat vrchol s~nejvìt¹ím \<out>, spustit z~nìj DFS v~$G^R$,
èím¾ oznaèíme první komponentu. Pak vybereme vrchol s~nejvìt¹ím \<out>
z~tìch, které je¹tì nebyly oznaèeny, a~pokraèujeme\dots

\goodbreak
\s{Algoritmus:}
\algo
\algin Graf $G$
\:Sestrojíme $G^R$
\:$Z \=$ prázdný zásobník, $\<komp>(*) \=$ ?
\:Spustíme $\<DFS>(G)$, pøi opu¹tení vrcholu jej vlo¾íme do $Z$. Máme tedy vrcholy v zásobníku setøídìné podle $\<out>(v)$.
\:Postupnì pro $v \in Z$:
\::Pokud $\<komp>(v)=~?$
\:::pustíme $\<DFS>(v)$ v $G^R$ s omezením jen na vrcholy $w$, pro které $\<komp>(w) =~?$, v¹em nav¹tíveným vrcholùm $w$ nastavíme $\<komp>(w) \= v$.
\algout Pro ka¾dý vrchol $v$ vrátíme jeho komponentu $\<komp>(v)$.
\endalgo

\s{Èasová a pamì»ová slo¾itost} bude $\Theta(m+n)$, nebo» první DFS má $\Theta(m+n)$,
ka¾dé dal¹í DFS se omezí jen na svoji komponentu a souèet
velikostí v¹ech komponent je $\Theta(m+n)$.

\bye
