Geri Dön

Çizgelerde yol-eşleme ve renklendirme

Path-matching and coloring in graphs

  1. Tez No: 318177
  2. Yazar: ZAKİR DENİZ
  3. Danışmanlar: DOÇ. DR. YUSUF CİVAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2012
  8. Dil: Türkçe
  9. Üniversite: Süleyman Demirel Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 58

Özet

Bu tezde, çizgelerde yol-bileşen, yol-eşleme ve renklendirme konusu ele alınmıştır. Çalışmanın amacı, çizgelerde yol-bileşen ve eşleme kavramlarının ele alınıp, çizgelerde renklendirme ile ilgili bilinen bazı teorem ve savlar hakkında yeni bulgular ortaya koymaktır.Çalışma altı bölümden oluşmaktadır ve her bir bölüm, okuyucunun çizgelerde yol-bileşen, eşleme ve renklendirme kavramları arasındaki ilişkileri anlayabileceği şekilde hazırlanmıştır. İlk bölümde, kullanılan tüm notasyonlar ile birlikte temel motivasyonumuz açık bir şekilde ifade edilmiştir. Ayrıca elde ettiğimiz yeni sonuçlar listelenmişir. İkinci bölümde ise bu çalışma boyunca ihtiyaç duyduğumuz bazı temel tanım ve kavramlara yer verilmiştir.Üçüncü ve dördüncü bölümlerde, çizgelerde eşleme ve bileşen konusu ele alınmıştır. Özellikle dördüncü bölümde, tüm regüler çizgeler için (P_2,P_3)-bileşenin mevcut olduğu ispatlanmıştır. Bu sonuç yardımıyla herhangi bir çizgede tüm maksimum dereceli köşeleri doyuran bir yol-eşlemenin mümkün olduğu ispatlanmıştır. Bu bölümde ek olarak, yol-eşleme kavramının maksimize edilmesiyle, herhangi bir çizgeden maksimal yol-eşlemenin çıkarılması durumunda maksimum derecenin en az bir 1 azalması sonucu elde edilmiştir. Bu gerçek, König ve Vizing Teoremlerinin alternatif birer ispatlarının verilmesini sağlamıştır. Böyle bir yaklaşım iyi bilinen Total Renklendirme Savının özel bir durumunu kanıtlamamıza olanak vermiştir. Tezin kalan kısmında Reed & Kostachka Savı ele alınmıştır. i(G), bağımsız baskınlık sayısı olmak üzere, üçgen-yoksun bir G çizgesinin köşe kromatik sayısı için i(G)+1 olacak şekilde bir üst sınır elde edilmiştir. Bunun yanı sıra üçgen-yoksun çizgeler üzerinde bir algoritma (Return Algorithm) geliştirerek iyileştirilmiş bir üst sınır verilmiştir. Bu sonuç, i(G) ? ?/2+1 olan üçgen-yoksun çizgeler için Reed Savının doğruluğunu ispat etmektedir.Sonuç bölümünde, elde edilen sonuçlar değerlendirilmiştir. Ayrıca bazı açık problemler ve ileride mümkün olabilecek projeler ifade edilmiştir.

Özet (Çeviri)

In this thesis, path-factor, path-matching and graph coloring are studied. Aim of this work is to examine the notions of path-factor and matching in graphs, and to present some new findings related to some well-known theorems and conjectures in graph theory.This study consists of six chapters, and each chapter prepares its readers to understand the interrelations of path-factor, matching and coloring of graphs. In the first chapter, we explicitly describe our motivation to study these notions all together. There, we also list some of the new results of this thesis. The second chapter provides some of the basic definitions and known results that are needed throughout the thesis.In chapters three and four, we study matchings and factors in graphs. In particular, the existence of (P_2,P_3)-factor for all regular graphs is proven in chapter four. With the help of this result, we are able to show that there exists a path-matching in any graph that saturates all vertices of maximum degree. Additionally, by maximizing the existing path-matching we conclude that the maximum degree of any graph can be reduced at least by one if we remove the maximal path-matching. This fact enables us to supply alternative proofs of classical theorems of König and Vizing on edge colorings of graphs. Such an approach permits us to prove a special case of the well-known Total Coloring Conjecture. The remainder of this thesis deals with Kostachka & Reed's Conjecture. We prove that the (vertex) chromatic number of triangle free graphs is always bounded above by i(G)+1, where i(G) is the independent domination number of G. Furthermore, we provide an algorithm (Return Algorithm) on triangle free graphs that enables to test tightness of the stated upper bound. This result also shows the accuracy of Reed?s conjecture for all triangle-free graphs with i(G) ? ?/2+1.In the conclusion chapter, we review the results of this thesis. We there also state some open problems and possible future projects.

Benzer Tezler

  1. Resource mapping optimization for distributed cloud services

    Dağıtık bulut hizmetleri için kaynak eşlemenin iyileştirilmesi

    ATAKAN ARAL

    Doktora

    İngilizce

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. TOLGA OVATMAN

  2. Studien zur literadur und kultur auffassung Friedrich Nietzsche und ihre wiederspiegelung in der Deutschen literadur anhand von Thomas Manns 'Doktor Faustus'

    Friedrich Nietzsche'nin edebiyat ve kültür anlayışı ve Thomas Mann'ın 'Doktor Faustus' adlı eserini örnek alarak bu anlayışın Alman edebiyatına olan etkisi

    NİLGÜN TÜRKER (MANİSA)

    Doktora

    Almanca

    Almanca

    1995

    Alman Dili ve EdebiyatıUludağ Üniversitesi

    PROF.DR. İNGRİD KELLİNG

  3. Parallel algorithms for shortest path problem on time dependent graphs

    Zamana bağımlı çizgelerde en kısa yol problemi için paralel algoritmalar

    MEHMET AKİF ERSOY

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. CAN ÖZTURAN

  4. The Robust shortest path problem with interval data uncertainties

    Aralık sayılar belirsizliğinde en kısa yol problemi

    ABDULLAH SIDDIK KARAMAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2001

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA Ç. PINAR

  5. Essays on some combinatorial optimization problems with interval data

    Verileri aralık sayılar olan bazı en iyileme problemleri üzerine denemeler

    HANDE YAMAN

    Yüksek Lisans

    İngilizce

    İngilizce

    1998

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA Ç. PINAR