Malatya merkezilik algoritmasına dayalı graf renklendirme algoritmasının harita renklendirme ve ders çizelgeleme uygulamaları

Graf renklendirme problemi(GCP), ilk kez 1852 yılında Francis Guthrie tarafından İngiltere haritası üzerinde çalışırken ortaya atılmıştır. Guthrie, komşu bölgelerin farklı renklerle boyanması gerektiğini ve bunun dört renk ile mümkün olduğunu gözlemlemiştir. Bu problem zamanla graf kuramının temel konularından biri hâline gelmiştir. Graf renklendirmede temel amaç, komşu düğümlere farklı renkler atamak ve mümkün olan en az sayıda rengi kullanmaktır. Bu tezde, GCP'ye yeni bir yaklaşım olarak Malatya Vertex Coloring(MVC) Algoritması geliştirilmiştir. MVC, graf yapısındaki her düğüm için Malatya Merkezilik değeri hesaplayarak en etkili düğümü belirler; bu düğümü komşularından farklı bir renkle boyar ve graf üzerinden çıkarır. İşlem, tüm düğümler renklendirilene kadar devam eder. Algoritmanın temel hedefi, kullanılan renk sayısını azaltmak ve çözümü polinom zamanda tamamlamaktır. Geliştirilen algoritma öncelikle GCP'ye uygulanmış, ardından harita renklendirme ve ders çizelgeleme gibi gerçek dünya problemlerinde test edilmiştir. Asya, Avrupa, Türkiye, ABD eyaletleri ve İstanbul ilçeleri gibi çeşitli haritalar üzerinde başarılı sonuçlar elde edilmiştir. MVC, klasik Dört Renk Teoremi'nden farklı olarak öngörülebilirliği ve hesaplama verimliliğiyle dikkat çekmektedir. Ayrıca üniversite ders çizelgeleme problemi(CSP) üzerinde de uygulanarak, dersler arası çakışmalar minimize edilmiş ve geçerli çizelgeler oluşturulmuştur. Elde edilen bulgular, MVC algoritmasının sezgisel ve klasik yöntemlere karşı güçlü, etkili ve uygulanabilir bir alternatif olduğunu ortaya koymuştur.