definicie.tex

\chapter{Definície}\label{chap:definicie}

V tejto kapitole sme zaviedli niektoré pojmy, s ktorými sa budeme stretávať 
počas nasledujúcich kapitol. Sú to prevažne pojmy z teórie grafov. Keďže 
väčšina článkov, ktorými sme sa zaoberali v ďalších častiach je anglického 
pôvodu, rozhodli sme sa pre značenie uprednostniť knihu Graph Theory 
\citep{diestel} pred knihou Grafové algoritmy \citep{plesnik}. 

Základným pojmom je pre nás množina, čo je súbor navzájom rôznych objektov. 
Množinu prirodzených čísel vrátane nuly označujeme $\mnn$. Množinu celých 
čísel označujeme $\mnz$. Množinu reálnych čísel $\mnr$. Pre reálne číslo 
$x$ označujeme hornú celú časť $\lceil x\rceil$ a označuje najmenšie celé 
číslo väčšie alebo rovné ako $x$. Podobne dolnú celú časť označujeme 
$\lfloor x\rfloor$ a označuje najväčšie celé číslo menšie alebo rovné ako $x$. 
Základ logaritmov napísaných ako "$\log$" je 2 a základ logaritmov napísaných 
ako "$\ln$" je $\eul$. Množina $\mathcal = \{A_1, \ldots, A_k\}$ navzájom 
disjunktných podmnožín množina $A$ je \emph{rozdelenie} ak 
$A = \bigcup_{i=1}^{k} A_i$ a všetky $i$ platí, že $A_i = \emptyset$.

\section{Grafy}

Graf $G = (V, E)$ je usporiadaná dvojica množiny vrcholov a množiny hrán, ktorá 
má následujúce vlastnosti: 
\begin{itemize}
	\item $V \cap E = \emptyset$ (hrany a vrcholy sú rozlíšiteľné)
	\item $E \subseteq\left\{ \left\{ u, v\right\} : u \neq v; u, v \in V\right\} $ 
		(hrana spája dva vrcholy)
\end{itemize}

Graf sa zvyčajne znázorňuje nakreslením bodov pre každý vrchol a čiar medzi 
dvoma bodmi tam, kde existuje hrana. Rozmiestenie bodov a čiar nemá význam. 

O grafe s množinou vrcholov $V$ hovoríme, že je grafom \emph{na} $V$. 
\emph{Množina 
vrcholov grafu} $G$ je označovaná $V(G)$ a to aj v prípade, kedy graf $G$ má za 
množinu vrcholov inú množinu ako $V$. Napríklad, pre graf $H = (W, F)$ 
označujeme množinou vrcholov $V(H)$ a platí $V(H) = W$. Podobne označujeme 
\emph{množinu hrán grafu} $E(G)$ (v hore uvedenom príklade platí $E(H) = F$). 
Pre jednoduchosť hovoríme, že vrchol (hrana) patrí grafu a nie množine vrcholov 
(hrán) grafu a preto sa občas vyskytuje označenie $v \in G$ a nie $v \in V(G)$. 

\emph{Rád grafu} je počet vrcholov v grafe a označujeme ho ako $|G|$.
\emph{Prázdny graf} $(\emptyset, \emptyset )$ označujeme $\emptyset$. Grafy 
rádu $0$ alebo $1$ sa označujeme ako \emph{triviálne}.

Vrchol $v$ je incidentný s hranou $e$ ak platí $v \in e$. Hranu $\{x, y\}$ 
jednoduchšie označujeme ako $xy$. \emph{Hranami} $X-Y$ označujeme množinu 
hrán $E(X,Y) = \left\{ \left\{ x, y\right\} : x \in X, y \in Y\right\} $. 
Namiesto $E(\{x\},Y)$ píšeme $E(x,Y)$ a podobne aj namiesto $E(X,\{y\})$ 
píšeme $E(X,y)$. s
Zápisom $E(v)$ označujeme $E(v, V(G))$ a hovoríme o \emph{hranách vrchola} $v$. 

