Transformasyon grafların paketleme boyama sayısı

Abstract

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.

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.