Çizgelerde yol-eşleme ve renklendirme
Path-matching and coloring in graphs
- Tez No: 318177
- Danışmanlar: DOÇ. DR. YUSUF CİVAN
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: Türkçe
- Üniversite: Süleyman Demirel Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- Resource mapping optimization for distributed cloud services
Dağıtık bulut hizmetleri için kaynak eşlemenin iyileştirilmesi
ATAKAN ARAL
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TOLGA OVATMAN
- 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)
- 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
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CAN ÖZTURAN
- 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
2001
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA Ç. PINAR
- 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
1998
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA Ç. PINAR
