An Innovative Solution to the Map Coloring Problem Using the Malatya Vertex Coloring Algorithm

Abstract

The map coloring problem is a classical NP-complete problem that requires adjacent regions to be colored differently and is encountered in many real-world applications. Numerous algorithms have been developed to solve this problem. In this study, the Malatya Vertex Coloring (MVC) Algorithm, which presents a novel and original approach to solving the problem, is applied. This algorithm aims to identify influential vertices to reduce the number of colors used in graphs and to complete the coloring process more efficiently. Additionally, the applicability of the algorithm to real-world problems is also evaluated. The MVC Algorithm calculates the Malatya Centrality value for each vertex in the graph; it selects the vertex with the highest value, colors it with a color different from its neighbors, and then removes it from the graph. This process continues until all vertices are colored. The algorithm has been successfully applied to maps of Asia, Europe, districts of Istanbul, Turkey, U.S. states, and the world, and the results demonstrate the effectiveness of the algorithm. The advantages of the MVC Algorithm include its predictability, as well as its ability to operate in polynomial time and space. In this respect, the MVC Algorithm offers an alternative solution approach to the classical Four Color Theorem in the context of the map coloring problem.

Harita renklendirme problemi, bitişik bölgelerin farklı renklerle boyanmasını gerektiren ve birçok gerçek hayat uygulamasında karşılaşılan klasik bir NP-tam problemdir. Bu problemin çözümü için birçok algoritma geliştirilmiştir. Bu çalışmada, ilgili problemin çözümüne yönelik yeni ve özgün bir yaklaşım ortaya koyan Malatya Vertex Coloring (MVC) Algoritması uygulanmıştır. Bu algoritma, graflarda kullanılan renk sayısını azaltmak için etkili düğümleri belirlemekte ve renklendirme sürecini daha kısa sürede tamamlamayı hedeflemektedir. Ayrıca algoritmanın, gerçek hayat problemlerine uygulanabilirliği de değerlendirilmiştir. MVC Algoritması, graf yapısındaki her düğüm için Malatya Merkezilik değerini hesaplar; en yüksek değere sahip düğümü seçerek komşularından farklı bir renkle boyar ve ardından bu düğümü graf üzerinden çıkarır. Bu işlem, tüm düğümler renklendirilene kadar devam etmektedir. Algoritma; Asya, Avrupa, İstanbul ilçeleri, Türkiye, ABD eyaletleri ve Dünya haritaları üzerinde başarıyla uygulanmış ve elde edilen sonuçlar algoritmanın etkinliğini ortaya koymuştur. MVC Algoritması’nın avantajları arasında öngörülebilir olması, polinom zamanda ve polinom uzayda çalışabilmesi yer almaktadır. Bu yönüyle, MVC Algoritması’nın harita renklendirme problemine ilişkin olarak klasik Dört Renk Teoremi’ne alternatif bir çözüm yaklaşımı sunduğu ortaya konulmuştur.