bakimliyiz
Sponsor Reklamlar
Geri git   Bakimliyiz.Com > GENEL KÜLTÜR > Eğitim ve Öğretim

Kadın Portalı Kayıt Ol İletişim Forumları Okundu Kabul Et
Alt 24-05-2013, 04:54   #1 (permalink)
 
ebush - ait Kullanıcı Resmi (Avatar)
 
Standart Kenar kapsama problemleri ve çözümleri

Kenar kapsama problemleri ve çözümleri


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.


Tanım

Köşe Örtme={(Gk)| G k tane düğümlü bir köşe örtme alt kümesine sahip bir graftır.} Buna göre;



Kenar kapsama problemleri ve çözümleri


Köşe örtme Probleminin NP-Tam İçinde Yer Aldığının İspatı

Bir problemin NP-Tam olduğunu ispat etmek için daha önce NP-Tam olduğu bilinen bir problemin bu probleme polinom zamanda indirgeniyor olduğunu ispat etmek yeterlidir.
Bunun için 3SAT probleminin NP-Tam olduğunun bilinmesinden yola çıkarak 3SAT <p köşe örtme(Vertex Cover) ispat edilmesi halinde köşe örtme probleminin de NP-Tam olduğu ispatlanmış olur.


Bunun için öncelikle 3SAT probleminin her bir şart cümleciğinin k tane terim ile gösteriliyor olduğunu bilmek gerekmektedir. Örneğin;


f=(x1 OR x1 OR x2)AND(!x1 OR !x2 OR !x2)AND(!x1 OR x2 OR x2)

şeklinde verilmiş 3SAT problemine uygun bir formülü graf şekline
çevirmek gerekmektedir. Böylece bir 3SAT problemi graf haline çevrilmiş
olur. Yukarıda verilmiş formülün graf haline çevrilmesi esnasında şu yol
izlenmektedir. Önce şart cümlecikleri içinde geçen terimler ile o terimlerin "DEĞİL" leri arasında bir kenar oluşturacak şekilde graf çizilmeye başlanır. Daha sonra şart cümleciklerini de grafa ekleyerek aynı terimleri birbirine bağlayarak graf oluşturulur. Buna göre m terim sayısı l şart cümleciği sayısı olarak düşünülürse 2m+3l tane düğümden oluşan bir graf ortaya çıkar. Verilen grafın içinden tüm köşeleri örtme bir düğüm alt kümesinin eleman sayısını da m+2l olarak farzedelim.


Kenar kapsama problemleri ve çözümleri

Buradaki örnekte k=8 olarak bulunur.


Bundan sonraki adım ise köşe örtme algoritmasını gerçekleyecek ve bu koşulları olumlu olarak mantıksal doğrulanabilir sağlayacak bir karşılanabilirlik ifadesi çıkarılır. Bunun için önce grafta terimlere "doğru" karşılık gelecek kısımları seçilir. Daha sonra bu seçimin ardından şart cümleciklerinin içinden öylesine ikişer tane düğüm seçilir ki hem grafın kenarlarının tamamı kapsanabilir olur hem de formülde verilen şart cümleciklerinin her birisi mantıksal doğrulanabilir olur. Bunun için eğer; x1 "YANLIŞ" x2 "DOĞRU" seçilirse o zaman yukarıdaki terimlerden !x12 seçilip aşağıdaki şart cümleciklerinden de taralı kısımların seçilmesiyle graftaki tüm köşe örtme olmasının yanı sıra x1 ve x2 değerlerinin şart cümlecikleri içerisinde yerine konulmasıyla da şart cümleciklerinin herbirinin mantıksal doğrulanaiblir olduğu görülür. Tüm bu işlemlerin yapılması polinom zamanda gerçeklenebildiğinden 3SAT problemini polinom zamanda köşe örtme problemi haline dönüşebildiğinden köşe örtme problemi de NP-Tam sınıfındadır. ve x


(x1 OR x1 OR x2)=(YANLIŞ OR YANLIŞ OR DOĞRU) =DOĞRU
(!x1 OR !x2 OR !x2)=(DOĞRU OR YANLIŞ OR YANLIŞ)=DOĞRU
(!x1 OR x2 OR x2)=(DOĞRU OR DOĞRU OR DOĞRU)=DOĞRU


Böylece yukarıdaki tüm şart cümlecikleri mantıksal doğrulanabilir olmasının yanı sıra graf üzerinde 8 tane düğümün seçilerek tüm
köşeleri örten bir alt küme bulunmuş olur.


Buna göre oluşan grafın son hali aşağıdaki şekilde gösterildiği gibi olmaktadır.

Kenar kapsama problemleri ve çözümleri


ebush isimli Üye şimdilik offline konumundadır  





Hızlı Cevap

Doğrulama Sorusu
Mesajınız:
Yazı şeklini sil
Kalın
Eğik yazı
Altı çizik

Grafik ekle
Alıntı yap [QUOTE]
 
Alanı Küçült
Alanı Büyült

Seçenekler
Stil


Kenar kapsama problemleri ve çözümleri

Kenar kapsama problemleri ve çözümleri konusu, GENEL KÜLTÜR / Eğitim ve Öğretim forumunda tartışılıyor.



Benzer Konular

Konu Konuyu Başlatan Forum Cevap Son Mesaj
Aritmetik Ortalama Problemleri ve Çözümleri elif Matematik 5 31-03-2017 08:05
Kuvvet problemleri soru ve çözümleri ebush Eğitim ve Öğretim 0 06-05-2013 01:52
Aritmetik Ortalama Problemleri ve Çözümleri elif Soru Cevap 0 18-04-2013 03:00
Kat problemleri ve çözümleri Я Soru Cevap 0 21-02-2012 10:36
Çocukluk dönemi beslenme problemleri ve çözümleri daywest Bebek Bakımı 0 21-03-2010 04:04

Üye olmadan soru sorabilirsiniz!

Bütün Zaman Ayarları WEZ +4 olarak düzenlenmiştir. Saat şuan 06:49 .


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
SEO by vBSEO 3.5.2 ©2010, Crawlability, Inc.
Web Stats