Dva vrcholy $x, y$ grafu $G$ sú \emph{susedia}, ak existuje hrana $xy$ v grafe 
$G$. Dve hrany $e \neq f$ sú susedné, ak majú spoločný jeden vrchol. Ak sú 
všetky vrcholy v grafe navzájom susedné, graf je \emph{kompletný} (alebo 
\emph{úplný}). Kompletný graf s $n$ vrcholmi označujeme $K^n$.

Majme dva grafy $G = (V,E)$ a $G' = (V', E')$. Potom $G \cup G' := (V \cup V', 
E \cup E')$. Podobne $G \cap G' := (V \cap V', E \cap E')$. Ak platí $G \cap G' 
= \emptyset$ tak hovoríme, že grafy sú \emph{disjunktné}. Ak platí $V \subseteq 
V'$ a $E \subseteq E'$, tak potom je graf $G'$ \emph{podgrafom} grafu $G$. 
Zapisujeme $G' \subseteq G$.

Ak $G' \subseteq G$ a $G'$ obsahuje všetky hrany $xy \in E$ pre $x,y \in V'$, 
tak hovoríme, že graf $G'$ je \emph{indukovaný podgraf} grafu $G$. Taktiež 
hovoríme, že $V'$ \emph{indukuje} $G'$ na $G$ a zapisujeme $G' =: G[V']$. 
Zápis $G[\{v\}]$ skracujeme na $G[v]$.

Ak je $U$ nejaká množina vrcholov, tak zápisom $G - U$ (operátory $-$ a 
$\setminus$ budeme občas zamieňať) označujeme $G[V(G) \setminus U]$. Inými 
slovami graf $G - U$ dosiahneme tak, že z grafu $G$ vymažeme všetky vrcholy z 
množiny $U$ a všetky incidentné hrany k nim. Pre $G - \{u\}$ používame aj zápis 
$G - u$.
Pre graf $G=(V,E)$ a množinu hrán $F = \{xy: x, y \in V\}$ zapisujeme 
$G + F = (V, E \cup F)$ a $G - F = (V, E \setminus F)$.

\emph{Komponent grafu} je taký maximálny podgraf, kde medzi každou dvojicou 
vrcholov existuje cesta.

\section{Vlastnosti grafu}

Uvažujme o grafe $G = (V, E)$. Množinu susedov vrchola $v$ označujeme
$N_G(v)$. Pokiaľ to bude z kontextu jasné, tak iba skrátene $N(v)$. Zápis 
rozšírme na množiny. Pre množinu $U \subseteq V$ zapisujeme $N(U)$ množinu 
susedov všetkých vrcholov $u \in U$. Množinu $N(U)$ nazývame \emph{susedmi} $U$. 
\emph{Susedov vrátane vrchola} označujeme susedov vrchola s vrcholom samotným. 
Pre vrchol $v$ susedov vrátane vrchola zapisujeme ako $N[v] := N(v) \cup \{v\}$. 
Podobne môžeme rozšíriť zápis aj na množiny. \emph{Pokrytím} množiny $U 
\subseteq V$ nazývame množinu $N[U] := N(U) \cup U$.

Číslo $d_G(v) = d(v) := |E_G(v)|$ sa nazýva \emph{stupeň} vrchola. Je to počet 
susedov vrchola (neplatí pre digrafy, multigrafy a iné zložité grafy, ktorými 
sa tu však nezaoberáme). Vrchol stupňa $0$ je \emph{izolovaný}. Číslo $\delta 
(G) := min \{d(v), v \in G\}$ je \emph{minimálny stupeň} grafu $G$. Podobne 
číslo $\Delta (G) := max \{d(v), v \in G\}$ je \emph{maximálny stupeň} grafu 
$G$.

\section{Cesta a cyklus}

