\documentclass[a4paper,10pt]{article}
\usepackage[latin2]{inputenc}
\addtolength{\textwidth}{4cm} \addtolength{\oddsidemargin}{-2.3cm}
\begin{document}
\pagestyle{empty}
\begin{center}
\large{\textbf{Számítástudomány elemei} gyakorlat\\
9. feladatsor (2002. nov. 7.)}
\end{center}
\ \\
\begin{enumerate}
\item Adjunk polinomrendű algoritmust annak eldöntésére, hogy egy
$G$ gráfban $\alpha(G)\geq3$ teljesül-e?

\item Mi a bonyolultsága az alábbi feladatnak?\\
\textbf{Input:} $G$ gráf és $k$ pozitív egész szám.\\
\textbf{Kérdés:} $G$ leghosszabb köre $k$-nál több élből áll-e?
(Vizsga, 1999. jún.)

\item Milyen bonyolultságú az alábbi feladat?\\
\textbf{Input:} Egy $n$ pontú $G$ gráf.\\
\textbf{Kérdés:} Teljesül-e Ore feltétele, vagyis igaz-e, hogy $G$
minden nem szomszédos $u$ és $v$ pontpárjára $d(u)+d(v)\geq n$
teljesül? (ZH, 2000. máj.)

\item Bizonyítsd be, hogy az alábbi probléma \textbf{NP}-teljes!\\
\textbf{Input:} Egy $G$ irányítatlan gráf és $K$ szám.\\
\textbf{Kérdés:} Van-e $G$-ben két olyan $K$-as klikk, amelyeknek
pontosan egy közös pontjuk van? (Vizsga, 2001. jún.)

\item Legyen $S$ olyan szubrutin, mely tetszőleges $n$ pontú
gráfról eldönti, hogy van-e benne legalább $\frac n2$ db független
pont. Készítsünk olyan algoritmust, amely $S$-nek polinom számú
hívásával talál ilyen független ponthalmazt, ha egyáltalán
létezik!

\item Határozzuk meg a következő probléma bonyolultságát!\\
\textbf{Input:} Egy $G(V,E)$ gráf és egy $A\subseteq V$ részhalmaza a csúcsainak.\\
\textbf{Kérdés:} Kiszínezhető-e $G$ három színnel úgy, hogy az
$A$-beli csúcsok színe azonos legyen? (ZH, 1999. máj.)

\item Mi a bonyolultsága az alábbi feladatnak?\\
\textbf{Input:} Egy $G$ gráf.\\
\textbf{Kérdés:} Kiszínezhető-e $G$ négy színnel úgy, hogy a
színek közül kettőt csak legfeljebb két-két pont színezésére
használunk?

\item Határozd meg a következő probléma bonyolultságát!\\
\textbf{Input:} Egy $G$ egyszerű gráf, melyre $|V(G)|=5n$.\\
\textbf{Kérdés:} Tartalmaz-e $G$ olyan kört, melynek hossza
pontosan $n$? (ZH, 2001. jan.)

\item Milyen a bonyolultsága az alábbi feladatnak?\\
\textbf{Input:} Egy síkba rajzolható $G$ gráf és $k$ szám.\\
\textbf{Kérdés:} Van-e $G$-ben $k$ méretű klikk? (ZH, 2002. máj.)

\item Egy labdarúgó bajnokságban 10 csapat játszik körmérkőzést.
Minden fordulóban minden csapat pályára lép. Igazoljuk, hogy a
4.~forduló után van három olyan csapat, amelyik egyike sem
játszott még a másikkal! (A feladatra nov.~14-ig beadott helyes
megoldás csokit ér!)
\end{enumerate}
\ \\
Ajánlott feladatok a gyakorló példasorból: \textbf{14., 17., 25.,
29., 33., 41., 42., 54.}
\end{document}
