Minimum tepe örtüsü problemi üzerine

Minimum tepe örtüsü problemi (en çok bilinen graf problemlerinden biri ) döngü içermeyen, birleştirilmiş, yönsüz graflar üzerinde çalışılmıştır. "G=(V,E)" bir graf olsun. G grafının, her bir "(u,v)"ϵ"E" ayrıtının en az bir uç noktasını içeren, "C"⊆"V" kümesine, G grafının tepe örtüsü (vertex cover) kümesi denir. Minimum tepe örtüsü probleminde bu kümenin en küçük boyutta olanı bulunmak istenir.Minimum tepe örtüsü problemi Np-Tamdır ve bu problem için polinom zamanlı algoritma yoktur. Minimum tepe örtüsü probleminin Np-Tam sınıftaki diğer problemlerle de ilişkisi bu tezde incelenmiştir. Özellikle tepe örtüsü sayısı ile bağımsızlık sayısı arasındaki ilişki üzerinde durulmuştur. Bağımsızlık sayısı için var olan sonuçlar, tepe örtü sayısı için de kullanılmıştır. Güçlü çarpım, tensör çarpım, lexicografik çarpım, kartezyen çarpım gibi ikili işlemler sonucu oluşan grafların, tepe örtü ve bağımsızlık sayıları arasındaki ilişki incelenmiştir. Özellikle de herhangi iki grafın kartezyen çarpımıyla oluşan grafın tepe örtüsü ve bağımsızlık sayısı arasındaki ilişki bu tez çalışmasının ana kısmını oluşturmuştur. Bağımsızlık sayısına ilişkin var olan kartezyen çarpım sonuçları kullanılarak, ikili ağaçların kartezyen çarpımıyla oluşan grafın tepe örtüsü sayısı incelenmiştir. Bu grafların tepe örtüsü sayısını bulmak için zeki greedy (aç gözlü yaklaşım) algoritması kullanılmıştır. Bu algoritmanın optimal sonucu garanti etmediği halde, "B"_"2" x "B"_"3" den "B"_"2" x "B"_"6" ye kadar yapılan işlemlerde optimal sonuca ulaştığı gözlenmiştir.