Kenar kapsama problemi

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 sınıfı içerisinde olduğu bilinmektedir. Amaç, bu problemin 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(n²) 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={(G,k)| G, k tane düğümlü bir köşe örtme alt kümesine sahip bir graftır.}} Buna göre; birer köşe örtme alt kümesine sahip olan graflardır.

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=(x₁ OR x₁ OR x₂)AND(!x₁ OR !x₂ OR !x₂)AND(!x₁ OR x₂ OR x₂)

ş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.

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; x₁ "YANLIŞ", x₂ "DOĞRU" seçilirse, o zaman yukarıdaki terimlerden !x₁ ve x₂ 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, x₁ ve x₂ değerlerinin şart cümlecikleri içerisinde yerine konulmasıyla da şart cümleciklerinin her birinin 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.

(x₁ OR x₁ OR x₂)=(YANLIŞ OR YANLIŞ OR DOĞRU) =DOĞRU

(!x₁ OR !x₂ OR !x₂)=(DOĞRU OR YANLIŞ OR YANLIŞ)=DOĞRU

(!x₁ OR x₂ OR x₂)=(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.

Kaynakça

• Michael Sipser (2006) Introduction to the Theory of Computation, Second Edition, Thomson Course Technology, Boston, MA, ISBN 0-534-95097-3. The problem is defined on pp. 284–286
• Greg Aloupis,A Sample Proof of NP-Completeness16 Ağustos 2009 tarihinde Wayback Machine sitesinde arşivlendi.
• Vertex cover 29 Mart 2010 tarihinde Wayback Machine sitesinde arşivlendi.