- Katılım
- 7 Eyl 2009
- Konular
- 6,986
- Mesajlar
- 38,038
- Çözüm
- 1
- Online süresi
- 7d 22h
- Reaksiyon Skoru
- 1,833
- Altın Konu
- 0
- Başarım Puanı
- 494
- MmoLira
- 6,600
- DevLira
- 0
HERAKLES Otomatik Avlı kalıcı sunucu. 19 Haziran'da açılıyor. Atius & Wizard güvencesiyle hemen kayıt ol, ön kayıt ödülleri aktif. HEMEN TIKLA!
Köşe Örtme (İngilizce: Vertex Cover), bir çizge (graf) içerisindeki tüm kenarların en az sayıda seçilebilecek düğüm ile kapsanabilir olup olmadığının bulunması problemidir. Bu problemin [NP (karmaşıklık)|NP] sınıfı içerisinde olduğu bilinmektedir. Amaç, bu problemin [NP (karmaşıklık)|NP-Tam] sınıfında olup olmadığının ispatıdır.
Köşe Örtme probleminin NP sınıfı içerisinde olduğu zaten görülmektedir. Çünkü NP sınıfındaki bir probleme ilişkin verilen bir çözümün polinom zamanda doğru olup olmadığını tespit etmek mümkündür. Örneğin verilen bir grafın içinde tüm kenarları kapsayan bir alt küme olduğunu iddia eden bir çözümün doğruluğu için O(n2) zaman yeterlidir. Bu çözüm için iç içe iki tane döngü içerisinde düğümler arasındaki ilişkiyi izlemek yeterlidir.
Köşe Örtme probleminin NP sınıfı içerisinde olduğu zaten görülmektedir. Çünkü NP sınıfındaki bir probleme ilişkin verilen bir çözümün polinom zamanda doğru olup olmadığını tespit etmek mümkündür. Örneğin verilen bir grafın içinde tüm kenarları kapsayan bir alt küme olduğunu iddia eden bir çözümün doğruluğu için O(n2) zaman yeterlidir. Bu çözüm için iç içe iki tane döngü içerisinde düğümler arasındaki ilişkiyi izlemek yeterlidir.
