The selective graph coloring problem

Klasik çizge boyama problemi, verilen bir çizgenin köşelerinin iki komşu köşe aynı rengi almayacak şekilde en az renk kullanılarak boyanması problemidir. Bir çizgenin boyanabileceği en az sayıdaki renge, o çizgenin boyama sayısı denir. Klasik çizge boyama probleminin karar versiyonu NP-tam, optimizasyon versiyonu NP-zor'dur. Seçmeli boyama problemi, klasik boyama probleminin bir genellemesidir. Bu problemde, çizge ve bu çizgenin köşelerinin parçalanmış hali girdi olarak verilmektedir. Problemin amacı, iki komşu köşe aynı rengi almayacak şekilde her parçadan bir köşe seçilerek bu şekilde oluşan çizgeyi en az sayıda renkle boyamaktır. Seçmeli boyama problemi çeşitli uygulamaların çözümüne yardımcı olabilecektir. Doğal bir felaketten sonra yeni vericilere frekans atama probleminin çözülebilmesi için GSM ağının tamir edilmesi ya da yeniden kurulması ve her iş paketinin yapılabileceği belli zaman aralıklarının olduğu bir çizelgeleme probleminin çözülmesi bu uygulamalara örnektir. Sezgisel yöntemler, NP-zor problemler için hızlı çalışan ve en iyi sonuca yakın sonuçlar vermeyi amaçlayan yöntemlerdir. Bu nedenle seçmeli boyama probleminin çözümü için sezgisel yöntemlerin geliştirilmesi kaçınılmazdır. Tezin ana konusu seçmeli çizge boyama probleminin çözümü için yeni sezgisel ve tam çözüm yöntemleri geliştirilmesidir. Bu amaçla çeşitli sezgisel ve tam çözüm yöntemleri denenmiş ve deneylerle sonuçları incelenmiştir.