Minimum tepe örtüsü problemi üzerine
On minimum vertex cover problem
Yazar: SEMİHA EMİNOĞLU
Danışman: YRD. DOÇ. DR. ELGİN KILIÇ ; PROF. DR. ALPAY KIRLANGIÇ
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı
Derece: Yüksek Lisans, 2014
Konu: Matematik = Mathematics

Özet:
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 kulllanı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"  "×" "B" _"3"   den  "B" _"2"  "×" "B" _"6"   ye kadar yapılan işlemlerde optimal sonuca ulaştığı gözlenmiştir.
Anahtar Sözcükler : Tepe örtüsü problemi, Yaklaşık algoritma, Kartezyen çarpım, İkili ağaç,  Greedy algoritması.

Abstract:
Minimum vertex cover problem (one of the most known graph theory problems) has been studied on looples, connected and undirected graps. Let G be a graph "G=(V,E)" . The subset "C"⊆"V"   which contains at least one end of each "(u,v)"∈"E"     is called vertex cover of graph G. In minimum vertex cover problem it is desired to find vertex cover set which has the smallest cardinality.	Minimum vertex cover problem is Np-Complete problem and no polynomial time algorithm is known.The relation between minimum vertex cover problem and other problems in NP-Complete class are examined. The results previously given for the independence number is also used for vertex covering number.
The relation between vertex covering number  and independence number of graphs obtained by binary operations such as strong product, tensor product, lexicographic product, cartesian product are examined. Especially the existing results obtained by cartesian products for vertex covering and independence number is the main part of this thesis. By using the existing results of cartesian product related to independence number, the vertex covering number of  resulting graphs obtained by cartesian product of binary trees has been examined. Clever greedy is used for finding the vertex covering number of these graphs. Even if the optimal result is not guaranteed by greedy algorithms, it has been observed that optimal outcomes are found for the cartesian products of binary trees from "B" _"2"  "×" "B" _"3"   to "B" _"2"  "×" "B" _"6" .
Keywords: Minimum vertex cover problem, Approximation algorithm, Cartesian product, Binomial trees, Greedy algorithm.