\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{amsmath}
\usepackage[magyar]{babel}
\usepackage{graphics}
\usepackage{epic}
\usepackage{eepic}
\usepackage{color}
\usepackage{amssymb}

\setlength{\hoffset}{-1 cm}
\setlength{\voffset}{-2 cm}
\addtolength{\textwidth}{2 cm}
\addtolength{\textheight}{4 cm}

\begin{document}

\begin{center}
{\Large \bf 
Számítástudomány elemei\\
10. gyakorlat
}
\end{center}

\large

\begin{enumerate}

\item Adjunk algoritmust annak eldöntésére, hogy egy $G$ gráf
kiszínezhető-e 3 színnel!

\item Mutassuk meg, hogy a Hamilton-kör keresésének problémája polinom
időben megoldható olyan gráfok esetén, amelyeknek legfeljebb $n+10$
élük van!

\item Mi a bonyolultsága a következő feladatnak:\\
Bemenet: egy $G(V,E)$ gráf és egy $A\subseteq V$ részhalmaza a
pontjainak\\
Kérdés: Kiszínezhetők-e $G$ pontjai 3 színnel úgy, hogy az $A$-beli
csúcsok azonos színűek legyenek?

\item Mi az alábbi probléma bonyolultsága: Adott egy $G$ egyszerű
gráf, kérdés, hogy két részre oszthatóak-e a csúcsai úgy, hogy a két
rész egy-egy teljes részgráf legyen.

\item Mi az alábbi probléma bonyolultsága: adott egy $G$ gráf és egy
$k$ természetes szám, eldöntendő, hogy a $G$ leghosszabb köre legalább
$k$ élet tartalmaz-e.

\item Tegyük fel, hogy van egy $H$ eljárásunk, amely egy tetszőleges
$G$ gráfra megmondja, hogy van-e benne Hamilton-út! Tervezzünk ennek
felhasználásával olyan algoritmust, amely polinomiális időben megad
egy Hamilton-utat (ha van)!

\item Igazoljuk, hogy a Hamilton-út probléma NP-teljes.

\item Bizonyítsuk be, hogy a következő probléma NP-teljes: Adott egy G
gráf és egy $k$ természetes szám, van-e a $G$ gráfban egy legalább $k$
méretű két színnel színezhető feszített részgráf? (Útmutatás: vezessük
vissza rá a MAXFTLN feladatot.)

\end{enumerate}

\end{document}
