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

\setassignment{11}
\setexercise{1}
\setduedate{21}{12}{2015}
\setpoints{2}

\newcommand{\clique}[1]{\ensuremath{#1\text{-}\mathrm{CLIQUE}}}
\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 neorientovaném grafu
  existují alespoň 2 různé $k$-kliky (dva úplné podgrafy s $k$ vrcholy
  lišící se alespoň jedním vrcholem), je \NP-těžký. Jinak řečeno,
  dokažte, že jazyk \clique{2} definovaný níže zadává \NP-těžký
  problém.
  \[
  \clique{2} = \{ \langle G, k \rangle \mid G\text{ je
    neorientovaný graf
    obsahující alespoň 2 různé } k \text{-kliky} \}
  \]

  \noindent
  V důkazu můžete využít faktu, že problém kliky (definovaný níže)
  je \mbox{\NP-úplný}:
  \[
  \mathrm{CLIQUE} = \{ \langle G, k \rangle \mid{} G \text{ je
    neorientovaný graf obsahující } k \text{-kliku} \}.
  \]

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

  \begin{bonus}{1}
    Dokažte, že jazyk \clique{n} definovaný níže je \NP-úplný pro
    libovolné $n \ge 1$:
    \[
    \clique{n} = \{ \langle G, k \rangle \mid G\text{ je neorientovaný
      graf obsahující alespoň } n \text{ různých } k \text{-klik} \}.
    \]
  \end{bonus}
\end{zadani}


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

\end{document}