\emph{Cesta} je graf $P = (V, E)$ v tvare: 
$$ V = \{x_0, x_1, x_2, x_3, \ldots, x_k\} \qquad 
   E = \{x_0x_1, x_1x_2, x_2x_3, \ldots, x_{k-1}x_k\},$$
kde všetky vrcholy $x_i$ sú navzájom rôzne. Vrcholy $x_0$ a $x_k$ sa nazývajú 
\emph{konce} cesty a zvyšné vrcholy sú \emph{vnútorné} vrcholy. Cestu 
zjednodušene označujeme sledom vrcholov: $P = x_0x_1x_2\cdots x_k$. Aj keď 
nevieme rozlíšiť medzi cestami $P_1 = x_0x_1x_2\cdots x_k$ a 
$P_2 = x_kx_{k-1}x_{k-2}\cdots x_0$, často si zvolíme jednu možnosť a hovoríme 
o \emph{ceste z $x_0$ do $x_k$} (v tomto prípade sme si vybrali cestu $P_1$). 
\emph{Dĺžka cesty} je číslo $k$ (cesta môže mať dĺžku 0).

\emph{Cyklus} je cesta $P = (V, E)$ v tvare 
$$ V = \{ x_0, x_1, x_2, x_3, \ldots, x_{k-1}\} \qquad 
E = \{x_0x_1, x_1x_2, x_2x_3, \ldots, x_{k-2}x_{k-1}, x_{k-1}x_0\}$$

O ceste má zmysel hovoriť iba ak $k \geq 3$. \emph{Dĺžka cyklu} je číslo $k$. 
Je to počet vrcholov (a zároveň aj hrán) v grafe.

V nasledujúcej časti si ukážeme dátové štruktúry, s ktorými sme v práci 
pracovali.

\section{Strom}

Graf, ktorý nemá cyklus, sa nazýva \emph{acyklický}. Taktiež sa nazýva aj 
\emph{les}. Les, ktorý má iba jeden komponent sa nazýva \emph{strom}. Takže 
les je graf, ktorého komponenty sú stromy. Často sa nám oplatí poznať 
základné vlastnosti stromu. 
Tie najzákladnejšie sú zároveň aj zameniteľné a ú rôznymi obmenami definície 
stromu.

Následné tvrdenia sú zameniteľné pre graf $T$:
%\begin{enumerate}[(i)]
\begin{enumerate}
	\item \label{itm:strom} graf $T$ je strom;
	\item ľubovoľné dva vrcholy v grafe $T$ sú spojené jedinečnou cestou 
v grafe $T$;
	\item \label{itm:minsuv} graf $T$ je minimálne súvislý -- graf $T$ 
je spojitý, ale graf $T - e$ je nespojitý pre všetky hrany $e \in T$;
	\item graf $T$ je maxmimálne acyklický -- graf $T$ neobsahuje cyklus, 
ale graf $T + xy$ cyklus obsahuje pre ľubovoľné nesusedné vrcholy $x, y \in T$.
\end{enumerate}

Jedinečnú cestu z vrcholu $x$ do vrcholu $y$ v strome $T$ budeme označovať 
$xTy$. Z ekvivalencie bodov \ref{itm:strom} a \ref{itm:minsuv} vyplýva, 
že pre každý spojitý graf platí, že jeho ľubovoľný najmenej spojitý podgraf 
bude strom.

Vrcholy stupňa jeden sa nazývajú \emph{listy}. Každý netriviálny strom má aspoň 
dva listy. Napríklad konce najdlhšej cesty. Jeden zaujímavý fakt -- ak zo 
stromu odstránime list, ostane nám strom.

Občas je vhodne označiť jeden vrchol stromu špeciálne. A to ako \emph{koreň}. 
Koreň potom tvorí základ stromu. Pokiaľ je koreň nemenný, tak hovoríme 
o \emph{zakorenenom strome}. Vybratím koreňa $k$ v strome $T$ nám dovoľuje 
spraviť čiastočné usporiadanie na $V(T)$. Nech $r$ je koreň stromu $T$, 
$r, x, y \in V(T)$, $x \leq y$ a platí, že $x \in rTy$, potom $\leq$ je 
čiastočné usporiadanie na množine $V(T)$. Zakorenené stromy sa zvyknú kresliť 
"po vrstvách", kde je vidieť čiastočné usporiadanie vrcholov.


