Pótgyakorlat a hetedik gyakorlathoz
1. Igazoljuk, hogy a Karp redukció tranzitív, azaz: ha ![]() ![]() ![]() 2. Igazoljuk, hogy a 4 színnel színezhető irányítatlan gráfok nyelve NP-teljes! 3. Jelölje RH1 a részhalmaz-összeg probléma azon speciális esetét, melyben az első súly 1 (a tanult jelöléssel: s1=1). Igazoljuk, hogy az RH1 nyelv ![]() ![]() 4. Igazoljuk, hogy a Hamilton-út probléma NP-teljes! (Van-e G-ben ![]() 5. Mutassuk meg, hogy a ![]() 6. Igazoljuk, hogy a következő feladat P-beli: Adott egy G gráf és egy ![]() 7. Igazoljuk, hogy a következő feladat NP-nehéz: Adott egy G gráf és egy ![]() 8. Jelölje H a következő hipotézist: Az NP-teljes feladatok nem oldhatók meg O(1,2n)-nél kisebb lépésszámú algoritmussal, ahol n az input mérete. Mutassuk meg, hogy ha H igaz, akkor a következő feladat nem lehet NP-teljes: Input: Egy n csúcsú irányítatlan gráf G. Kérdés: Van-e G -ben legalább ![]() |