\chapter{Dokres\v lovanie hr\'an a vrcholov do nakreslen\'eho grafu}
%!
%!
\hyphenation{dru-h\'u na-kre-sle-n\'e-ho gra-fu ob-r\'a-zok na-vz\'a-jom d\^o-le-\v zi-t\'ych}
%!
%!
V tejto kapitole sa budeme venova\v t probl\'emu dokres\v lovania hr\'an a vrcholov do u\v z nakreslen\'eho grafu. 
To znamen\'a, \v ze m\'ame nakreslen\'y graf, m\'ame u\v z zafixovan\'e kde pribli\v zne je ktor\'y vrchol a chceme 
prida\v t nov\'e vrcholy alebo nov\'e spojenia medzi vrcholmi ale nechceme pritom h\'yba\v t s u\v z existuj\'ucimi 
vrcholmi (aby sme nestratili preh\v lad v nakreslenom grafe). Najprv uk\'a\v zeme \v ze dokres\v lovanie viacer\'ych 
hr\'an naraz je efekt\'ivnej\v sie ako dokres\v lovanie po jednej hrane z h\v ladiska po\v ctu kr\'i\v zen\'i hr\'an. 
Potom uvedieme dve nov\'e heuristiky na dokres\v lovanie vrcholov do nakreslen\'eho grafu a tieto heuristiky porovn\'ame, 
\v ci u\v z z h\v ladiska \v casovej a implementa\v cnej zlo\v zitosti ako aj z poh\v ladu efekt\'ivnosti 
(v tomto pr\'ipade po\v ctu kr\'i\v zen\'i hr\'an).
%!
\newline
\newline
%!
Ak m\'ame dan\'y nakreslen\'y graf $G$ a chceme do\v nho dokresli\v t hrany alebo vrcholy, tak vo v\v seobecnosti 
je lep\v sie dokres\v lova\v t vrcholy ako hrany, preto\v ze ak dokres\v lujeme hranu, ktor\'a je incidentn\'a s 
nov\'ym nedokreslen\'ym vrcholom, tak n\'am sta\v c\'i ur\v ci\v t polohu tohoto vrchola (alebo oboch vrcholov), 
a umiestnenie hrany je u\v z ur\v cen\'e. Ak dokres\v lujeme vrchol, tak m\^o\v zeme  prihliada\v t na viac vec\'i 
(ak m\'a ve\v la susedn\'ych vrcholov, tak m\^o\v zeme prihliada\v t na v\v setk\'ych, ale ak dokres\v lujeme hranu, 
tak prihliadame najviac na jeden nakreslen\'y vrchol).
%!
%!
\section{Dokres\v lovanie hr\'an do nakreslen\'eho grafu}
%!
%!
\newtheorem{insert2}{Veta}[section]
%! Toto je moja VETA, je v zosite DIP 1
\begin{insert2}
Ak k dan\'emu nakreslen\'emu grafu prid\'avame 2 hrany (koncov\'e vrcholy t\'ychto hr\'an nemusia patri\v t do grafu), tak 
vzh\v ladom na po\v cet kr\'i\v zen\'i nie je efekt\'ivnej\v sie prid\'a\v t ich postupne.
\end{insert2}
%!
\begin{proof}
Probl\'em rozdel\'ime na viacero situ\'aci\'i pod\v la toho, ktor\'e  koncov\'e vrcholy dop\'l\v nan\'ych hr\'an patria 
do grafu.
\begin{enumerate}
\item Koncov\'e vrcholy oboch hr\'an s\'u v grafe :
\newline
Tu je jedno \v ci prid\'avame obe hrany naraz, alebo ich prid\'avame postupne, nakreslenie t\'ychto hr\'an je 
u\v z ur\v cen\'e. 
\item Jedna hrana m\'a oba koncov\'e vrcholy v grafe, druh\'a m\'a len jeden :
\newline
Tu je lep\v sie najprv dokresli\v t hranu s koncov\'ymi vrcholmi v grafe a potom t\'u s jedn\'ym koncov\'ym vrcholom
v grafe, preto\v ze pri opa\v cnom postupe by sa mohli tieto dve hrany kri\v zova\v t (Obr\'azok \ref{fig:pridhran} a)~). \item Jedna m\'a oba koncov\'e vrcholy v grafe, druh\'a nem\'a ani jeden v grafe :
\newline
Tu nepom\^o\v ze dokres\v lova\v t hrany naraz, jednu dokresl\'ime do grafu, druh\'u nakresl\'ime mimo grafu.
\item Obe hrany maj\'u v grafe jeden koncov\'y vrchol :
\newline
Ak mimografov\'y vrchol t\'ychto hr\'an je ten ist\'y, tak je ve\v lmi d\^ole\v zit\'e ur\v ci\v t jeho polohu 
(Obr\'azok \ref{fig:pridhran} b)~). Ak to nie je ten ist\'y vrchol, tak hrany dokresl\'ime do grafu tak, aby sa navz\'ajom nepret\'inali. 
\item Jedna hrana m\'a jeden koncov\'y vrchol v grafe, druh\'a nem\'a ani jeden :
\newline
Ak maj\'u tieto 2 hrany spolo\v cn\'y vrchol, tak je lep\v sie najprv prida\v t hranu s jedn\'ym koncov\'ym vrcholom 
v grafe, preto\v ze ak by sme dokreslili najprv hranu bez koncov\'ych vrcholov v grafe, tak by mohlo vznikn\'u\v t viacero kr\'i\v zen\'i (Obr\'azok \ref{fig:pridhran} c)~).
%!
\item \v Ziaden koncov\'y vrchol hr\'an nie je v grafe :
\newline
Tu nepom\^o\v ze dokres\v lova\v t hrany naraz, hrany nakresl\'ime mimo grafu, je jedno v akom porad\'i.
\end{enumerate}
\end{proof}
%!
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=\textwidth]{obrazky/pridhran.eps}
\caption{Prid\'avanie hr\'an do nakreslen\'eho grafu : a)~prid\'avame hrany AX, BC, lep\v sie je prida\v t najprv BC 
b)~prid\'avame hrany AX, BX, treba rozumne n\'ajs\v t polohu vrcholu X  c)~prid\'avame hrany XZ, AX, lep\v sie je 
prida\v t najprv AX} \label{fig:pridhran}
\end{center}
\end{figure}
%!
%!
%!
\section{Dokres\v lovanie vrcholov do nakreslen\'eho\\grafu}
%!
%!
M\'ame dan\'y graf $G$ a vrcholy, ktor\'e chceme do tohoto grafu dokresli\v t. Sna\v z\'ime sa minimalizova\v t 
po\v cet kr\'i\v zen\'i hr\'an v grafe. Prv\'y probl\'em je, \v ci m\'ame dokres\v lova\v t vrcholy po jednom alebo 
viacero naraz, u\v z dokres\v lovanie jedn\'eho vrcholu do nakreslen\'eho grafu je zlo\v zit\'e.
\v Dalej treba ur\v ci\v t, v akom porad\'i sa maj\'u dan\'e vrcholy do grafu dokres\v lova\v t. Tu sa m\^o\v ze 
prihliada\v t tie\v z na viacero krit\'eri\'i, ako napr\'iklad stupe\v n vrcholu v celom grafe, stupe\v n vrcholu v 
zatia\v l nakreslenom grafe, po\v cet susedov ktor\'ych m\'a dan\'y vrchol medzi e\v ste nedokreslen\'ymi vrcholmi 
a \v dal\v sie. Na dokreslenie vybrat\'eho vrcholu do nakreslen\'eho grafu navrhneme dve nov\'e heuristiky, 
ktor\'e nesk\^ or porovn\'ame.
%!
%!
\subsection{Heuristika 1}
%!
%! zdroj zosit
%!
%! mozno pridat pri planarnych grafov definiciu oblasti
%!
T\'ato heuristika obsahuje metriku, na z\'aklade ktorej ur\v c\'i, kam je vhodn\'e umiestni\v t dan\'y vrchol. 
Sklad\'a sa z dvoch \v cast\'i, v prvej \v casti ur\v c\'i, v ktorej oblasti grafu umiestnime vrchol a v druhej \v 
casti zist\'i kde v r\'amci tejto oblasti bude najlep\v sie dan\'y vrchol umiestni\v t. 
Najprv si graf uprav\'ime tak, \v ze kr\'i\v zenia hr\'an nahrad\'ime umel\'ymi (dummy) vrcholmi, a budeme s nimi 
pracova\v t ako s norm\'alnymi. Ke\v d u\v z dokres\v lovan\'y vrchol umiestnime do grafu, 
tak m\^o\v zeme tieto umel\'e vrcholy zasa odstr\'ani\v t.
%!
%!
\newtheorem{oblast}{Defin\'icia}[section]
\begin{oblast}
M\'ame graf $G$, a jeho zakreslenie do roviny $D$. Mno\v zina bodov $R^2-D$ je neohrani\v cen\'a a 
jej s\'uvisl\'e \v casti sa naz\'yvaj\'u oblasti (faces) z D. Ke\v d\v ze D je ohrani\v cen\'a, tak presne 
jedna oblas\v t z D je neohrani\v cen\'a. T\'uto oblas\v t naz\'yvame vonkaj\v sia oblas\v t z D.
\end{oblast}
%!
%!
T\'ym, \v ze sme vlo\v zili do grafu umel\'e vrcholy, tak ka\v zd\'a vn\'utorn\'a oblas\v t je ohrani\v cen\'a vrcholmi z grafu.
\newtheorem{poc_oblasti1}[oblast]{Veta}
\begin{poc_oblasti1}
Po\v cet oblast\'i grafu $G$ s $n$ vrcholmi je $O(n^4)$. Ak je graf plan\'arny, tak po\v cet t\'ychto oblast\'i je $O(n^2)$.
\end{poc_oblasti1}
\begin{proof}
Ku ka\v zd\'emu vrcholu (p\^ovodn\'emu aj umel\'emu) v grafe zist\'ime po\v cet oblast\'i s ktor\'ymi sused\'i a 
s\'u\v cet po\v ctu t\'ychto oblast\'i, ktor\'y je ur\v cite v\"a\v c\v s\'i ako celkov\'y po\v cet oblast\'i, 
bude $O(n^4)$. P\^ovodn\'ych vrcholov je $n$. Ka\v zd\'y z nich sused\'i maxim\'alne s $n-1$ oblas\v tami, 
preto\v ze z neho vych\'adza maxim\'alne $n-1$ hr\'an. S\'u\v cet po\v ctu susedn\'ych oblast\'i 
p\^ovodn\'ych vrcholov je teda $O(n^2)$. Ak je graf plan\'arny, tak neprid\'avame \v ziadne umel\'e vrcholy, 
teda aj po\v cet oblast\'i je $O(n^2)$.
Po\v cet hr\'an v grafe je $O(n^2)$. Umel\'y vrchol prid\'avame na miesto, kde sa kr\'i\v zia hrany, 
teda ich po\v cet je $O(n^4)$. Ak je umel\'y vrchol na kr\'i\v zen\'i dvoch hr\'an, 
tak sused\'i so \v styrmi oblas\v tami. Ak je umel\'y vrchol na kr\'i\v zen\'i $m$ hr\'an, tak sused\'i s $2*m$ 
oblas\v tami, ale tento umel\'y vrchol m\'a v sebe $\frac{m*(m-1)}{2}$ umel\'ych vrcholov 
(ka\v zd\'a dvojica hr\'an v tomto vrchole). Teda najviac oblast\'i sa prid\'a, ak sa ka\v zd\'e dve 
hrany kr\'i\v zia na inom mieste. Vtedy je ale ich po\v cet pre ka\v zd\'y umel\'y vrchol ohrani\v cen\'y kon\v stantou 4, teda ich celkov\'y po\v cet je $O(n^4)$.
\end{proof}
\newline
\newline
%!
%!
K metrike, ktor\'u vyu\v z\'iva t\'ato heuristika e\v ste potrebujeme zadefinova\v t pojem vrcholov\'a vzdialenos\v t 
vrchola $v$ od oblasti $U$. Je to d\'l\v zka najkrat\v sej cesty z vrcholu $v$ k nejak\'emu vrcholu, ktor\'y sused\'i s oblas\v tou $U$.
%!
%!
\newtheorem{vvzd}[oblast]{Defin\'icia}
\begin{vvzd}
M\'ame graf $G$, a jeho zakreslenie do roviny $D$. Vrcholov\'a vzdialenos\v t vrchola $u_0$ od oblasti $U$ je 
najmen\v s\'i po\v cet vrcholov $u_1,u_2, \dots ,u_k$ tak\'ych, \v ze $(u_{i-1},u_i)\in E(G)~\forall i\in \{1..k\}$ a $u_k$ sused\'i s oblas\v tou $U$, ozna\v cujeme $D_v(U,u_0)=k$.
\end{vvzd}
%!
%!
M\'ame nakreslen\'y graf $G$ a chceme k nemu prida\v t vrchol $v$. Susedov vrchola $v$ v grafe $G$ ozna\v c\'ime 
$v_1,v_2,\dots ,v_s$. Popis heuristiky :
\begin{enumerate}
%!
\item \v cas\v t : 
\newline
Pre ka\v zd\'u oblas\v t $U_i$ ur\v c\'ime nejak\'u \v c\'iseln\'u hodnotu (t\'uto hodnotu ozna\v c\'ime $M(U_i)$) 
pod\v la zvolenej metriky a potom vyberieme oblas\v t $U_n$ s najmen\v sou hodnotou, ak je tak\'ych viac, 
tak pre vopred zvolen\'u kon\v stantu $r$ vyberieme $r$ n\'ahodn\'ych z nich (Obr\'azok \ref{fig:oblast1}). 
Metriku definujeme ako s\'u\v cet vrcholov\'ych vzdialenost\'i v\v setk\'ych susedn\'ych vrcholov vrchola $v$ od 
oblasti $U_i$.
\newline \newline
    $M(U) = \sum_{i=1}^{s} D_v(U,v_i)$ \newline
    $M(U_n) \leq M(U_i)~ \forall i\in \{1..k\}$, kde $k$ je po\v cet oblast\'i zakreslenia
%!
\item \v cas\v t : 
\newline
Pre vopred zvolen\'u kon\v stantu $k$ postupne dokres\v lovan\'y vrchol 
umiestnime na $k$ n\'ahodn\'ych poz\'ici\'i vn\'utri vybratej oblasti a vyberieme umiestnenie, pri ktorom
vzniklo najmenej kr\'i\v zen\'i. Ak je tak\'ych umiestnen\'i viac, tak vyberieme 
umiestnenie s najv\"a\v c\v sou vzdialenos\v tou od najbli\v z\v sieho vrcholu p\^ovodn\'eho grafu.
\end{enumerate}
%!
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.8\textwidth]{obrazky/oblast1.eps}
\caption{Ur\v cenie \v c\'iseln\'ych hodn\^ot pre ka\v zd\'u oblas\v t grafu} \label{fig:oblast1}
\end{center}
\end{figure}
%!
%!
\subsection{Heuristika 2 (l\'u\v cov\'a) }
%!
%!
L\'u\v cov\'a heuristika je zalo\v zen\'a na tom, \v ze pre nieko\v lk\'ych susedov $v_i$ prid\'avan\'eho vrchola $v$, 
rozdel\'ime nakreslenie grafu na nieko\v lko oblast\'i, pri\v com pre ka\v zd\'u oblas\v t budeme ma\v t l\'u\v cov\'e \v c\'islo. Toto \v c\'islo n\'am bude ud\'ava\v t, \v ze ke\v d vrchol $v$ vlo\v z\'ime do tejto oblasti, tak hrana $(v,v_i)$ prid\'a maxim\'alne tak\'yto po\v cet kr\'i\v zen\'i.
\newline
V prvom kroku nakreslen\'y graf rozdel\'ime na ve\v lk\'e oblasti (ich po\v cet bude men\v s\'i ako po\v cet vrcholov grafu) 
a v \v dal\v som kroku tieto oblasti rozdel\'ime na nieko\v lko men\v s\'ich, pri\v com z\'iskame aj l\'u\v cov\'e 
\v c\'isla t\'ychto oblast\'i. Ak m\'ame nakreslenie grafu takto rozdelen\'e pre nieko\v lk\'ych susedov vrchola $v$, 
tak sta\v c\'i ur\v ci\v t oblas\v t, ktor\'a po prieniku oblast\'i od ka\v zd\'eho tak\'ehoto suseda m\'a mal\'y 
s\'u\v cet l\'u\v cov\'ych \v c\'isel. Vr\'amci tejto oblasti potom m\^o\v zeme umiest\v nova\v t vrchol tak ako v 
Heuristike 1 (na $k$ n\'ahodn\'ych poz\'ici\'i) a potom vyberieme najlep\v sie umiestnenie vzh\v ladom na po\v cet kr\'i\v zen\'i hr\'an.
\newline
\newline
%!
Pop\'i\v seme l\'u\v cov\'u heuristiku pre jedn\'eho suseda ($u$) vrchola $v$, pre ostatn\'ych zvolen\'ych susedov je postup rovnak\'y :
%!
%!
\begin{enumerate}
\item \v cas\v t : 
\newline
Z vrchola $u$ vedieme polpriamky (l\'u\v ce) ku ka\v zd\'emu vrcholu v grafe. Priestor medzi susedn\'ymi dvoma 
polpriamkami bude ve\v lk\'a oblas\v t (Obr\'azok \ref{fig:oblastluc}).
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.8\textwidth]{obrazky/oblastluc.eps}
\caption{Vytvorenie ve\v lk\'ych oblast\'i z p\^ovodn\'eho grafu}
\label{fig:oblastluc}
\end{center}
\end{figure}
%!
\item \v cas\v t : 
\newline
Ka\v zd\'u ve\v lk\'u oblas\v t rozdel\'ime na men\v sie tak\'ymto sp\^osobom. Ak nejak\'a hrana zasahuje do tejto oblasti, 
tak z nej sprav\'ime \'use\v cku s koncov\'ymi bodmi na l\'u\v coch ohrani\v cuj\'ucich t\'uto oblas\v t. Tieto body si 
ozna\v c\'ime ako hrani\v cn\'e body. Ka\v zd\'a hrana zasahuj\'uca do oblasti m\'a dva hrani\v cn\'e body, z nich vyberieme 
ten, ktor\'y je bli\v z\v sie k vrcholu $u$ a ozna\v c\'ime ho ako d\^ole\v zit\'y bod. Potom sprav\'ime pre ka\v zd\'y 
d\^ole\v zit\'y bod \'use\v cku, ktor\'a sp\'aja tento bod a bod, ktor\'y je rovnako vzdialen\'y od vrcholu $u$ a patr\'i 
druh\'emu hrani\v cn\'emu l\'u\v cu. Men\v sie oblasti bud\'u ohrani\v cen\'e t\'ymito nov\'ymi \'use\v ckami a hrani\v cn\'ymi l\'u\v cmi. L\'u\v cov\'e \v c\'islo bude rovn\'e po\v ctu nov\'ych \'use\v ciek, ktor\'e s\'u bli\v z\v sie k vrcholu $u$ ako dan\'a oblas\v t (Obr\'azok \ref{fig:transform}). Do l\'u\v cov\'eho \v c\'isla zar\'atavame ka\v zd\'u \'use\v cku, aj ke\v d ich nakreslenie m\^o\v ze by\v t toto\v zn\'e. 
%!
%!
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.9\textwidth]{obrazky/transform.eps}
\caption{Vytvorenie men\v s\'ich oblast\'i a ich l\'u\v cov\'e \v c\'isla} \label{fig:transform}
\end{center}
\end{figure}
%!
%!
\item \v cas\v t : 
\newline
Teraz mus\'ime ur\v ci\v t nejak\'y vhodn\'y prienik medzi vzniknut\'ymi oblas\v tami. Ak dokres\v lovan\'y vrchol 
sused\'i len s dvoma vrcholmi, tak m\^o\v zeme pre ka\v zd\'u dvojicu men\v s\'ich oblast\'i zisti\v t, \v ci maj\'u 
spolo\v cn\'y prienik a s\'u\v cet ich l\'u\v cov\'ych \v c\'isel prirad\'ime tomuto prieniku. 
Potom u\v z len sta\v c\'i vybra\v t prieniky oblast\'i s najmen\v s\'im tak\'ymto s\'u\v ctom a umiestnime vrchol sem. 
Ak dokreslovan\'y vrchol sused\'i s viacer\'ymi vrcholmi, tak m\^o\v zeme h\v lada\v t spolo\v cn\'y prienik viacer\'ych 
oblast\'i (pre ka\v zd\'eho suseda jedna). Ak je ale po\v cet jeho susedov ve\v lk\'y, tak h\v ladanie najlep\v sieho 
prieniku m\^o\v ze by\v t a\v z exponencion\'alne. Aby sa tomu predi\v slo, tak pre vopred stanoven\'e pevn\'e $t$ vyberieme $t$ 
susedov a n\'ajdeme najlep\v s\'i prienik pre t\'ychto susedov (mo\v zu to  by\v t napr\'iklad susedia s najv\"a\v c\v s\'im stup\v nom).
%!
\item \v cas\v t: 
\newline
Ak u\v z m\'ame prienik vybrat\'y, tak vrchol do\v n umiestnime rovnak\'ym sp\^osobom ako v Heuristike 1. 
Pre vopred zvolen\'u kon\v stantu $k$ postupne vrchol umiestnime na $k$ n\'ahodn\'ych poz\'ici\'i vn\'utri prieniku a 
vyberieme umiestnenie, pri ktorom vzniklo najmenej kr\'i\v zen\'i. Ak je tak\'ych umiestnen\'i viac, 
tak vyberieme umiestnenie s najv\"a\v c\v sou vzdialenos\v tou od najbli\v z\v sieho vrchola p\^ovodn\'eho grafu.
%!
\end{enumerate}
%!
%!
\newtheorem{poc_oblasti}[oblast]{Veta}
\begin{poc_oblasti}
Po\v cet men\v s\'ich oblast\'i grafu $G$ s $n$ vrcholmi pre \v lubovo\v ln\'y vrchol $u$ je $O(n^3)$.
\end{poc_oblasti}
\begin{proof}
Ked\v ze m\'ame $n$ vrchlov, tak n\'am m\^o\v ze vznikn\'u\v t maxim\'alne $n-1$\\ ve\v lk\'ych oblast\'i. Maxim\'alny po\v cet hr\'an v grafe okrem hr\'an s vrcholom $u$ je $\frac{(n-1)*(n-2)}{2}$. Toto je aj maxim\'alny po\v cet hr\'an, ktor\'e m\^o\v zu zasahova\v t do jednej ve\v lkej oblasti, teda aj maxim\'alny po\v cet d\^ole\v zit\'ych bodov v tejto oblasti. Maxim\'alny po\v cet men\v s\'ich oblast\'i pre jednu ve\v lk\'u oblas\v t je potom $\frac{(n-1)*(n-2)}{2}+1$ a celkov\'y maxim\'alny po\v cet men\v s\'ich oblast\'i v celom grafe je $(\frac{(n-1)*(n-2)}{2}+1)*(n-1)$, \v co je  $O(n^3)$.
\end{proof}

\subsection{Porovnanie uveden\'ych heurist\'ik}
Najprv porovn\'ame tieto algoritmy z h\v ladiska \v casovej zlo\v zitosti. Oba algoritmy maj\'u spolo\v cn\'e, \v ze 
ich \v casov\'a zlo\v zitos\v t ve\v lmi z\'ale\v z\'i na tom, ak\'u \v strukt\'uru m\'a vstupn\'y graf a ak\'e vrcholy 
do grafu prid\'avame. Pre ka\v zd\'u heuristiku preto uvedieme  horn\'e ohrani\v cenie jej \v casovej zlo\v zitosti.\label{analyza}
\newline
\newline
\v Casov\'a zlo\v zitos\v t Heuristiky 1 : 
\newline
Najprv mus\'ime v danom grafe nahradi\v t kr\'i\v zenia hr\'an umel\'ymi vrcholmi. 
Zistenie \v ci sa dve hrany pret\'inaj\'u je $O(1)$. Po\v cet hr\'an v grafe je $O(n^2)$, preto zis\v tovanie, \v ci 
sa kri\v zuje niektor\'a dvojica hr\'an je $O(n^4)$. Toto je aj horn\'e ohrani\v cenie pre po\v cet kr\'i\v zen\'i. 
Pre ka\v zd\'u hranu si z\'arove\v n pam\"at\'ame, ktor\'e priese\v cn\'iky na nej le\v zia. Teraz ka\v zd\'u hranu 
nahrad\'ime nov\'ymi hranami, ktor\'e le\v zia medzi t\'ymito priese\v cn\'ikmi a koncov\'ymi vrcholmi hrany. 
Hr\'an je $O(n^2)$, maxim\'alny po\v cet priese\v cn\'ikov le\v ziacich na jednej hrane je $O(n^2)$, teda t\'ato transform\'acia hr\'an je $O(n^4)$. M\'ame teraz nov\'y graf, ktor\'y m\'a $O(n^4)$ vrcholov a $O(n^4)$ hr\'an.
\newline
Teraz mus\'ime n\'ajs\v t jednotliv\'e oblasti v tomto upravenom grafe. Ka\v zd\'a hrana sused\'i presne s dvoma 
oblas\v tami, teda ka\v zd\'u hranu 
nahrad\'ime dvoma navz\'ajom opa\v cne orientovan\'ymi hranami. 
Oblasti budeme kon\v struova\v t tak, \v ze najprv si vyberieme \v lubovoln\'u hranu a \v dal\v sie hrany budeme 
postupne prid\'ava\v t. \v Dal\v siu hranu prid\'ame t\'u, ktor\'a zviera s poslednou pridanou hranou najmen\v s\'i 
uhol v smere hodinov\'ych ru\v ci\v ciek. Hrany budeme prid\'ava\v t dovtedy, k\'ym medzi koncov\'ymi vrcholmi 
t\'ychto hr\'an nevznikne cyklus. Tento cyklus n\'am ohrani\v cuje nejak\'u oblas\v t v grafe, odstr\'anime ho z 
grafu (iba orientovan\'e hrany v jednom smere, po ktor\'ych sme prech\'adzali) a pokra\v cujeme v prid\'avan\'i hr\'an, 
dok\'ym nie s\'u z grafu odstr\'anen\'e v\v setky hrany. Takto postupne skon\v struujeme v\v setky oblasti. Po ka\v zdej 
hrane prech\'adzame 2-kr\'at, raz v ka\v zdom smere (hr\'an je $O(n^4)$), ke\v d vyber\'ame \v dal\v siu hranu, tak 
pozer\'ame $O(n^4)$ kandid\'atov, takisto aj ke\v d kontrolujeme, \v ci u\v z vznikol cyklus, tak pozer\'ame $O(n^4)$ 
vrcholov. Toto h\v ladanie oblast\'i je teda $O(n^8)$.
\newline
Pre ka\v zd\'u oblas\v t v grafe mus\'ime zisti\v t jej vrcholov\'u vzdialenos\v t od susedov dokres\v lovan\'eho vrchola. 
Hodilo by sa n\'am pozna\v t vzdialenos\v t v\v setk\'ych susedov dokres\v lovan\'eho vrchola od v\v setk\'ych vrcholov 
v grafe. Vzdialenos\v t vrchola od v\v setk\'ych ostatn\'ych vrcholov v grafe m\^o\v zeme zisti\v t Dijkstrovym algoritmom, 
ten m\'a \v casov\'u zlo\v zitos\v t $O(|V|^2)$, \v co je pri na\v som po\v cte vrcholov $O(n^8)$. Ked\v ze toto 
potrebujeme pre v\v setk\'ych susedov (t\'ych je $O(n)$), tak je to celkovo $O(n^9)$. S\'u\v cet vrcholov\'ych 
vzdialenost\'i susedov od oblasti zist\'ime tak, \v ze pre ka\v zd\'eho suseda ur\v c\'ime minimum z jeho vzdialenost\'i 
cez ka\v zd\'y vrchol ohrani\v cuj\'uci t\'uto oblas\v t. Po\v cet oblast\'i je $O(n^4)$, po\v cet vrcholov 
ohrani\v cuj\'ucich jednu oblas\v t je $O(n^4)$, po\v cet susedov dokres\v lovan\'eho vrchola je $O(n)$, teda celkovo 
je to $O(n^9)$.
\newline
Ke\v d u\v z pre ka\v zd\'u oblas\v t (je ich $O(n^4)$) m\'ame s\'u\v cet jej vzdialenost\'i od susedov dokres\v lovan\'eho 
vrchola, tak minimum z t\'ychto s\'u\v ctov n\'ajdeme v \v case $O(n^4)$. Teraz pre $r$ oblast\'i, ktor\'e maj\'u tento 
minim\'alny s\'u\v cet sk\'usime h\v lada\v t vhodn\'e umiestnenie dokres\v lovan\'eho vrchola. Budeme sk\'u\v sa\v t $k$ 
n\'ahodn\'ych umiestnen\'i. Pre ka\v zd\'e tak\'eto umiestnenie potrebujeme zisti\v t ko\v lko nov\'ych kr\'i\v zen\'i 
vznikne, ako aj vzdialenos\v t od najbli\v z\v sieho vrchola v p\^ovodnom grafe. Pre ka\v zd\'u hranu, ktor\'a vznikne 
pri dokreslen\'i tohoto nov\'eho vrchola ($O(n)$) zist\'ime \v ci pret\'ina nejak\'u p\^ovodn\'u hranu 
(t\'ych je $O(n^2)$), teda zistenie po\v ctu kr\'i\v zen\'i je $O(n^3)$. Zistenie vzdialenosti od najbli\v z\v sieho 
vrcholu p\^ovodn\'eho grafu je $O(n)$. Teda zistenie umiestnenia vrchola je celkovo $O(r*k) * O(n^3)$, \v co je $O(n^3)$.
\newline
\newline
\v Casov\'a zlo\v zitos\v t Heuristiky 2 : 
\newline
Najprv mus\'ime skon\v struova\v t l\'u\v ce. Skon\v struovanie l\'u\v cov pre jedn\'eho suseda $u$ dokres\v lovan\'eho 
vrchola je $O(n)$, preto\v ze l\'u\v c je veden\'y zo suseda cez ka\v zd\'y vrchol grafu, l\'u\v cov je $O(n)$. 
Potom l\'u\v ce usporiadame pod\v la toho, ak\'y uhol zvieraj\'u s osou $x$ v smere hodinov\'ych ru\v ci\v ciek. 
Usporiadanie $O(n)$ prvkov sa d\'a spravi\v t $O(n \log n)$ napr\'iklad quick-sortom. Tu z\'arove\v n odstr\'anime 
duplicitn\'e l\'u\v ce. Teraz m\^o\v zeme vytvori\v t ve\v lk\'e oblasti, tie bud\'u ohrani\v cen\'e dvojicou susedn\'ych 
l\'u\v cov (aj posledn\'y s prv\'ym), pokia\v l tieto l\'u\v ce zvieraj\'u uhol men\v s\'i ako $\pi$ v smere hodinov\'ych 
ru\v ci\v ciek. Vytvorenie ve\v lk\'ych oblast\'i je teda $O(n \log n)$.
\newline 
M\'ame vytvoren\'e ve\v lk\'e oblasti, teraz vytvor\'ime mal\'e. Najprv ur\v c\'ime d\^ole\v zit\'e body. Pre ka\v zd\'u 
hranu zist\'ime \v ci kri\v zuje oba hrani\v cn\'e l\'u\v ce, ak \'ano, tak ten priese\v cn\'ik ktor\'y je bli\v z\v sie 
k vrcholu $u$ prid\'ame do d\^ole\v zit\'ych bodov tejto oblasti. Ak u\v z m\'ame v\v setky d\^ole\v zit\'e body, 
tak ich usporiadame pod\v la vzdialenosti od vrchola $u$ vzostupne. Po\v cet d\^ole\v zit\'ych bodov je $O(n^2)$, ich 
usporiadanie quick-sortom je teda $O(n^2 \log(n^2))$, \v co je $O(n^3)$. Teraz u\v z m\^o\v zeme vytv\'ara\v t men\v sie 
oblasti. Prv\'a tak\'ato oblas\v t bude ohrani\v cen\'a bodmi $u$, prv\'ym d\^ole\v zit\'ym bodom a jeho obrazom na druhom 
l\'u\v ci (oba s\'u od $u$ rovnako vzdialen\'e), l\'u\v cov\'e \v c\'islo tejto oblasti bude $0$. \v Dal\v sia oblas\v t 
bude ohrani\v cen\'a prv\'ym d\^ole\v zit\'ym bodom, druh\'ym d\^ole\v zit\'ym bodom a ich obrazmi. Takto postupne 
kon\v struujeme oblasti, je ich $O(n^2)$, kon\v strukcia jedn\'eho je $O(1)$, teda celkovo vytvorenie men\v s\'ich 
oblast\'i z jednej ve\v lkej je $O(n^3)$. Ke\v d\v ze m\'ame $O(n)$ ve\v lk\'ych oblast\'i, tak vytvorenie men\v s\'ich 
oblast\'i pre jedn\'eho suseda dokres\v lovan\'eho vrchola je $O(n^4)$, pre $t$ susedov $O(n^4)$.
\newline
Pre jedn\'eho suseda m\'ame $O(n^3)$ men\v s\'ich oblast\'i, ak chceme pre dvoch susedov dokres\v lovan\'eho vrchola 
zisti\v t ktor\'e oblasti maj\'u prienik, tak mus\'ime vysk\'u\v sa\v t $O(n^3)*O(n^3)=O(n^6)$ dvoj\'ic. Zisti\v t 
prienik dvoch tak\'ychto oblast\'i sa d\'a v \v case $O(1)$, preto\v ze obe s\'u ohrani\v cen\'e maxim\'alne \v styrmi 
vrcholmi. Ak chceme zisti\v t spolo\v cn\'e prieniky od $t$ susedov, tak mus\'ime uva\v zova\v t $O(n^{3t})$ $t$-tic. 
\newline 
Ak m\'ame vybrat\'e prieniky, tak vrchol v nich umiest\v nujeme presne tak ako v Heuristike 1, \v co je 
$O(r*k)*O(n^3)= O(n^3)$.
\newline
\newline
Obidve heuristiky maj\'u ve\v lk\'u \v casov\'u zlo\v zitos\v t, Heuristika 1 $O(n^9)$, kde najn\'aro\v cnej\v sie \v casti 
s\'u h\v ladanie oblast\'i $(O(n^8))$ a h\v ladanie najkrat\v s\'ich ciest medzi vrcholmi $(O(n^9))$. Tieto oper\'acie s\'u preto tak \v casovo n\'aro\v cn\'e, preto\v ze s\'u aplikovan\'e na graf, ktor\'y m\'a $O(n^4)$ vrcholov a $O(n^4)$ hr\'an. Naproti tomu Heuristika 2 aby mala zmysel, tak mus\'i by\v t $t\geq 2$, pri\v com ak $t=2$, tak \v casov\'a zlo\v zitos\v t je $O(n^6)$. \v Casovo najn\'aro\v cnej\v sia oper\'acia je h\v ladanie prienikov medzi ka\v zd\'ymi dvoma men\v s\'imi oblas\v tami. 
Tieto zlo\v zitosti s\'u pri prid\'avan\'i jedn\'eho vrchola do grafu, ak prid\'avame viac vrcholov, tak sa daj\'u upravi\v t
niektor\'e \v casti heurist\'ik tak, aby sa zbyto\v cne ner\'atali tie ist\'e veci 2-kr\'at a t\'ym zn\'i\v zi\v t ich 
\v casov\'u zlo\v zitos\v t.
\newline 
\newline
Ak m\'a ka\v zd\'y z vrcholov kreslen\'eho grafu maxim\'alne kon\v stantn\'y po\v cet susedov $p$, tak \v casov\'e zlo\v zitosti
t\'ychto heurist\'ik s\'u nasledovn\'e : 
\newline
Heuristika 1 : 
\newline
Po\v cet hr\'an v grafe je $O(n)$, po\v cet kr\'i\v zen\'i $O(n^2)$, teda transform\'acia na plan\'arny 
graf je $O(n^2)$, vytvoren\'y graf m\'a $O(n^2)$ vrcholov a $O(n^2)$ hr\'an.
\newline
Pri kon\v struovan\'i oblast\'i prejdeme po ka\v zdej hrane 2-kr\'at ($O(n^2)$), pri prid\'avan\'i \v dal\v sej hrany a 
h\v ladan\'i cyklu kontrolujeme $O(n^2)$ hr\'an/vrcholov, teda celkovo $O(n^4)$.
\newline
Pri zis\v tovan\'i vrcholovej vzdialenosti zis\v tujeme vzdialenos\v t pre $O(p)$ vrcholov od ka\v zd\'eho vrcholu v grafe,
\v co je Dijkstrovym algoritmom $O(p) * O(n^2) * O(n^2) = O(n^4)$. S\'u\v cet vrcholov\'ych vzdialenost\'i oblast\'i od
susedov dokres\v lovan\'eho vrcholu je $O(n^4)$.
\newline
Ked\v ze m\'ame $O(n^2)$ oblast\'i, tak n\'ajdenie minim\'alneho s\'u\v ctu je $O(n^2)$, pri umiest\v novan\'i vrchola do
oblasti je zistenie po\v ctu kr\'i\v zen\'i $O(p)*O(n*p)=O(n)$, zistenie vzdialenosti od najbli\v z\v sieho vrchola je $O(n)$.
\newline
Celkov\'a zlo\v zitos\v t heuristiky je teda $O(n^4)$, kde znovu najn\'aro\v cnej\v sia oper\'acia na \v cas je zis\v tovanie
vrcholovej vzdialenosti. 
\newline
Heuristika 2 : 
\newline
Vytvorenie ve\v lk\'ych oblast\'i je $O(n \log n))$, tam sa ni\v c nezmen\'i. Po\v cet d\^ole\v zit\'ych
bodov pre jednu ve\v lk\'u oblas\v t je $O(n)$, ich usporiadanie je $O(n \log n)$. Vytvorenie mal\'ych oblast\'i z jednej 
ve\v lkej je $O(n \log n)$, pre $O(n)$ ve\v lk\'ych oblast\'i to je $O(n^2 \log n)$. 
\newline
Pre jedn\'eho suseda m\'ame $O(n^2)$ mal\'ych oblast\'i, zis\v tovanie prieniku po dvojiciach pre dvoch susedov je 
$O(n^2)*O(n^2)=O(n^4)$. Zis\v tovanie spolo\v cn\'ych prienikov pre $t$ susedov je $O(n^{2t})$.
\newline
Zis\v tovanie umiestnenia vrcholu vr\'amci vybrat\'eho prieniku je podobne ako v Heuristike 1 $O(n)$.
\newline
Celkov\'a \v casov\'a zlo\v zitos\v t heuristiky je $O(n^4)$ pre $t=2$, kde op\"a\v t \v casovo najn\'aro\v cnej\v sia 
oper\'acia je zis\v tovanie prienikov medzi oblas\v tami od dvoch susedov dokres\v lovan\'eho vrchola.
\newline
\newline
Implementa\v cne ove\v la \v ta\v z\v sie bolo naprogramova\v t Heuristiku 1, hlavne pretransformovanie p\^ovodn\'eho grafu na graf s umel\'ymi vrcholmi a h\v ladanie oblast\'i v tomto grafe. 
\newline
Porovnaniu t\'ychto dvoch heurist\'ik z h\v ladiska po\v ctu kr\'i\v zen\'i sa venujeme v \textbf{Kapitole 6}, strana~\pageref{porov}.