\section{Bipartitné grafy}

Nech $r \geq 2$ je prirodzené číslo. Graf $G = (V, E)$ sa nazýva 
\emph{r-partitný}, ak môžeme $V$ rozdeliť do $r$ skupín tak, že každá hrana 
má koniec v inej skupine. Z toho vplýva, že vrcholy v jednej skupine nie sú 
susedné. Ak platí, že  $r = 2$, nenazývame graf "2-partitný" ale 
\emph{bipartitný} (i keď obe pomenovania sú správne).

\section{Toky}

Veľa vecí z reálneho sveta sa dá modelovať pomocou grafov alebo štruktúr 
podobných grafom. Ide napríklad o elektrickú rozvodnú sieť, cestnú sieť, 
vlakovú/dráhovú sieť, komunikačnú sieť. Pri týchto znázorneniach vystupujú 
vždy dvojice komunikácií a "križovatiek" (elektrické vedenie s trafostanicami, 
cesty s mestami, dráhy so zástavkami, linky s prepojovacími stanicami). Každá 
komunikácia má svoju kapacitu. V týchto štruktúrach má zmysel sa pýtať otázky, 
ako napríklad koľko veľa prúdu, zásob, dát dokáže prúdiť medzi dvoma vrcholmi. 
V teórii grafov hovoríme o tokoch. 

Konkrétne komunikáciu si môžeme predstaviť ako hranu $e = xy$, ktorá vyjadruje 
aj smer prúdenia. K usporiadanej dvojici $(x, y)$ môžeme priradiť hodnotu $k$ 
vyjadrujúcu kapacitu komunikácie. Znamená to, že $k$ jednotiek môže prúdiť z 
vrcholu $x$ do vrcholu $y$. Alebo usporiadanej dvojici $(x, y)$ môžeme priradiť
zápornú hodnotu $-k$ a to znamená, že $k$ jednotiek prúdi opačným smerom. To 
znamená, že pre zobrazenie $f:V^2\rightarrow\mnz$ (množina V označuje vrcholy), 
bude platiť, že $f(x,y) = -f(y,x)$, keď $x$ a $y$ sú susedné vrcholy.

Keď už máme vrcholy a komunikácie, musíme mať aj \emph{zdroj} vecí, ktoré po 
komunikáciach budú prúdiť a taktiež miesta, z ktorých budú tieto veci odchádzať 
z modelu. Tie sa označujú ako \emph{stoky}. Okrem týchto špeciálnych vrcholov 
platí, že $$\sum_{y\in N(x)}^{}{f(x,y) = 0}$$

Pokiaľ platia pre graf $G := (V, E)$ a zobrazenie $f:V^2\rightarrow\mnz$ 
vlastnosti $f(x,y) = -f(y,x)$ pre susedné vrcholy $x$ a $y$ a pre vrcholy mimo 
zdrojov a stôk, že $\sum_{y\in N(x)}^{}{f(x,y) = 0}$, tak budeme hovoriť o 
\emph{toku} na grafe $G$.

Graf sme si zadefinovali ako štruktúru, ktorá má hrany \emph{neorientované}, 
to znamená, že nevieme rozlíšiť, kde hrana "začína" a kde "končí". Pri tokoch 
sme ale začali rozlišovať túto vlastnosť a tým sa hrany stali 
\emph{orientovanými}. Grafy sa nazývajú neorientované, pokiaľ sú aj ich hrany 
neorientované a naopak, ak sú orientované hrany, tak hovoríme aj o 
orientovanom grafe. V ďalšom texte budeme orientovanosť uvádzať iba vtedy, keď 
nebude jasne vyplávať z kontextu.

