PERBANDINGAN ALGORITMA SEQUENTIAL COLORING DENGAN ALGORITMA GREEDY UNTUK MELAKUKAN PEWARNAAN GRAF DALAM PEMETAAN DAERAH KOTA MEDAN PROVINSI SUMATERA UTARA

Salah satu terapan terpenting pewarnaan graf adalah pewarnaan peta (coloring of map). Peta terdiri atas sejumlah wilayah, wilayah pada peta dapat menyatakan provinsi, kabupaten, negara dan lain-lain. Dalam mewarnai sebuah peta, pewarnaan setiap wilayah di dalam peta sedemikian sehingga tidak ada dua wilayah bertetangga yang mempunyai warna sama. Satu cara untuk menjamin bahwa dua buah wilayah bertetangga tidak mempunyai warna yang sama adalah dengan menggunakan warna yang berbeda untuk setiap wilayah.Penelitian ini bertujuan untuk menentukan algoritma manakah yang lebih efisien antara algoritma Sequential Coloring dengan algoritma greedy dalam menentukan warna pada peta Kota Medan Provinsi Sumatera Utara.Hasil penelitian menunjukkan bahwa hasil pewarnaan dari algoritma sequential coloring dengan greedy mempunyai kesamaan, yaitu persamaan dalam pewarnaan yang mempunyai empat warna. Jika dilihat dari segi efisiennya, algoritma sequential coloring lebih efisien jika dibandingkan dengan algoritma greedy. Karena algoritma sequential coloring memiliki konpleksitas waktu dan konpleksitas ruang yang lebih sedikit jika dibandingkan dengan algoritma greedy .