On the graph coloring problem
Çizge boyama problemi
- Tez No: 444750
- Danışmanlar: DOÇ. DR. FATİH DEMİRKALE
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Yıldız Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 89
Özet
Çizge boyama problemindeki amaç, ortak noktaları olan kenarları ayrı renklerde olmak üzere en az renk sayısını bulmaktır. Çizge boyama problemi, gerçek hayattaki bir çok problemi modellemek ve çözmek için kullanılır. Bölüm 1'de, çizge boyama problemini tanıtacağız. Sonra, bu teorinin tarihsel gelişiminden bahsedeceğiz. Ayrıca, Königsberg köprü problemini şekillerle açıklayacağız. Bölüm 2'de, çizge kuramı ve çizge boyama ile ilgili tanımları örneklerle vereceğiz. Ayrıca, çizgeler üzerindeki operasyonları ve bazı özel çizgeleri ayrıntılı inceleyeceğiz ve bazı önemli teoremleri ispatları ile sunacağız. Bölüm 3'te, nokta boyama problemini açıklayıp ilgili tanımları vereceğiz. Ayrıca, bir çizgenin nokta renk sayısını tanımlayacağız. Sonra, nokta renk sayısı ile ilgili önemli alt ve üst sınırları ifade eden teoremleri vereceğiz. Son olarak, nokta renk sayısı ile ilgili bir açgözlü algoritma ve ilgili teoremleri sunacağız. Bölüm 4'te, kenar boyama problemini açıklayacağız. Kenar renk sayısını tanımlayıp ilgili sınırları ifade edeceğiz. Ayrıca, bazı özel çizgelerin kenar renk sayılarını inceleyeğiz. Bölüm 5'te, nokta ve kenar boyama üzerine bazı uygulamar sunacağız. Bu uygulamarla, çizge boyamanın önemine değineceğiz ve bu teorinin gerçek hayattaki problemlerde nasıl çalıştığını keşfedeceğiz.
Özet (Çeviri)
The aim in the graph coloring problem is finding the minimum number of colors so that the vertices of a given graph are colored with the property that no two adjacent vertices take the same color. The graph coloring problem is used to model and solve several real life problems. In Chapter 1, we introduce the graph coloring problem, also we give a historical view on the graph coloring, and we explain the beginning of this theory. Also, we explain the Königsberg Bridge problem with an illustration. In Chapter 2, we give the important concepts and definitions on the graph coloring with illustrations. Also, we explain the operations on the graphs and we give the definitions of the directed graphs, cliques, connected graphs, trees and spanning trees, and we state some important theorems with their proofs. In Chapter 3, we introduce vertex coloring problem and we state the definitions of proper coloring and the chromatic number of a graph. We give some well-known upper and lower bounds for the chromatic number. Also, we explain the greedy algorithm and some theorems which have relations with chromatic number. In Chapter 4, we introduce the edge coloring problem and give the definitions of proper k-edge-coloring, chromatic index of a graph, edge independence number and we state some bounds on chromatic index for special graphs. In Chapter 5, we present some applications on vertex coloring and edge coloring problem. By these applications, we will touch the importance of graph coloring and we discover how this theory works in real life.
Benzer Tezler
- Graflarda düğüm boyama problemi için kurbağa sıçrama algoritması tabanlı bir yaklaşım
An approach based on shuffled frog leaping algorithm for vertex coloring problem in graphs
MURAT ASLAN
Yüksek Lisans
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. NURDAN BAYKAN
- A decomposition approach to solve the selective graph coloring problem
Seçmeli çizge boyama problemi için bir ayrıştırma yaklaşımı
OYLUM ŞEKER
Doktora
İngilizce
2018
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TINAZ EKİM AŞICI
PROF. DR. ZEKİ CANER TAŞKIN
- Graf renklendirme problemine uyarlanmış personel atama uygulaması
An implementation of personnel assignment adapted to graph coloring problem
MURAT CAN BURAK YILDIZ
Yüksek Lisans
Türkçe
2017
Endüstri ve Endüstri MühendisliğiBeykent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. ÜMİT TERZİ
- Solving dynamic graph coloring problem by using a heuristic algorithm
Sezgisel bir algoritma kullanarak dinamik grafik renklendirme problemi çözme
GİZEM SÜNGÜ
Yüksek Lisans
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. BETÜL DEMİRÖZ BOZ
- Solving graph coloring problem by using an evolutionary algorithm
Başlık çevirisi yok
SERAP KORKMAZ
Yüksek Lisans
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BETÜL DEMİRÖZ BOZ