Next: About this document ...
Számítástudomány elemei gyakorlat
9. feladatsor (2002. nov. 7.)
- Adjunk polinomrendű algoritmust annak eldöntésére, hogy egy
gráfban
teljesül-e?
- Mi a bonyolultsága az alábbi feladatnak?
Input:
gráf és
pozitív egész szám.
Kérdés:
leghosszabb köre
-nál több élből áll-e?
(Vizsga, 1999. jún.)
- Milyen bonyolultságú az alábbi feladat?
Input: Egy
pontú
gráf.
Kérdés: Teljesül-e Ore feltétele, vagyis igaz-e, hogy
minden nem szomszédos
és
pontpárjára
teljesül? (ZH, 2000. máj.)
- Bizonyítsd be, hogy az alábbi probléma NP-teljes!
Input: Egy
irányítatlan gráf és
szám.
Kérdés: Van-e
-ben két olyan
-as klikk, amelyeknek
pontosan egy közös pontjuk van? (Vizsga, 2001. jún.)
- Legyen
olyan szubrutin, mely tetszőleges
pontú
gráfról eldönti, hogy van-e benne legalább
db független
pont. Készítsünk olyan algoritmust, amely
-nek polinom számú
hívásával talál ilyen független ponthalmazt, ha egyáltalán
létezik!
- Határozzuk meg a következő probléma bonyolultságát!
Input: Egy
gráf és egy
részhalmaza a csúcsainak.
Kérdés: Kiszínezhető-e
három színnel úgy, hogy az
-beli csúcsok színe azonos legyen? (ZH, 1999. máj.)
- Mi a bonyolultsága az alábbi feladatnak?
Input: Egy
gráf.
Kérdés: Kiszínezhető-e
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?
- Határozd meg a következő probléma bonyolultságát!
Input: Egy
egyszerű gráf, melyre
.
Kérdés: Tartalmaz-e
olyan kört, melynek hossza
pontosan
? (ZH, 2001. jan.)
- Milyen a bonyolultsága az alábbi feladatnak?
Input: Egy síkba rajzolható
gráf és
szám.
Kérdés: Van-e
-ben
méretű klikk? (ZH, 2002. máj.)
- 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.
Next: About this document ...
Veto Balint
2002-11-07