\documentclass[12pt]{ib102}
\usepackage[czech]{babel}

\setassignment{11}
\setexercise{1}
\setduedate{15}{12}{2014}
\setpoints{2}

\newcommand{\hampath}[1]{\ensuremath{#1\text{-}\mathrm{HAMPATH}}}
\newcommand{\NP}{\ensuremath{\mathsf{NP}}}

%%% ZDE NAPISTE SVOJE UCO, JMENO A SKUPINU
\setstudent{}
\setgroup{}
\setuco{}


\begin{document}
\begin{zadani}
Dokažte, že problém rozhodnout, zda v daném orientovaném grafu existují
alespoň 2 různé hamiltonovské cesty z vrcholu $s$ do vrcholu $t$ (lišící se alespoň jednou hranou),
je \NP-těžký. Jinak řečeno, dokažte, že jazyk \hampath{2} definovaný
níže zadává \NP-těžký problém.
\begin{align*}
\hampath{2} = \{ \langle G, s, t \rangle \mid{} &G\text{ je orientovaný graf
obsahující alespoň 2 různé}\\
    &\text{hamiltonovské cesty z } s \text{ do } t \}
\end{align*}

\noindent
V důkazu můžete využít faktu, že problém hamiltonovské cesty (definovaný níže) je \mbox{\NP-úplný}:
$$ \mathrm{HAMPATH} = \{ \langle G, s, t \rangle \mid{} G \text{ je orientovaný graf obsahující hamiltonovskou cestu z } s \text{ do } t \}\text{.}$$

\bigskip
\begin{bonus}{1}
Dokažte, že problém \hampath{2} je dokonce \NP-úplný. Tedy dokažte navíc, že
$\hampath{2} \in \NP$.
\end{bonus}

\begin{bonus}{1}
Dokažte, že jazyk \hampath{k} definovaný níže je \NP-úplný pro libovolné $k \ge 1$:
\begin{align*}
\hampath{k} = \{ \langle G, s, t \rangle \mid{} &G\text{ je orientovaný graf
obsahující alespoň } k \text{ různých}\\
    &\text{hamiltonovských cest z } s \text{ do } t \}
\end{align*}
\end{bonus}

\end{zadani}


\begin{reseni}
%%% SEM PISTE SVE RESENI
\end{reseni}

\end{document}
