Geri Dön

Minimum tepe örtüsü problemi üzerine

On minimum vertex cover problem

  1. Tez No: 371432
  2. Yazar: SEMİHA EMİNOĞLU
  3. Danışmanlar: YRD. DOÇ. DR. ELGİN KILIÇ, PROF. DR. ALPAY KIRLANGIÇ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Minimum vertex cover problem, Approximation algorithm, Cartesian product, Binomial trees, Greedy algorithm
  7. Yıl: 2014
  8. Dil: Türkçe
  9. Üniversite: Ege Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Minimum tepe örtüsü problemi üzerine

    On the minimum vertex cover problem

    ONUR UĞURLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    MatematikEge Üniversitesi

    Matematik Ana Bilim Dalı

    PROF. DR. URFAT NURİYEV

    YRD. DOÇ. DR. MURAT ERŞEN BERBERLER

  2. Çizge teoride ortalama zedelenebilirlik parametreleri üzerine

    On average vulnerability parameters in graph theory

    AYŞE TEZEL YOLCU

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolManisa Celal Bayar Üniversitesi

    Yazılım Mühendisliği Ana Bilim Dalı

    PROF. ERSİN ASLAN

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

    Türkçe

    2004

    Meteorolojiİstanbul Teknik Üniversitesi

    Meteoroloji Mühendisliği Ana Bilim Dalı

    PROF.DR. YURDANUR TULUNAY

    Y.DOÇ.DR. SİBEL MENTEŞ

  4. Balıkesir'de çevre sorunları

    Başlık çevirisi yok

    NECDET EREN

    Yüksek Lisans

    Türkçe

    Türkçe

    1995

    Coğrafyaİstanbul Üniversitesi

    PROF.DR. BARIŞ MATER

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

    Doktora

    Türkçe

    Türkçe

    1998

    CoğrafyaOndokuz Mayıs Üniversitesi

    Coğrafya Ana Bilim Dalı

    DOÇ. DR. ALİ UZUN