Transformasyon grafların paketleme boyama sayısı
On the packing chromatic number of transformation graphs
- Tez No: 548477
- Danışmanlar: DR. ÖĞR. ÜYESİ DERYA DURGUN
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: Türkçe
- Üniversite: Manisa Celal Bayar Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 86
Özet
Graflarda boyama probleminin temelleri 1852'de Francis Guthrie tarafından atılmıştır. Uygulamada harita üzerindeki komşu şehirlerin farklı renklerle boyanması en yaygın örneğidir. Bu örneğin graftaki karşılığı komşu tepelerin farklı renklerle boyanmasıdır. Benzer şekilde bitişik ayrıtların farklı renklerle boyanması ile de ayrıt boyama tanımlanır. Bu tür boyama klasik boyama olarak adlandırılır. Bir grafın tepe ve ayrıtlarının klasik boyanmasına indirgenemeyen pek çok problem için klasik olmayan boyama modelleri tanımlanmıştır. Her boyama modeli için çözümün en iyisi ve geçerliliği üzerine çeşitli kurallar vardır. Bu tezde, klasik boyama problemi modeli üzerine tanımlanmış olan paketleme boyama üzerine çalışılmıştır. Paketleme boyama problemi NP sınıfından olduğundan hesaplama yapmak oldukça zordur. Bu çalışmada, bazı özel graf sınıflarının transformasyon grafları elde edilmiş ve bunların paketleme boyama sayıları genelleştirilmeye çalışılmıştır. Çalışmanın tamamında, bağlantılı, basit ve yönsüz graflarla çalışılmıştır. Bu tez beş bölümden oluşmaktadır. İlk bölümde Graf Teorinin ortaya çıkışı olan Königsberg Köprülerinden bahsedilmiştir. Daha sonra Graf Teorinin ilk teoremi olan El Sıkışma Teoremine değinilmiştir. Ardından dört renk problemi anlatılmış ve paketleme boyama probleminin ortaya çıkış şeklinden bahsedilmiştir. İkinci bölümde, tezde kullanılan temel tanım ve teoremler ayrıntılı bir şekilde verilmiştir. Üçüncü bölümde, paketleme boyama sayısı tanımı verilmiş ve transformasyon graflar açıklanmıştır. Bu bölümde, bir transformasyon grafın paketleme boyama sayısının bulunuşu örnek olarak verilmiştir. Dördüncü bölümde, G grafı yol, çevre, tekerlek, tam ve star graflar olmak üzere G^(---), G^(+--), G^(-+-) ve G^(++-) transformasyon graflarının paketleme boyama sayıları teoremler ile ifade edilmiş ve ispatları verilmiştir. Bu bölümün sonunda, çalışmaya ait sonuçlar bir tablo halinde verilmiştir. Beşinci ve en son bölümde ise yapılan çalışma öneriler ile birlikte değerlendirilmiştir.
Özet (Çeviri)
The foundations of the coloring problem in graphs were laid by Francis Guthrie in 1852. In practice, the most common example of coloring is coloring the neighbor cities on the map with different colors. This corresponds to assignment of different colors to adjacent vertices. Similarly, the coloring of adjacent edges with different colors is also described. This type of coloring is called classical coloring. Non-classical coloring models have been described for many problems that cannot be reduced to the classical coloring of the vertex and edges of a graph. There are various rules for the best and validity solution for each coloring models. In this thesis, packing coloring which is defined on classical coloring problem model has been studied. It is very difficult to make a calculation because the packing coloring problem is NP class. In this study, transformation graphs of some special graph classes is obtained and their packing coloring numbers is tried to be generalized. Throughout the study simple, undirected and connected graphs are studied. This thesis consists of five chapters. In the first chapter, Königsberg bridges, which are emergence of the graph theory, are mentioned and the history of the Graph Theory are mentioned. Then, the first theorem of graph theory, (the handshake theorem) is given. Then, The four color problem and of packing coloring problem is mentioned. In the second chapter, the basic definations and theorems used in the thesis are given in details. In the third chapter, the defination of transformation graphs and the packing coloring number is given. In this section, the example of the packing coloring number of a transformation graph is given. In the Fourth chapter, Packing chromatic number of G^(---), G^(+--), G^(-+-) and G^(++-) transformation graphs, where G, path, cycle, wheel, complete and star graphs, are given by theorem and their proofs. At the end of the chapter, the results of the study are given as a table. In the fifth chapter, the study is evaluated with suggestions.
Benzer Tezler
- Nicemlenmiş yerel zernike momentlerle trafik işaretlerinin sınıflandırılması
Traffic sign classification with quantized local zernike moments
EMRAH BAŞARAN
Yüksek Lisans
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MUHİTTİN GÖKMEN
- Transformasyon grafların Gutman indeksi
Gutman index of transformation graphs
MERVE ÇAKAL
Yüksek Lisans
Türkçe
2021
MatematikManisa Celal Bayar ÜniversitesiMatematik Ana Bilim Dalı
DOÇ. DR. GÖKŞEN BACAK TURAN
- Transformasyon grafların 2-baskınlık ve ortalama alt 2-baskınlık değerleri
The values of 2-domination and average lower 2-domination of transformation graphs
MUHAMMED BEHRAM TALAY
- Transformasyon Grafların Komşu Rupture Derecesi
Neighbor Rupture Degree Of Transformation Graphs
EKREM ÖZ
Yüksek Lisans
Türkçe
2015
MatematikCelal Bayar ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. GÖKŞEN BACAK TURAN
- Transformasyon graflarda ortalama düşük bağlantılılık ve komşu izole saçılım sayısı
Transformation of the graphs average lower connecti̇vi̇ty and nei̇ghbor i̇zoleted scatteri̇n number
BÜŞRA AÇAN
Yüksek Lisans
Türkçe
2017
MatematikCelal Bayar ÜniversitesiFen Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. ERSİN ASLAN