\section{Komplexné siete}

Ďalšie veci, ktoré môžeme pri modelovaní sietí z reálneho sveta skúmať sú 
veci ohľadne štruktúry. Má zmysel sa pýtať na to, aký je priemer grafu, či vieme 
určiť hierarchiu vrcholov a jej, aké komunikácie treba prerušiť na to, aby 
sa sieť rozpadla, kam treba nasadiť obmedzený počet špiónov, aby sme získali čo 
najviac informácií a podobne.

Týmito a následujúcimi záležitosťami sa autor v knihe Graph Theory nezaoberá. 
Preto sa od tejto knihy odkloníme a budeme čerpať z dizertačnej práce, ktorú 
napísal Peter \citet{nather}.

Pri modeloch reálnych sietí má zmysel zaoberať sa nielen stupňami jednotlivých 
vrcholov ale aj distribúciou stupňov a priemerným stupňom vrchola. 
\emph{Priemerný stupeň grafu} $G = (V, E)$ označujeme $\overline{d_G} = \bar{d}$ a 
vypočítame ako: $$\overline{d_G} = \bar{d} = \frac{\sum_{v \in V}^{}{d_v}}{|V|}$$

K zadefinovaniu distribúcie budeme potrebovať ešte jednu funkciu. Táto funkcia 
vracia hodnotu 1 v bode 0 a vo všetkých ostatných bodoch vracia hodnotu 0. 
Takže dobre slúži ako filter. Označme ju $\tau$ a zadefinujme: 
$$\tau (n) = \begin{cases}
\hfill 1 \hfill & \text{ak $n=1$} \\
\hfill 0 \hfill & \text{inak} \\
\end{cases}$$

\emph{Distribúcia stupňov vrcholov} grafu $G$ je funkcia 
$p(d)$ reprezentujúca pravdepodobnosť toho, že vrchol má stupeň $d$. Platí, že: 
$$p(d) = \frac{\sum_{v \in V}^{}{\tau(d - d_v)}}{|V|}$$

Suma vo funkcii prechádza všetkými vrcholmi a vďaka filtračnej funkcii $\tau$ 
spočíta, koľko je vrcholov stupňa $d$. Potom sa toto číslo predelí počtom vrcholov.

Zaujímavou vlastnosťou grafu je \emph{klasterizačný koeficient vrchola}. Je 
definovaný ako pomer počtu hrán medzi susediacimi vrcholmi daného vrchola a 
všetkými možnými (aj potenciálnymi) hranami medzi susediacimi vrcholmi. 
Formálne, pre graf $G := (V, E)$ je \emph{klasterizačný koeficient} vrchola 
$v$ hodnota: $$c_v = \frac{|E(N[v])|}{\binom{|N[v]|}{2}}$$

\emph{Priemerný klasterizačný koeficient} $\bar{c}$ grafu $G$ je definovaný ako:
$$\bar{c} = \frac{\sum_{v\in V}^{c_v}}{|V|}$$

Podobne ako distribúciu stupňov vrcholov zadefinujeme aj distribúciu 
klasterizačných koeficientov. \emph{Distribúcia klasterizačných koeficientov 
grafu} $G$ je funkcia $c(d)$, ktorá hovorí o tom, aký je priemer
klasterizačných koeficientov pre všetky vrcholy stupňa $d$. Vypočítame ho ako: 
$$c(d) = \frac{\sum_{v \in V}^{}{\tau(d - d_v)c_v}}
{\sum_{v \in V}^{}{\tau(d - d_v)}}$$

\section{Vlastnosti komplexných sietí}

V predošlej časti sme uviedli definície vlastností, ktorými vieme medzi sebou 
jednotlivé siete porovnávať a odlíšiť ich od seba.

Prvou vlastnosťou, ktorou môžeme grafy porovnávať a objavuje sa v reálnych 
sieťach, je to, čomu sa hovorí \emph{malý svet}. Graf je sieťou malého sveta 
vtedy, keď je jeho priemer malý a zároveň má vysokú klasterizáciu vrcholov.

