Minimum tepe örtüsü problemi üzerine
On minimum vertex cover problem
- Tez No: 371432
- Danışmanlar: YRD. DOÇ. DR. ELGİN KILIÇ, PROF. DR. ALPAY KIRLANGIÇ
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Minimum vertex cover problem, Approximation algorithm, Cartesian product, Binomial trees, Greedy algorithm
- Yıl: 2014
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 91
Ö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ı.
Özet (Çeviri)
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”.
Benzer Tezler
- Minimum tepe örtüsü problemi üzerine
On the minimum vertex cover problem
ONUR UĞURLU
Yüksek Lisans
Türkçe
2013
MatematikEge ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. URFAT NURİYEV
YRD. DOÇ. DR. MURAT ERŞEN BERBERLER
- Çizge teoride ortalama zedelenebilirlik parametreleri üzerine
On average vulnerability parameters in graph theory
AYŞE TEZEL YOLCU
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolManisa Celal Bayar ÜniversitesiYazılım Mühendisliği Ana Bilim Dalı
PROF. ERSİN ASLAN
- Güneş lekesi çevrim süreci içerinde kozmik ışınların yeryüzü iklimi-bulut örtüsü ile olan ilişkisinin incelenmesi
The influence of cosmic rays on climate and cloudiness in sunspots cycle
MEHMET ENDER AKCAN
Yüksek Lisans
Türkçe
2004
Meteorolojiİstanbul Teknik ÜniversitesiMeteoroloji Mühendisliği Ana Bilim Dalı
PROF.DR. YURDANUR TULUNAY
Y.DOÇ.DR. SİBEL MENTEŞ
- Amasya Ovası ve yakın çevresinin fiziki coğrafyası
The Geography of physical survey in Amasya plain and its environment
HALİL İBRAHİM ZEYBEK