Pewarnaan Graf pada Peta Provinsi Sumatra Barat dengan Parameter Kemiskinan Menggunakan Algoritma Welch-Powell

Abstract

Kemiskinan merupakan salah satu permasalahan global yang masih sulit untuk diatasi. Data tingkat kemiskinan umumnya disajikan dalam bentuk numerik, sehingga gambaran mengenai tingkat kemiskinan wilayah kurang terlihat jelas. Oleh karena itu, diperlukan representasi secara visual dalam bentuk peta wilayah dengan parameter kemiskinan. Dalam penelitian ini, Provinsi Sumatra Barat direpresentasikan sebagai graf dengan setiap kota/kabupaten sebagai simpul dan sisi menggambarkan hubungan dua kota/kabupaten yang berada di tingkat kemiskinan yang berbeda. Pewarnaan simpul pada graf tersebut dilakukan berdasarkan kategori tingkat kemiskinan menggunakan algoritma Welch-Powell. Penelitian ini menunjukkan bahwa graf yang merepresentasikan Provinsi Sumatra Barat memiliki derajat simpul maksimum sebanyak delapan belas dan dapat diwarnai menggunakan lima warna dengan tetap memperhatikan sifat-sifat pewarnaan graf.

Poverty is one of the global issues that remains difficult to overcome. Poverty rate data is often presented numerically, making it difficult to illustrate regional poverty levels clearly. Therefore, a visual representation in the form of a regional map with poverty parameters is needed. In this study, West Sumatra Province is represented as a graph, with each city/district as a node and edges indicating relationships between cities or districts with different poverty levels. The nodes in the graph are colored based on poverty level categories using the Welch-Powell algorithm. This study shows that the graph representing West Sumatra Province has a maximum node degree of eighteen and can be colored using five colors while still considering the properties of graph coloring.