Veľa z reálnych sietí má ďalšiu spoločnú vlastnosť. Ich distribúcia stupňov 
vrcholov klesá mocninovo. Môžeme zapísať, že pre distribúciu platí:
$$p(d) = d^{-\alpha}$$

Siete sa líšia v konštante $\alpha$, ale iba trochu. V drvivej väčšine platí, 
že $2 \leq \alpha \leq 3$. Keďže v takýchto sieťach by mal náhodný "výsek" 
grafu podobné vlastnosti, tak táto vlastnosť sa nazýva aj \emph{bezškálovosť}.

\section{Modely sietí}\label{sec:modely}

V tejto časti si ukážeme spôsob vytvárania grafov s nejakou vlastnosťou. Keďže 
sa zaoberáme porovnávaním "obyčajných" grafov so sieťami malého sveta, 
zameriame sa najmä na tieto dva typy.

\emph{Náhodné grafy} môžeme vytvoriť napríklad týmito dvoma spôsobmi. Prvým je, 
že pevne určíme, koľko bude mať graf vrcholov a určíme, koľko hrán má mať graf. 
Potom náhodne vyberieme počet určených hrán. Druhým spôsobom je, že pevne 
určíme počet vrcholov grafu a pravdepodobnosť, s ako sa každá hrana vyberie. 
Grafy vytvorené týmito postupmi nepopisujú (nemajú dostatočné vlastnosti) siete 
malého sveta dostatočne, preto ich nebudeme považovať za siete malého sveta.

\emph{Barabási -- Albertov model} alebo aj model s preferenčným napájaním je 
spôsob vytvárania grafov, ktorý zohľadňuje stupeň vrcholov grafu. Na začiatku 
má graf daný počet náhodne spojených vrcholov a v každom kroku sa pridá 
jeden vrchol a niekoľko hrán spájajú tento pridaný vrchol s existujúcimi 
vrcholmi v grafe. Pravdepodobnosť toho, že sa hraná spojí s vrcholom je priamo 
úmerná stupňu vrchola. Tento postup vedie ku tvorbe grafom podobným 
vlastnosťami s komplexnými sieťami.

\section{Asymptotická zložitosť}

V tejto práci sa zaoberáme najmä prácou s reálnymi dátami a konkrétnymi 
algoritmami. Ale aj pri tomto zameraní je dobre, keď vieme približne odhadnúť 
s akými veľkými množstvami dát algoritmus pracuje, ako zhruba veľa operácií 
procesor vyžaduje na daný výpočet v závislosti od veľkosti vstupných dát. Inými 
slovami, potrebujeme buď vedieť porovnať dve funkcie alebo nejakú funkciu 
zatriediť medzi ostatné. 

Na tieto požiadavky vznikla \emph{"O-notácia"} \citep{onot}, ktorá vyjadruje 
asymptotický rast funkcií. Uplatňuje sa v informatike a matematike. 
Ide o vytvorenie rôznych tried funkcií. Aj keď v informatike sa zväčša 
porovnáva rast počtu krokov od veľkosti vstupu a veľkosť vstupu aj počet krokov 
sú diskrétne údaje, uvedieme tu definíciu pre funkcie, ktoré majú svoj 
definičný obor aj obor hodnôt v množinách reálnych čísel.

Vyjadrime \emph{asymptotický odhad zhora}. 
Majme dve funkcie $f, g: \mnr \rightarrow \mnr$. Potom:

$$\exists c\ge 0\ \exists x_0\ \forall x\ge x_0: 
f(x) \leq c\cdot g(x) \iff f(x) \in O(g(x))$$

