\documentclass[a4paper,12pt,oneside]{article}
\usepackage[latin2]{inputenc}
\usepackage{amssymb}
\setlength{\textwidth}{16.6cm} \setlength{\oddsidemargin}{-6mm}
\begin{document}
\pagestyle{empty}
\begin{center}
\large{\textbf{Számítástudomány elemei} gyakorlat\\
10. feladatsor (2002. nov. 14.)}
\end{center}
\ \\
\begin{enumerate}
\item Tegyük fel, hogy van egy $H$ eljárásunk, mely egy
tetszőleges $G$ input gráfra megmondja, hogy van-e $G$-ben
Hamilton-út. Tervezzünk olyan algoritmust, amely egy adott gráfban
a $H$ eljárást használva polinom sok lépésben talál egy
Hamilton-utat!\\
(Vizsga, 1999. máj.)

\item Mi az alábbi probléma bonyolultsága?\\
\textbf{Input:} $G$ egyszerű gráf.\\
\textbf{Kérdés:} Két részre oszthatók-e $G$ csúcsai úgy, hogy
mindkét rész egy-egy teljes részgráf legyen? (Vizsga, 1999. jún.)

\item Vezessük vissza polinomiális időben a Hamilton-kör
létezésének problémáját arra, hogy egy adott gráf pontjai
lefedhetők-e 100 (pont)diszjunkt körrel? (ZH, 2001. máj.)

\item Mi a bonyolultsága a következő feladatnak?\\
\textbf{Input:} egy $G$ gráf és egy $K$ pozitív egész szám.\\
\textbf{Kérdés:} Van-e $G$-nek olyan $F$ feszítőfája, amelyre $F$
páros fokú pontjainak száma legalább $K$? (Pótzh, 2001. máj.)

\item Keressük meg az alábbi számok legnagyobb közös osztóját az
euklideszi algoritmus segítségével!
\begin{enumerate}
\item $(7469,2464)$ \item $(2947,3997)$
\end{enumerate}

\item Milyen $x,y$ egész számokra teljesül, hogy $3x+5y=17$? (ZH,
2000. máj.)

\item Hány olyan $a,b\in\mathbb{N}$ pár van, melyre $(a,b)=12$ és
$[a,b]=240$? Soroljuk fel az összes lehetséges esetet!

\item Határozzuk meg az összes olyan $1<n\leq100$ egész számot,
amelyekre teljesül, hogy $n$ pozitív osztóinak száma háromnak egy
hatványa! (Pótzh, 2001. máj.)

\item Hány olyan osztója van a $2^5\cdot3^9\cdot5^5\cdot7^3$-nak,
ami 0-ra végződik? (Vizsga, 2000. dec.)

\item Jelölje $F_k$ a $k$-adik Fibonacci-számot, azaz legyen
$F_1=F_2=1$, és ha $n>2$, akkor $F_n=F_{n-1}+F_{n-2}$. Található-e
olyan $k$, hogy $F_k$ és $F_{k+2}$ is osztható hárommal?\\
(ZH, 1999. máj.)
\end{enumerate}
\end{document}
