Transformasyon grafların paketleme boyama sayısı

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.