Introduction to vertex-coloring problem
Köşe renklendirme problemine giriş
- Tez No: 711502
- Danışmanlar: DR. ÖĞR. ÜYESİ CELALETTİN KAYA
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Graflar, Kromatizm, Renklendirme, Graphs, Chromaticism, Coloring
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Çankırı Karatekin Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Cebir ve Sayılar Teorisi Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Köşe renklendirme problemi, bir grafın köşelerini uygun bir şekilde renklendirmek için mümkün olan en az sayıda rengi kullanmak ve bu renklendirmeyi bulmanın bazı yollarını göstermek ile ilgilidir. Bu tezin birinci bölümünde, bu ünlü problemi kökenini ve tarihsel gelişimini vererek tanıttık. ̇İkinci bölümde, graflarla ilgili temel tanım ve teoremleri verdik. Üçüncü bölümde, bir grafın kromatik sayısını tanımladık ve ilgili sonuçları sunduk. Bunun, bazı gerçek hayat problemlerinin çözümü için bir zaman çizelgesi bulma gibi bazı uygulamalarını sunduk. Dördüncü bölümde, bir graf için kromatik sayının nasıl hesaplanacağını ve üst ve alt sınırlarını inceledik. Kromatik sayıyı bulmanın yollarından birisi olan açgözlü renklendirme algoritmasına değindik. Ayrıca, iki basit grafın Kartezyen çarpımının kromatik sayısını bulduk. Beşinci ve son bölümde, dört renk problemini tanıttıktan sonra, bir yüzey üzerindeki bir grafın renklendirilmesi konusunu ele aldık. Son olarak, Hajos ve Hadwiger varsayımlarından da bahsettik.
Özet (Çeviri)
The vertex coloring problem is about using the smallest number of colors possible to color the vertices of a graph properly, and also related to ways to find this coloring. In the first chapter of this thesis, we introduced this famous problem by giving its origin and historical development. In the second chapter, we gave basic definitions and theorems about graphs. In the third chapter, we defined the chromatic number of a graph, and introduced related results. We also presented some of its applications such as finding a time line for solving some real-life problems. In the fourth chapter, we looked at how to calculate chromatic number for a graph, and its upper and lower bounds. We looked at one of the ways to find the chromatic number, which is the greedy coloring algorithm. We also found the chromatic number of the Cartesian product of two simple graphs. In the fifth and final chapter, after introducing the four-color problem, we reviewed the topic of coloring a graph on a surface. Finally, we also mentioned Hajos and Hadwiger conjectures.
Benzer Tezler
- Türkiye'deki konut sorununun çözümünde endüstrileşmiş yapım yöntemlerinin yeri ve hücre sistemi ile yapılan tasarımda değişebilirliğe yönelik bir çalışma
A Study on the importance of the industrialized building methods in handling the housing problem in Turkey and the changeability in the box-unit design
NEJDET TANATMIŞ
- The Effects of the chomskyan revolution in linguistics on language teaching
Başlık çevirisi yok
BANU KARAHAN
- Çekirdeksiz kuru üzümde uygulanan politikanın Ege Bölgesinde üretim ve üretici açısından sonuçlarının değerlendirilmesi
Başlık çevirisi yok
GÜVEN ÖZERİN
