Számítástudomány elemei gyakorlat
10. feladatsor (2002. nov. 14.)

1. 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.)

2. Mi az alábbi probléma bonyolultsága?
   Input: $G$ egyszerű gráf.
   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.)

3. 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.)

4. Mi a bonyolultsága a következő feladatnak?
   Input: egy $G$ gráf és egy $K$ pozitív egész szám.
   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.)

5. Keressük meg az alábbi számok legnagyobb közös osztóját az euklideszi algoritmus segítségével!
   1. $(7469,2464)$
   2. $(2947,3997)$

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

7. 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!

8. 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.)

9. 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.)

10. 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.)