Veľmi často sa v informatike zamieňa zápis $f(x) \in O(g(x))$ so zápisom 
$f(x) = O(g(x))$ a hovorí sa, že "$f(x)$ je $O(g(x))$". Napríklad, ak 
funkcia $f(x) = 5x^2+3x+7$ a funkcia $g(x) = x^2$, tak sa hovorí, 
že "$f(x)$ je $O(x^2)$". Taktiež môžeme povedať, že $f(x)$ rastie 
kvadraticky.

Vidno, že funkcia $g(x)$ nejakým spôsobom ohraničuje funkciu $f(x)$ zhora. 
Asymptotický odhad pomocou $O(g(x))$ nám ale nehovorí nič o tom, ako veľmi 
zhora je funkcia $f(x)$ ohraničená. Zväčša sa však používa dostatočne tesný 
odhad.

Ak však chceme byť v našom odhade presnejší, existuje aj \emph{asymptoticky tesný 
odhad} a je definovaný ako:

$$\exists c_1\ge 0\ \exists c_2\ge 0\ \exists x_0\ \forall x\ge x_0: 
c_1\cdot g(x)\leq f(x) \wedge f(x) \leq c_2\cdot g(x) \iff f(x) \in \Theta (g(x))$$

V praxi sa používa menej. Je však vhodný, ak chceme ukázať najtesnejší odhad 
pre daný algoritmus. Ak existuje. Ak neexistuje, alebo sme ho zatiaľ nenašli, 
tak neostáva nič iné, ako spraviť tesný horný a dolný odhad. 
\emph{Asymptotický dolný odhad} je definovaný ako:

$$\exists c\ge 0\ \exists x_0\ \forall x\ge x_0: 
c\cdot g(x) \leq f(x) \iff f(x) \in \Omega (g(x))$$

Z tejto definície je vidieť, že \emph{asymptoticky tesný odhad} $\Theta (g(x))$ 
môžeme vyjadriť aj ako: 

$$f(x) \in O(g(x)) \wedge f(x) \in \Omega (g(x)) \iff f(x) \in \Theta (g(x))$$

Tento vzťah dobre vyjadruje reálnu snahu pri určovaní asymptotickej zložitosti 
algoritmov. Algoritmus sa hrubo odhadne zhora aj zdola a postupne sa tieto 
odhadu spresňujú. 

V matematike sa používa ešte jeden asymptotický vzťah a to 
\emph{asymptotická rovnosť}. Je to podobný vzťah ako tesný asymptotický odhad, 
opäť používa dve funkcie $f(x), g(x)$ na reálnych číslach a je definovaný ako:

$$\forall \varepsilon \ge 0 \exists n_0 \forall n > n_0: 
\left| \frac{f(x)}{g(x)} - 1 \right| < \varepsilon \iff f(x) \sim g(x)$$

Z definície je vidieť, že pokiaľ sú dve funkcie asymptoticky rovnaké, tak budú 
aj navzájom asymptoticky tesné.

\section{Ostatné definície}

V tejto časti uvádzame iné definície, o ktorých si myslíme, že sú užitočné.

\emph{Maximum}, respektíve \emph{minimum} funkcie je najväčšia, resp.\ najmenšia 
hodnota, ktorú funkcia nadobúda. Pre funkciu $f(x)$ platí, že: 
\begin{align*}
\max f(x) := f(x) \mid \forall y : f(y) \leq f(x) \\
\min f(x) := f(x) \mid \forall y : f(y) \geq f(x)
\end{align*}

\emph{Argumentom maxima}, respektíve \emph{argumentom minima} funkcie sú prvky 
z definičného oboru funkcie, v ktorom funkcia nadobúda maximum, resp.\ minimum. 
Pre funkciu $f(x)$ platí, že: 
\begin{align*}
\argmax_x f(x) := \left\{x \mid \forall y : f(y) \leq f(x)\right\} \\
\argmin_x f(x) := \left\{x \mid \forall y : f(y) \geq f(x)\right\}
\end{align*}

V následujúcich kapitolách sme sa zamerali a prebrali si jednotlivé existujúce 
algoritmy, ktoré boli implementované.