Geri Dön

On the graph coloring problem

Çizge boyama problemi

  1. Tez No: 444750
  2. Yazar: AHMED MOHAMMED ABBAS ABBAS
  3. Danışmanlar: DOÇ. DR. FATİH DEMİRKALE
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2016
  8. Dil: İngilizce
  9. Üniversite: Yıldız Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Türkçe

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. NURDAN BAYKAN

  2. 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

    İngilizce

    2018

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

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

    DOÇ. DR. TINAZ EKİM AŞICI

    PROF. DR. ZEKİ CANER TAŞKIN

  3. 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

    Türkçe

    2017

    Endüstri ve Endüstri MühendisliğiBeykent Üniversitesi

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

    YRD. DOÇ. ÜMİT TERZİ

  4. 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

    İngilizce

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. BETÜL DEMİRÖZ BOZ

  5. Solving graph coloring problem by using an evolutionary algorithm

    Başlık çevirisi yok

    SERAP KORKMAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ BETÜL DEMİRÖZ BOZ