Számítástudomány elemei gyakorlat
9. feladatsor (2002. nov. 7.)

1. Adjunk polinomrendű algoritmust annak eldöntésére, hogy egy $G$ gráfban $\alpha(G)\geq3$ teljesül-e?

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

3. Milyen bonyolultságú az alábbi feladat?
   Input: Egy $n$ pontú $G$ gráf.
   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.)

4. Bizonyítsd be, hogy az alábbi probléma NP-teljes!
   Input: Egy $G$ irányítatlan gráf és $K$ szám.
   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.)

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

6. Határozzuk meg a következő probléma bonyolultságát!
   Input: Egy $G(V,E)$ gráf és egy $A\subseteq V$ részhalmaza a csúcsainak.
   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.)

7. Mi a bonyolultsága az alábbi feladatnak?
   Input: Egy $G$ gráf.
   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?

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

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

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

Ajánlott feladatok a gyakorló példasorból: 14., 17., 25., 29., 33., 41., 42., 54.