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: Belirtilmemiş.
- 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ı: 42
Ö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
- Graf matrisleri ve enerji
Graph matrices and energy
ÇİLEM YAMAÇ
Yüksek Lisans
Türkçe
2019
MatematikBursa Uludağ ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. İSMAİL NACİ CANGÜL
- Bina işlevi ile bina biçimi ilişkisinde çizge teorisi kullanımı ile veri eldesi
Obtaining data by using graph theory within the context of building function and building form
MEHMET TAYFUN YILDIRIM
- Doğum indüksiyonunda intravenöz oksitosin infüzyonu ile servikal olgunlaştırıcı balonun (cervical ripening balloon) karşılaştırılarak sonuçlarının değerlendirilmesi
Comparing the effect of intravenous oxytocin and cervical ripening balloon for the labor induction
FIRAT TÜLEK
Tıpta Uzmanlık
Türkçe
2014
Kadın Hastalıkları ve DoğumAnkara ÜniversitesiKadın Hastalıkları ve Doğum Ana Bilim Dalı
PROF. DR. FERİDE SÖYLEMEZ
- 19. yüzyıl İstanbul dizi konutlarının morfolojik andizine dayalı bilgi tabanlı tasarım modeli
Başlık çevirisi yok
ÇİLER KIRŞAN
- Soliter pulmoner nodülü olan hastalara uygulanan PET/BT çalışmasında tüm vücut BT yerine sadece toraksa yönelik çekilen BT'nin etkileri.
The effects of only thoracic CT scan instead of whole body CT scan in patients with solitary pulmonary nodule, who are applied PET/CT scan.
ÇAĞLA HAKSAL
Tıpta Uzmanlık
Türkçe
2015
Radyoloji ve Nükleer TıpKocaeli ÜniversitesiNükleer Tıp Ana Bilim Dalı
YRD. DOÇ. DR. GÖZDE DAĞLIÖZ GÖRÜR