\documentstyle[12pt]{letter}
\setlength{\textwidth}{14.7cm}
\setlength{\textheight}{24.5cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
\setlength{\topmargin}{-1.7cm}
\def\RR{\hbox{\boldmath{$R$}}}
\def\NP{\hbox{\bf NP}}
\def\PP{\hbox{\bf P}}

\begin{document}

\begin{center}
2. KOLOKVIJ IZ RA\v{C}UNALNI\v{S}TVA III \\[2mm]
12. maj 1994
\end{center}

\bigskip

{\bf 1.} \ 
Poi\v{s}\v{c}i minimalni $(s,t)$--prerez v naslednjem omre\v{z}ju:

\vskip 6.5cm

\bigskip

{\bf 2.} 
Imamo $n$ deklet $D_1,\dots,D_n$ in ravno toliko fantov, $F_1,\dots,F_n$.
\v Ce ple\v{s}eta $F_i$ in $D_j$, tedaj fant $F_i$ $c_{ij}$--krat
pohodi $D_j$. (\v Ce je $c_{ij}<0$, potem je seveda nerodno dekle.)
\v Zelimo sestaviti $n$ plesnih parov tako, da bo najbolj pohojena oseba 
\v{c}im manjkrat pohojena. Sestavi polinomski algoritem za ta problem
in oceni njegovo \v{c}asovno zahtevnost. 

\bigskip

{\bf 3.} 
Dan je graf $G$ in to\v{c}ki $a,b\in V(G)$. {\em Hamiltonov sprehod} v $G$
od $a$ do $b$ je sprehod, ki se za\v{c}ne v $a$, kon\v{c}a v $b$ in ki
obi\v{s}\v{c}e vse to\v{c}ke grafa. (Nekatere to\v{c}ke, lahko tudi $a$
ali $b$, so seveda lahko obiskane ve\v{c}krat. Tudi povezave lahko na sprehodu
ve\v{c}krat nastopijo.)

a) Ugotovi, kako te\v{z}ko je iskanje najkraj\v{s}ega Hamiltonovega
sprehoda med danima to\v{c}kama. ({\em Dol\v{z}ina} sprehoda je enaka
\v{s}tevilu povezav na sprehodu, \v{s}tetih ve\v{c}kratno glede na
\v{s}tevilo njihovih pojavitev na sprehodu.)

b) \v Ce v (a) nisi znal poiskati u\v{c}inkovitega postopka,
ali zna\v{s} najti kak\v{s}en aproksimacijski algoritem
(na primer 1-aproksimacijski)?

\end{document}