\input ../lecnotes.tex

\prednaska{8}{Základní grafové algoritmy}{(Zapsali M. Petr, O.Tichý, ¥. Magic)}

\h{Reprezentace grafu}
Oznaème vrcholy grafu na následujícím obrázku písmeny A, B, C, D.
Pokud bychom chtìli tento graf uchovat v pamìti poèítaèe, máme na výbìr
hned nìkolik zpùsobù, jak to udìlat.
\figure{img1_stvorec.eps}{}{\epsfxsize}

\s{1. seznam hran}

Jednodu¹e vypí¹eme seznam v¹ech dvojic vrcholù grafu spojených hranou.

AB, BC, DC, CA, BC
\medskip

\s{2. matice sousednosti}

Matice sousednosti je pole $A$ o velikosti $n \times n$, jeho¾ prvky na
souøadnicích $i, j$ jsou dány následujícím pøedpisem:

$$ A_{i,j} = \left\{ \matrix {0 \Leftrightarrow \{i,j\} \notin E \cr
            			1 \Leftrightarrow \{i,j\} \in E  \cr
				}
\right.$$

Ná¹ graf z obrázku vý¹e by tedy v maticové reprezentaci vypadal takto:

$$\bordermatrix{
  & A & B & C & D\cr
A & 0 & 1 & 1 & 0\cr
B & 1 & 0 & 1 & 1\cr
C & 1 & 1 & 0 & 1\cr
D & 0 & 1 & 1 & 0\cr
}$$

S touto matici se pracuje velmi snadno (napø. v¹echny sousedy i-tého vrcholu
zjistíme jednodu¹e tak, ¾e projdeme i-tý øádek matice, co¾ pøedstavuje èasovou
slo¾itost $O(n)$), ale má i jednu zøejmou nevýhodu: její velikost je v¾dy
kvadratická bez ohledu na to, jak "øídký" je graf. U grafu s mnoha vrcholy, ale
s malým poètem hran, tedy budeme zbyteènì plýtvat místem v pamìti.

Nabízí se proto tøetí, úspornìj¹í, zpùsob, a to:
\medskip

\s{3. seznam sousedù}

%$$\matrix{
%A&\rightarrow&BC\quad \cr 
%B&\rightarrow&ACD\cr
%C&\rightarrow&ABD\cr
%D&\rightarrow&BC\quad \cr
%}$$

V pamìti poèítaèe by se dal seznam sousedù uchovávat dvìma poli: polem vrcholù
$V$ grafu, jeho¾ prvky postupnì pro ka¾dý vrchol udávají index na zaèátek
odpovídajícího úseku v poli $E$, ve kterém by byli ulo¾eni jeho sousedé.
\figure{img4_susedia.eps}{Znázornìní polí seznamu sousedù.}{\epsfxsize}

Na tuto reprezentaci u¾ staèí prostor $O(n + m)$, co¾ u¾ je, na rozdíl od
pøedchozího kvadratického prostoru, docela pøíjemné.

Je¹tì dodejme, ¾e aèkoliv jsme jednotlivé reprezentace ukazovali na pøíkladì
neorientovaného grafu, orientované grafy se dají reprezentovat prakticky stejnì. U
orientovaných grafù je toti¾ jediný rozdíl: existuje-li hrana z vrcholu $u$ do
vrcholu $v$, neznamená to, ¾e existuje i hrana z $v$ do $u$ (tedy $(u, v)$ a $(v, u)$
tvoøí uspoøádané dvojice).

\h{Prùchod grafem}

\s{Definice:} Vrchol je dosa¾itelný, pokud do nìj vede cesta z poèáteèního vrcholu.

\s{Efektivní prùchod by mìl splòovat tyto podmínky:}
\itemize\ibull
\:ka¾dou hranu projdu právì jednou (resp. maximálnì dvakrát - 1x tam, 1x zpìt)
\:hranou se vracím zpìt, a¾ kdy¾ u¾ z vrcholu, na kterém momentálnì jsem, nevede
  dosud neprozkoumaná hrana
\:pokud jsem do¹el po hranì do ji¾ døíve nav¹tíveného vrcholu, hned se vrátím
\endlist

\s{Koneènost}

\proof
Plyne z prvního bodu.
\qed

\s{Korektnost} (algoritmus projde celý graf)

\proof
Sporem: Nech» existuje vrchol, který je dosa¾itelný, ale algoritmus ho nepro¹el.
Pak jsme ale pøi prùchodu narazili na $\{u, v\}\in E$ takovou, ¾e vrchol $u$ je
dosa¾itelný a $w$ dosa¾itelný není. Tzn., ¾e $\{u, w\}$ tvoøí neprozkoumanou
hranu $\Rightarrow$ spor s druhým bodem.
\qed

\s{Èasová slo¾itost}

Z toho, ¾e ¾ádná hrana ani vrchol se neprojde vícekrát (první podmínka
efektivního prùchodu), plyne èasová slo¾itost $O(n + m)$.

\>Nyní si nìco povíme o dvou zpùsobech, kterak mù¾eme procházet grafy.

\s{Prùchod do hloubky} (Depth First Search, DFS)

Prùchod do hloubky je prvním základním postupem pøi procházení grafem. Pokud bychom
chtìli DFS trochu pøiblí¾it, mohli bychom ho pøirovnat k Théseovì postupu
pøi prùchodu Minotaurovho bludi¹te za pomoci Ariadniny nitì.

\s{Prùchod do ¹íøky} (Breadth First Search, BFS)

Na rozdíl od prohledávání do hloubky vyu¾ívá prohledávání do ¹íøky namísto zásobníku
frontu. Motivaèní úlohou by mohlo být napø. hledání nejkrat¹í cesty mezi dvìma vrcholy
v grafu, nebo známý pøevozníkùv problém.
\figure{img6_BFS.eps}{}{\epsfxsize}

\s{Pø.} Koza, vlk a zelí
\figure{img8_kvz.eps}{}{\epsfxsize}

Øe¹ení ulohy by se dalo popsat jako hledání cesty grafem stavù od poèáteèního stavu
(koza, vlk i zelí jsou na jednom bøehu) do koncového (v¹ichni byli bez újmy pøevezeni
na druhý bøeh øeky).

\h{DFS na neorientovaném grafu}

Pøi prùchodu grafu do hloubky pou¾íváme zásobník. Na zaèátku se v nìm nachází pouze
vstupní vrchol v. Dokud není zásobník prázdný, tak z nìj odebíráme vrchol; ten oznaèíme
jako zpracovaný (abychom ho v budoucnu, kdybychom na nìj je¹tì nìkdy narazili,
nezpracovávali znovu) a do zásobníku pøidáme v¹echny jeho sousedy takové, kteøí
je¹tì nebyli oznaèeni jako zpracovaní.
 
\>Vrcholy znaèíme tìmito barvami
\itemize\ibull
\:bílá - dosud nenav¹tívìné vrcholy (na zaèátku jsou tedy bílé v¹echny)
\:¹edá - oznaèuje právì zpracovávaný vrchol
\:èerná - u¾ zpracované vrcholy
\endlist
 
\>U ka¾dého vrcholu si dále také zapamatujeme èas pøíchodu a èas odchodu
($in[v]$, $out [v]$).

\s{Algoritmus}

\algo
\:procedure Projdi(v)
\::color[v] := ¹edá
\::time := time + 1
\::in[v] := time
\::$\forall$ w $\in$ Sousedi(v): 
\:::if color[w] = bílá $\Rightarrow$
\::::Projdi(w)
\::color[v] := èerná
\::time := time + 1
\::out[v] := time
\::
\:procedure DFS()
\::$\forall$ v: color[v] := bílá
\::time := 0
\::$\forall$ v $\in$ V :
\:::if color[v] = bílá $\Rightarrow$
\::::Projdi(v)
\endalgo

Implementaci zásobníku jsme v tomto meta-algoritmu nahradili pou¾itím rekurze
(která ale funguje na podobném principu, kdy se na zásobník vkládají jednotlivá
volání rekurzivní funkce).

Na následujících obrázcích je znázornìno, jak probíhá prùchod grafu pomocí DFS:

\figure{img2_dfs.eps}{}{\epsfxsize}
\figure{img3_dfs.eps}{Znázornìní prùbìhu algoritmu.}{\epsfxsize}

\s{Hrany v tomto znázornìní dìlíme na:}
\itemize\ibull
\:stromové - v momentì prùchodu vedou do dosud nenav¹tíveného, bílého, vrcholu
\:zpìtné - ostatní hrany
\endlist

\s{Pozorování:} plné hrany tvoøí strom (DFS strom, strom prùchodu do hloubky).

\s{Aplikace:}
\item{(1)} hledání kostry
\item{(2)} hledání komponent souvislosti

Èasová slo¾itost tìchto aplikací DFS je stejná jako slo¾itost pùvodního 
meta-algoritmu, tedy $O(n + m)$.

\item{(3)} hledání artikulací

Tuto aplikaci si teï rozebereme tro¹ku podrobnìji. Nejprve v¹ak nìkolik definic.

\s{Definice:} {\I Artikulace} je vrchol v grafu, jeho¾ odebráním se graf rozpadne na alespoò
dvì komponenty souvislosti.

\s{Definice:} {\I Most} je hrana v grafu, jejím¾ odebráním se graf rozpadne na dvì
komponenty souvislosti.

\s{Definice:} Graf je {\I 2-souvislý,} jestli¾e po odstranìní libovolného vrcholu
zùstane souvislý.

\s{Definice:} {\I 2-souvislá komponenta} je maximální 2-souvislý podgraf.

Jak bychom tedy pøi hledání artikulací v grafu mohli postupovat? Jako první
se nabízí tento algoritmus:

\s{Hloupý algoritmus}

Berme si postupnì v¹echny vrcholy grafu; pro ka¾dý zjistíme, jestli se jeho
odebráním zvý¹il poèet komponent. K tomu bychom mohli pou¾ít prùchod do hloubky,
který jsme si u¾ ukázali. Procedura Projdi(v) projde a oznaèí v¹echny vrcholy
dosa¾itelné z v, tedy v¹echny vrcholy komponenty obsahující vrchol v. Mù¾eme
tedy udìlat takovou zmìnu, ¾e si budeme nav¹tívené vrcholy oznaèovat èíslem
komponenty.

Takový algoritmus by mìl slo¾itost $n \times O(n + m))$ (pro ka¾dý vrchol grafu
bychom n-krát spou¹tìli DFS), co¾ se nám vùbec nelíbí. Pokusme se tedy najít
nìco lep¹ího. Nejprve uèiòmì toto pozorování:

\s{Pozorování:} v je artikulace $\Leftrightarrow$ v je koøen DFS stromu a má 
alespoò dva potomky nebo v není koøen a má syna w takového, ¾e ze ¾ádného
jeho potomka nevede hrana do pøedchùdce v.

\s{Definice:} Pøípustná cesta je taková cesta, pokud vede pøes stromové hrany
DFS stromu (mù¾e konèit i skokem zpìt).

\figure{img7_hrany.eps}{Pøíklady pøípustných cest.}{\epsfxsize}

\>Dále si definujme funkci low pro ka¾dý vrchol v, takto:

\s{low(v)} = min(in[w], z v do w vede pøípustná cesta)

\s{Pozorování:} v je artikulace $\Leftrightarrow$ v je koøen DFS stromu a má
alespoò dva potomky nebo má syna w takového, ¾e platí $low(w) \geq in[w]$.

\s{Jak ale hodnotu funkce low(w) spoèítat?}

low(v) = min(x, y, z)

x = in[v]

y = min(in[w],  $\{w, v\}$ je zpìtná hrana)

z = min(low(w), $\{v, w\}$ je stromová hrana)

\h{DFS na orientovaném grafu}
        
\figure{img5_dfso.eps}{Graf a znázornení prùbehu:}{\epsfxsize}

\s{Hrany v dìlíme na: }
\itemize\ibull
\:stromové $\{A,B\}$, $\{B,C\}$, $\{B,D\}$
\:zpìtné: vedou do pøedchùdce v DFS stromì (do ¹edého vrcholu)
\:pøíèné: vedou do vrcholu v jiném podstromì (do èerného vrcholu)
\:dopøedné: vedou do svého potomka (do èerného vrcholu v tém¾e podstromì)
\endlist
\bigskip

\>Na závìr nìkolik \s{pozorování:}

Intervaly (in[v], out[v]) $\forall v \in V $ tvoøí dobré uzávorkování.

v je následník u $\Leftrightarrow (in[v], out[v]) \subseteq (in[u], out[u]) $

$\{u,v\}$ je zpìtná hrana $\Leftrightarrow (in[u], out[u]) \leq (in[v], out[v])$

$\{u,v\}$ je pøíèná hrana $\Leftrightarrow in[v] < out[v] < in[u] < out[u]$
\bye
