## Implementasi Algoritma Sequential dan Welch Powell phsada Pewarnaan Graf (Studi
Kasus Pewarnaan Peta Kota Makassar)

## Muhammad Ammar
Universitas Muhammadiyah Bulukumba
Tanah Kongkong, Ujung Bulu, Kabupaten Bulukumba, Sulawesi Selatan 92511 Email: ammar.uin@gmail.com

## Abstract
The aim of this research is how to implement Sequential algorithm and Welch Powell algorithm on graph coloring, especially on Makassar city map coloring. The research method used was a case study aimed at searching information in the form of a map of Makassar city. The first step is to take a colored map of Makassar  city  at  the  Dinas  tata  ruang  kota  makassar,  then  redraw  it  with  the  help  of  Corel  Draw  X7 software, so there are no colors. The next step is to represent the map in graph form by taking the region (sub-district)  as  a  node  and  then  doing  graph  coloring  using  Sequential  algorithm  and  Welch  Powell algorithm. The results of coloring the Makassar city map using Sequential algorithm and Welch Powell algorithm, both produce chromatic numbers χ (G) = 4 or the number of colors produced to color a graph there are 4 colors. The colors used are red, yellow, green and blue. Then from the results of coloring this graph can easily be applied to color the map of the city of Makassar based on the coloring requirements obtained. Because it has the same chromatic numbers, it can be concluded that the Sequential algorithm is no better than the Welch Powell algorithm, or vice versa the Welch Powell algorithm is no better than the Sequential  algorithm  for  the  case  of  coloring  the  Makassar  city  map.  The  previous  Makassar  city  map coloring  or  without  the  algorithm,  produces  chromatic  numbers  χ  (G)  =  12  or  the  number  of  colors produced to color a graph there are 12 colors. So that the two algorithms are much better at coloring than the previous Makassar city map coloring or without the algorithm
Keywords: Graph, Graph Coloring, Sequential Algorithm, Welch Powell Algorithm, Chromatic Numbers

## Abstrak
Tujuan dari penelitian ini adalah bagaimana mengimplementasikan algoritma Sequential dan algoritma Welch Powell pada pewarnaan graf khususnya pada pewarnaan peta kota Makassar. Metode penelitian yang digunakan adalah studi kasus yang bertujuan mengumpulkan informasi berupa peta kota Makassar. Langkah pertama yang dilakukan yaitu mengambil peta kota Makassar berwarna di Instansi Dinas tata ruang kota Makassar, kemudian digambar ulang dengan bantuan software Corel Draw X7, sehingga tidak terdapat warna. Langkah berikutnya yaitu merepresentasikan peta kedalam bentuk graf dengan mengambil daerah  wilayah  (kecamatan)  sebagai  simpul  dan  selanjutnya  melakukan  pewarnaan  graf  menggunakan algoritma  Sequential  dan  algoritma  Welch  Powell.  Hasil  pewarnaan  peta  kota  Makassar  dengan menggunakan  algoritma  Sequential  dan  algoritma  Welch  Powell,  sama-sama  menghasilkan  Bilangan kromatik 𝜒(𝐺) = 4 atau jumlah warna yang dihasilkan untuk mewarnai sebuah graf ada 4 warna. Warna yang  digunakan  yaitu  merah,  kuning,  hijau,  dan  biru.  Kemudian  dari  hasil  pewarnaan  graf  ini  dengan mudah dapat diaplikasikan untuk mewarnai peta kota Makassar berdasarkan ketentuan pewarnaan yang diperoleh. Karena memiliki Bilangan kromatik yang sama, maka dapat disimpulkan algoritma Sequential tidak lebih baik dari algoritma Welch Powell, ataupun sebaliknya algoritma Welch Powell tidak lebih baik dari  algoritma  Sequential  untuk  kasus  pewarnaan  peta  kota  Makassar.  Adapun  pewarnaan  peta  kota Makassar  sebelumnya  atau  tanpa  algoritma,  menghasilkan  bilangan  kromatik 𝜒(𝐺) = 12 atau  jumlah warna yang dihasilkan untuk mewarnai sebuah graf ada 12 warna.  Sehingga kedua algoritma jauh lebih baik dalam melakukan pewarnaan dibandingkan pewarnaan peta kota Makassar sebelumnya atau tanpa algoritma.
Kata Kunci: Graf, Pewarnaan graf, Algoritma Sequential, Algoritma Welch Powell, bilangan kromatik

## I. PENDAHULUAN
Graf  dapat  digunakan  untuk  pada  beberapa kasus, termasuk jejaring sosial, kimia, penjadwalan, pengiriman paket, navigasi satelit, teknik elektro,dan lain-lain [1]. Graf memiki aplikasi yang sangat  luas,  Salah  satunya  adalah  pewarnaan  graf ( graph  colouring ).    Banyak  dari  persoalan kehidupan sehari-hari yang memiliki karakterisitik seperti mewarnai graf. Contohnya adalah persoalan mewarnai  peta  sehingga  tidak  ada  wilayah bertetangga yang mempunyai warna yang sama dan persoalan  menentukan  jadwal  ujian  mata  kuliah sehingga tidak ada jadwal ujian yang bertabrakan Kocay  membagi  Pewarnaan  graf  menjadi  tiga macam,  yaitu  pewarnaan  simpul,  pewarnaan  sisi, dan pewarnaan wilayah ( region ). Pewarnaan simpul ( vertex  coloring )  adalah  memberi  warna  pada simpul-simpul suatu graf sedemikian sehingga tidak ada dua simpul bertetangga mempunyai warna yang sama.  Pewarnaan  sisi  ( edge  coloring )  adalah memberi warna berbeda pada sisi yang bertetangga sehingga  tidak  ada  dua  sisi  yang  bertetangga mempunyai warna yang sama. Sedangkan pewarnaan  bidang  ( region  coloring )  adalah memberi  warna  pada  bidang  sehingga  tidak  ada bidang  yang  bertetangga  mempunyai  warna  yang sama  [2].  Menurut  Laputty,  Pewarnaan  bidang hanya bisa dilakukan dengan membuat graf tersebut menjadi graf planar terlebih dahulu [3].
Pada  persoalan  pewarnaan  graf,  masalah  yang ada  tidak  hanya  sekedar  mewarnai  simpul-simpul dengan  warna  berbeda  dari  warna  simpul tetangganya saja, namun jumlah macam warna yang digunakan  juga  harus  sesedikit  mungkin.  Jumlah warna  minimum  yang  dapat  digunakan  untuk mewarnai simpul disebut bilangan kromatik graf G ( 𝜒(𝐺) ) [4].
Beberapa graf tertentu dapat langsung ditentukan  bilangan  kromatiknya.  Kosowsky  & Manuzewsky menjelaskan bilangan kromatik untuk berbagai  graf,  Untuk  graf  kosong,  bilangan kromatiknya 𝜒(𝐺) = 1 karena  semua  simpul  tidak terhubung,  jadi  untuk  mewarnai  semua  simpul cukup dibutuhkan satu warna saja. Graf lengkap 𝐾 𝑛 memiliki 𝜒(𝐺) = 𝑛 sebab  semua  simpul  saling terhubung sehingga diperlukan n buah warna. Graf bipartit  mempunyai  bilangan  kromatik 𝜒(𝐺) = 2 , satu untuk simpul-simpul di himpunan 𝑉 1 dan satu lagi  untuk  simpul-simpul  di  himpunan 𝑉 2 .  Graf lingkaran  dengan n ganjil  memiliki 𝜒(𝐺) = 3 sedangkan jika n genap maka 𝜒(𝐺) = 2 , Sembarang pohon  T  memilik 𝜒(𝐺) = 2 .  Adapun  untuk  graf- graf  lain  tidak  dapat  dinyatakan  secara  umum bilangan
kromatiknya.  Sehingga  batas  untuk  bilangan kromatik  dari  beberapa  graf  G  dan  dapat disimpulkan dengan 1 ≤ 𝜒(𝐺) ≤ 𝑛 [5].
Salah  satu  terapan  penting  pewarnaan  graf adalah  mewarnai  peta.  Ketika  diminta  mewarnai suatu  peta  yang  terdiri  atas  sejumlah  wilayah, wilayah  pada  peta  dapat  menyatakan  provinsi, kabupaten,  negara  dan  lain-lain.  Untuk  mudahnya perhatikan negara Amerika serikat yang terdiri atas 50  negara  bagian.  Dan  diminta  mewarnai  setiap wilayah  didalam  peta  sedemikian  sehingga  tidak ada  dua  wilayah  bertetangga  yang  mempunyai warna yang sama. Satu cara untuk menjamin bahwa dua  wilayah  bertetangga  tidak  mempunyai  warna yang  sama  adalah  menggunakan  warna  yang berbeda untuk setiap wilayah.
Banyak  algoritma  yang  dapat  digunakan  untuk mewarnai  graf  dalam  berbagai  penerapannya.  Sari mengatakan teknik algoritma yang digunakan untuk melakukan pewarnaan graf secara umum mengadopsi metode First fit (FF), Largest Degree ordering (LDO), Saturation  degree  ordering (SDO), incidence degree ordering (IDO), dan lain- lain [6].
Beberapa  penelitian  tentang  penerapan  dari pewarnaan graf yang pernah dilakukan sebelumnya yaitu  [7]  penggunaan  algoritma  greedy  pada pewarnaan peta jawa timur,  [8] Pewarnaan simpul dengan algoritma Welch Powell pada traffic light di Yogyakarta, [9] Implementasi algoritma tabu search pada penyusunan jadwal kuliah jurusan matematika UIN  Alauddin  Makassar,  [10]  Penyusunan  lokasi duduk  menggunakan  algoritma  greedy  berbasis aplikasi  visual  basic,  dan  [11]  Penggunaan algoritma sequential pada penataan buku perpustakaan,  [12]  penyelesaian  pewarnaan  graf dengan menggunakan algoritma genetika.
Penyelesaian  algoritma  yang  akan  digunakan pada penelitian ini yaitu  algoritma Sequential dan algoritma  Welch  Powell.  Algoritma  Sequential merupakan  algoritma  paling  sederhana  karena pengerjaannya sesuai urutan simpul yang mengadopsi metode First fit (FF). Menurut Rahmat dkk, Implementasi algoritma Sequential diharapkan dapat  menghasilkan  banyaknya  warna  yang digunakan  pada  pewarnaan  simpul  graf  mendekati atau sama dengan bilangan kromatik graf itu sendiri [13]. Sedangkan menurut Sari, Jika dilihat dari segi efisiennya,  algoritma  Sequential  lebih  efisien  jika dibandingkan  dengan  algoritma  lainnya.  Karena algoritma Sequential memiliki kompleksitas waktu dan konpleksitas ruang yang lebih sedikit [14].
Adapun langkah-langkah  algoritma  Sequential dalam pewarnaan graf yaitu sebagai berikut:
a) start
b) Input simpul  (v) dan sisi (e)
c) Mencari nilai 𝐿 𝑖 untuk setiap 𝑖 = 1, … , 𝑣 d) Lakukan perulangan 𝑖 = 1, … , 𝑣
e) Mencari nilai 𝐶 𝑖 = 𝑉 1 di 𝐿 𝑖 f) Lakukan perulangan 𝑗 = 1, … , 𝑣 g) Melakukan  pengujian  Jika 𝑉 𝑖 , 𝑉 𝑗 ∈ 𝐸, 𝑖 ≠ 𝑗 maka  lanjutkan  jika  tidak  kembali  kelangkah (f)
h) Mencari nilai 𝐿 𝑗 = 𝐿 𝑗 − 𝐶 𝑖 i) Output 𝑉 𝑖 . 𝑉 𝑣 = 𝐶 𝑖 j) Output 𝑛 = 𝐶 𝑣 k) End Berdasarkan algoritma diatas maka dapat suatu flowchart sebagai berikut:
Gambar 1 . Flowchart Algoritma Sequential
Adapun  algoritma  Welch  Powell  merupakan salah  satu  algoritma  pewarnaan  graf  yang melakukan pewarnaan berdasarkan derajat tertinggi dari  simpul-simpulnya  yang  mengadopsi  metode Largest Degree Ordering (LDO). Menurut Ammar, algoritma  ini  dapat  digunakan  untuk  mewarnai sebuah  graf  secara  efisien  [15].  Adapun  menurut Purnamasari, mengatakan algoritma Welch Powell tidak  selalu  memberikan  jumlah  warna  minimum yang  diperlukan  untuk  mewarnai  graf,  tetapi algortima ini cukup praktis untuk digunakan dalam pewarnaan  simpul  sebuah  graf  dan  hanya  cocok digunakan untuk graf dengan orde yang kecil.
Adapun langkah-langkah dari Algoritma Welch Powell ini dinyatakan sebagai berikut :
a) Mendaftarkan  simpul-simpul  dalam  graf  G kemudian  mengurutkan  berdasarkan  derajat yang tinggi ke rendah.
b) Menggunakan  satu  warna  untuk  mewarnai simpul  pertama  yang  mempunyai  derajat paling tinggi dan mewarnai pula simpul-simpul lain  yang  tidak  bertetangga  dengan  simpul pertama sesuai daftar terurut .
c) Melakukan  hal  yang  sama  dengan  langkah kedua yang memiliki derajat tertinggi berikutnya  dalam  daftar  terurut  yang  masih belum  diwarnai  dengan  menggunakan  warna kedua yang berbeda dengan warna pertama.
d) Melakukan  pewarnaan  dan  berhenti  sampai semua simpul telah diwarnai.
Dari  algoritma  ini  dapat  dibuat flow  chart  sebagai berikut:
Gambar 2 . Flowchart Algoritma Welch Powell
Selanjutnya  untuk  studi  kasus  sendiri  peneliti tertarik  untuk  mewarnai  peta  kota  makassar  yang memiliki  14  kecamatan  yang  dijadikan  wilayah (religion). Pemilihan kota Makassar dianggap dapat memberikan kasus yang baik untuk pewarnaan graf karena simpul yang tidak terlalu banyak juga tidak terlalu  sedikit  dan  juga  lokasi  pengambilan  data yang  cukup  dekat  sehingga  lebih  memudahkan dalam melakukan penelitian.

## II. METODE PENELITIAN
Metode penelitian yang digunakan oleh penulis adalah  studi  kasus  yang  bertujuan  mengumpulkan informasi  berupa  peta  kota  Makassar  yang didapatkan langsung  dari kantor  Dinas tata ruang kota Makassar atau yang berkaitan.
Adapun Prosedur penelitian yang akan digunakan dalam mencapai tujuan penelitian adalah sebagai berikut:
1. Melakukan  pewarnaan  graf  menggunakan Algoritma Sequential dengan  menggunakan langkah-langkah sebagai berikut: a. Mengumpulkan  data  atau  informasi  berupa peta Kota Makassar.
b. Menggambarkan  ulang  peta  kota  Makassar dengan  menggunakan  software  Editing Corel Draw X7 dengan tanpa warna
c. Merepresentasikan  peta  kota  Makassar kedalam  bentuk  graf  dengan  Wilayah kecamatan  berupa  Simpul  (simpul)  dan wilayah yang berdekatan dihubungkan oleh sebuah sisi
d. Menggunakan  algoritma  Sequential  untuk melakukan pewarnaaan
2. Melakukan  pewarnaan  graf  menggunakan Algoritma Welch Powell dengan menggunakan langkah-langkah sebagai berikut:
a. Mengumpulkan  data  atau  informasi  berupa peta Kota Makassar.
b. Menggambarkan  ulang  peta  kota  Makassar dengan  menggunakan  software  Editing Corel Draw atau photoshop
c. Merepresentasikan  peta  kota  Makassar kedalam  bentuk  graf  dengan  Wilayah kecamatan  berupa  Simpul  (simpul)  dan wilayah yang berdekatan dihubungkan oleh sebuah sisi.
d. Menggunakan  algoritma  Welch  Powell untuk melakukan pewarnaaan
3. Membuat  tabel  perbandingan  warna  dan bilangan  kromatik  antara  kedua  algoritma  dan juga pewarnaan sebelumnya.

## III. HASIL DAN PEMBAHASAN
Berikut merupakan gambar peta kota Makassar
Gambar 3 . Peta kota Makassar
Langkah  selanjutnya  yaitu  menggambar ulang kembali peta dalam keadaan tanpa warna dan
menginterpretasikan  peta  kedalam  bentuk  graf sebagai berikut:
Gambar 4 . Interpretasi peta kedalam graf
Sehingga didpatkan perbaikan bentuk graf sebagai berikut:
Gambar 5 . Graf peta kota Makassar
Dimana : 𝑉 1 = Kec.Wajo 𝑉 2 = Kec.Ujung pandang 𝑉 3 = Kec.Mariso 𝑉 4 = Kec.Ujung Tanah
𝑉 5 = Kec.Bontoala
𝑉 6 = Kec.Makassar
𝑉 7 = Kec.Mamajang
𝑉 8 = Kec.Tamalate
𝑉 9 = Kec.Tallo
𝑉 10 = Kec.Panakukang
𝑉 11 = Kec.Rappocini 𝑉 12 = Kec.Tamalanrea 𝑉 13 = Kec.Manggala 𝑉 14 = Kec.Biringkanaya
Langkah  selanjutnya  yaitu  melakukan  pewarnaan graf  dengan  menggunakan  kedua  algoritma  yaitu algoritma Sequential dan Algoritma Welch Powell.
1. Algoritma  Sequential  dalam  menyelesaikan
pewarnaan peta kota Makassar
Langkah pertama dengan menggunakan algoritma  ini  yaitu  menginput  simpul  ( v )  dan  (e) yang ada dalam Graf 𝐺 = (𝐸, 𝑉) 𝑉 = {𝑉 1 , 𝑉 2 , 𝑉 3 , 𝑉 4 , 𝑉 5 , 𝑉 6 , 𝑉 7 , 𝑉 8 , 𝑉 9 , 𝑉 10 , 𝑉 11 , 𝑉 12 , 𝑉 13 , 𝑉 14 } 𝐸     = { (𝑉 1 , 𝑉 2 ), (𝑉 1 , 𝑉 4 ), (𝑉 1 , 𝑉 5 ), (𝑉 2 , 𝑉 3 ), (𝑉 2 , 𝑉 5 ), (𝑉 2 , 𝑉 6 ), (𝑉 2 , 𝑉 7 ), (𝑉 3 , 𝑉 7 ), (𝑉 3 , 𝑉 8 )
, (𝑉 4 , 𝑉 5 ), (𝑉 4 , 𝑉 9 ), (𝑉 5 , 𝑉 6 ), (𝑉 5 , 𝑉 9 ), (𝑉 5 , 𝑉 10 ), (𝑉 6 , 𝑉 7 ), (𝑉 6 , 𝑉 10 ), (𝑉 6 , 𝑉 11 ), (𝑉 7 , 𝑉 8 ) , (𝑉 7 , 𝑉 11 ), (𝑉 8 , 𝑉 11 ), (𝑉 9 , 𝑉 10 ), (𝑉 9 , 𝑉 12 ), (𝑉 10 , 𝑉 11 ), (𝑉 10 , 𝑉 12 ), (𝑉 10 , 𝑉 13 ), (𝑉 11 , 𝑉 13 ) , (𝑉 12 , 𝑉 13 ), (𝑉 12 , 𝑉 14 ) }
Adapun nilai 𝐿 𝑖 untuk setiap 𝑖 = 1, … ,14 𝐿 1 = 〈1〉 𝐿 2 = 〈1,2〉
𝐿 3 = 〈1,2,3〉
𝐿 4 = 〈1,2,3,4〉
𝐿 5 = 〈1,2,3,4,5〉 𝐿 6 = 〈1,2,3,4,5,6〉 𝐿 7 = 〈1,2,3,4,5,6,7〉 𝐿 8 = 〈1,2,3,4,5,6,7,8〉 𝐿 9 = 〈1,2,3,4,5,6,7,8,9〉 𝐿 10 = 〈1,2,3,4,5,6,7,8,9,10〉 𝐿 11 = 〈1,2,3,4,5,6,7,8,9,10,11〉 𝐿 12 = 〈1,2,3,4,5,6,7,8,9,10,11,12〉 𝐿 13 = 〈1,2,3,4,5,6,7,8,9,10,11,12,13〉 𝐿 14 = 〈1,2,3,4,5,6,7,8,9,10,11,12,13,14〉
Langkah  berikutnya  yaitu  melakukan  perulangan dari 𝑖 = 1 sampai 14 dan 𝑗 = 1 sampai 14 untuk melakukan  update 𝐿 𝑖 setiap  kali  perulangan  dan mendapatkan nilai 𝐶 𝑖 . Dari perhitungan diatas maka diperoleh  warna  setiap  simpulnya  yaitu 𝐶 1 = 1 , 𝐶 2 = 2 , 𝐶 3 = 1, 𝐶 4 = 2 , 𝐶 5 = 3 , 𝐶 6 = 1 , 𝐶 7 = 3 , 𝐶 8 = 2 , 𝐶 9 = 1 , 𝐶 10 = 2 , 𝐶 11 = 4 , 𝐶 12 = 3 , 𝐶 13 = 1 , dan 𝐶 14 = 2 .
Dari  sini  dapat  diperoleh  warna  masing-masing simpul  yaitu 𝑉 1 = 1 , 𝑉 2 = 2 , 𝑉 3 = 1 , 𝑉 4 = 2 , 𝑉 5 = 3 , 𝑉 6 = 1 , 𝑉 7 = 3 , 𝑉 8 = 2 , 𝑉 9 = 1 , 𝑉 10 = 2 , 𝑉 11 = 4 , 𝑉 12 = 3 , 𝑉 13 = 1 dan 𝑉 14 = 2 .  Misalkan  kita beri 1 untuk warna merah, 2 untuk warna kuning, 3 untuk  warna  hijau,  4  untuk  warna  biru,  maka diperoleh graf  dan peta yang telah diwarnai sebagai berikut;
Gambar 6. Graf peta kota Makassar yang telah diwarnai dengan Algoritma Sequential
Gambar 7 . Peta kota Makassar yang telah diwarnai
2. Algoritma
Welch Powell dalam menyelesaikan pewarnaan peta kota Makassar
Adapun langkah-langkah dari Algoritma Welch-Powell  yang  pertama  adalah  mendaftarkan simpul-simpul  dalam  graf  beserta  tetangga  dan derajatnya.
Tabel 1 .Simpul dalam graf beserta tetangga dan derajatnya No Simpul Tetangga Derajat 1 𝑉 1 𝑉 2 , 𝑉 4 , 𝑉 5 3 2 𝑉 2 𝑉 1 , 𝑉 3 , 𝑉 5 , 𝑉 6 , 𝑉 7 5 3 𝑉 3 𝑉 2 , 𝑉 7 , 𝑉 8 3 4 𝑉 4 𝑉 1 , 𝑉 5 , 𝑉 9 3 5 𝑉 5 𝑉 1 , 𝑉 2 , 𝑉 4 , 𝑉 6 , 𝑉 9 , 𝑉 10 6 6 𝑉 6 𝑉 2 , 𝑉 5 , 𝑉 7 , 𝑉 10 , 𝑉 11 5 7 𝑉 7 𝑉 2 , 𝑉 3 , 𝑉 6 , 𝑉 8 , 𝑉 11 5 8 𝑉 8 𝑉 3 , 𝑉 7 , 𝑉 11 3 9 𝑉 9 𝑉 4 , 𝑉 5 , 𝑉 10 , 𝑉 12 4 10 𝑉 10 𝑉 5 , 𝑉 6 , 𝑉 9 , 𝑉 11 , 𝑉 12 , 𝑉 13 6 11 𝑉 11 𝑉 6 , 𝑉 7 , 𝑉 8 , 𝑉 10 , 𝑉 13 5 12 𝑉 12 𝑉 9 , 𝑉 10 , 𝑉 14 3 13 𝑉 13 𝑉 10 , 𝑉 11 , 𝑉 12 3 14 𝑉 14 𝑉 12
Selanjutnya mengurutkan berdasarkan derajat yang tinggi ke rendah
Tabel 2 .Urutan simpul berdasarkan derajat terbesar ke terkecil
No Simpul Tetangga Derajat 1 𝑉 5 𝑉 1 , 𝑉 2 , 𝑉 4 , 𝑉 6 , 𝑉 9 , 𝑉 10 6 2 𝑉 10 𝑉 5 , 𝑉 6 , 𝑉 9 , 𝑉 11 , 𝑉 12 , 𝑉 13 6 3 𝑉 2 𝑉 1 , 𝑉 3 , 𝑉 5 , 𝑉 6 , 𝑉 7 5 4 𝑉 6 𝑉 2 , 𝑉 5 , 𝑉 7 , 𝑉 10 , 𝑉 11 5 5 𝑉 7
𝑉 2 , 𝑉 3 , 𝑉 6 , 𝑉 8 , 𝑉 11 5 6 𝑉 11 𝑉 6 , 𝑉 7 , 𝑉 8 , 𝑉 10 , 𝑉 13 5 7 𝑉 9 𝑉 4 , 𝑉 5 , 𝑉 10 , 𝑉 12 4 8 𝑉 12 𝑉 9 , 𝑉 10 , 𝑉 13 , 𝑉 14 4 9 𝑉 1 𝑉 2 , 𝑉 4 , 𝑉 5 3 10 𝑉 3 𝑉 2 , 𝑉 7 , 𝑉 8 3 11 𝑉 4 𝑉 1 , 𝑉 5 , 𝑉 9 3 12 𝑉 8 𝑉 3 , 𝑉 7 , 𝑉 11 3 13 𝑉 13 𝑉 10 , 𝑉 11 , 𝑉 12 3 14 𝑉 14 𝑉 12 1
Menggunakan satu warna pertama misalkan warna merah  untuk  mewarnai  simpul  pertama    yaitu 𝑉 5 yang mempunyai derajat paling tinggi dan simpul- simpul  lain  yang  tidak  bertetangga  dengan  simpul pertama  atau  simpul  yang  telah  terpilih  dengan urutan berdasarkan derajat tertinggi
𝑉 5 = warna merah 𝑉 10 = tidak diberi warna karena bertetangga dengan 𝑉 5 𝑉 2 =  tidak  diberi  warna  karena  bertetangga  dengan 𝑉 5 𝑉 6 =  tidak  diberi  warna  karena  bertetangga  dengan 𝑉 5
𝑉 7 = warna merah
𝑉 12 = warna merah
𝑉 11 = tidak diberi warna karena bertetangga dengan 𝑉 7
𝑉 9 =  tidak  diberi  warna  karena  bertetangga  dengan 𝑉 5
𝑉 1 =  tidak  diberi  warna  karena  bertetangga  dengan 𝑉 5
𝑉 3 =  tidak  diberi  warna  karena  bertetangga  dengan 𝑉 7
𝑉 4 =  tidak  diberi  warna  karena  bertetangga  dengan 𝑉 5
𝑉 8 =  tidak  diberi  warna  karena  bertetangga  dengan 𝑉 7
𝑉 13 = tidak diberi warna karena bertetangga dengan 𝑉 12
𝑉 14 = tidak diberi warna karena bertetangga dengan 𝑉 12
Langkah  selanjutnya  yaitu  melakukan  hal  yang sama  dengan  langkah  sebelumnya  yang  memiliki derajat  tertinggi  berikutnya  dalam  daftar  terurut yang  masih  belum  diwarnai  dengan  menggunakan warna  kedua  yaitu  warna  kuning.  Setelah    semua simpul  selesai  diwarnai  maka  diperoleh  warna simpul 𝑉 5 , 𝑉 7 , 𝑉 12 berwarna merah, simpul 𝑉 2 , 𝑉 4 , 𝑉 8 , 𝑉 10 , 𝑉 14 berwarna kuning, simpul 𝑉 1 , 𝑉 3 , 𝑉 6 , 𝑉 9 , 𝑉 13 berwarna  hijau,  dan  simpul 𝑉 11 berwarna  biru  sehingga  dapat  diberi  pewarnaan pada graf dan peta sebagai berikut:
Gambar.8 . Graf peta kota Makassar yang telah diwarnai dengan Algoritma Welch Powell
Gambar 9 .  Peta kota Makassar yang telah diwarnai dengan Algoritma Welch Powell
Tabel  3 .  pewarnaan  peta  berdasarkan  kedua algoritma dan warna sebelumnya
No Daerah Peta sebelum nya Algoritma Sequential Algoritma Welch Powell 1 Kec.Wajo 2 Kec.Ujung pandang 3 Kec.Maris o 4 Kec.Ujung Tanah 5 Kec.Bonto ala 6 Kec.Maka ssar
7 Kec.Mam
ajang 8 Kec.Tama late
9 Kec.Tallo
10 Kec.Panak ukang 11 Kec.Rapp ocini 12 Kec.Tama lanrea 13 Kec.Mang gala 14 Kec.Birin gkanaya Jumlah warna 𝜒(𝐺) 12 4 4
Berdasarkan  Tabel  3  diperoleh  perbandingan warna  untuk  setiap  kecamatan,  dimana  pada pewarnaan  peta  dengan  menggunakan  kedua algoritma  yaitu  algoritma  Sequential  dan  Welch Powell, sama-sama menghasilkan bilangan kromatik 𝜒(𝐺) = 4 .  Karena  memiliki  Bilangan kromatik  yang  sama  maka  Algoritma  Sequential tidak  lebih  baik  dari  Algoritma  Welch  Powell, ataupun sebaliknya Algoritma Welch Powell tidak lebih  baik  dari  Algoritma  Sequential  untuk  kasus pewarnaan peta pada kota Makassar. Adapun pada pewarnaan peta sebelumnya atau tanpa menggunakan algoritma yaitu menghasilkan jumlah warna atau 𝜒(𝐺) = 12 . Pada penggunaan algoritma Sequential dan Welch Powell, keduanya jauh lebih efektif  karena  warna  yang  digunakan  sedikit sehingga  hanya  perlu  menggunakan  warna-warna popular  seperti  merah,  kuning,  biru  dan  hijau. Sedangkan pada pewarnaan
peta sebelumnya, selain menggunakan warna-warna popular  juga  memungkinkan  untuk  menggunakan warna-warna gradasi disebabkan banyaknya warna yang harus digunakan.

## IV. KESIMPULAN DAN SARAN
Kesimpulan dari penelitian ini adalah Algoritma  Sequential  dapat  diimplementasikan untuk mewarnai peta kota Makassar. Pada algoritma Sequential  diperoleh  warna  untuk  masing-masing daerah  yaitu  kec.Wajo  berwarna  merah,  kec.ujung pandang  berwarna  kuning,  kec.mariso  berwarna merah, kec.ujung tanah berwarna kuning, kec.bontoala berwarna hijau, kec.makassar berwarna  merah,  kec.mamajang  berwarna  hijau, kec.tamalate  berwarna  kuning,  kec.tallo  berwarna merah, kec.panakukang berwarna kuning, kec.rappocini berwarna biru, kec.tamalanrea berwarna  hijau,  kec.manggala  berwarna  merah, kec.biringkanaya berwarna kuning.
Begitupun  dengan  Algoritma  Welch  Powell dapat diimplementasikan untuk mewarnai peta kota Makassar. Pada algoritma Welch Powell diperoleh warna untuk masing-masing daerah yaitu kec.Wajo berwarna  hijau,  kec.ujung  pandang  berwarna kuning, kec.mariso berwarna hijau, kec.ujung tanah berwarna  kuning,  kec.bontoala  berwarna  merah, kec.makassar berwarna hijau, kec.mamajang berwarna  merah,  kec.tamalate  berwarna  kuning, kec.tallo berwarna hijau, kec.panakukang berwarna kuning, kec.rappocini berwarna biru, kec.tamalanrea  berwarna  merah,  kec.manggala berwarna hijau, kec.biringkanaya berwarna kuning.
Pada  algoritma  Sequential  dan  algoritma Welch  Powell  sama-sama  menghasilkan  Bilangan kromatik 𝜒(𝐺) = 4 .  Kedua  algoritma  juga  jauh lebih  efektif  dibandingkan  pewarnaan  peta sebelumnya atau tanpa algoritma dimana menghasilkan  jumlah  warna  atau    Bilangan kromatik 𝜒(𝐺) = 12 .
Adapun  saran  untuk  penelitian  berikutnya  yaitu mewarnai peta yang lebih kompleks yakni memiliki region  (wilayah  )  yang  lebih  banyak  dan menggunakan  algoritma  lain  untuk  melakukan pewarnaan
V. DAFTAR PUSTAKA
[1] R.  M.  R.  Lewis, A  Guide  to  Graph Colouring . 2016.
[2] W.  Kocay  and  D.  L.  Kreher, Graphs, algorithms, and optimization . 2017.
[3] Assma  Laputty,  “Penggunaan  Metode Greedy  Pada  Pengaturan  Lampu  Lalu Lintas  Jalan  Di  Perempatan  Al-Fatah Ambon  Dengan  Teori  Graph,” J.  Pros.
Konfrensi  Nas.  Ilmu  Komput.  (KONIK , Vol. 2, pp. 147–151, 2014.
[4] R. Munir,
Matematika Disktrit . Bandung: Informatika Bandung, 2010.
[5] A.  Kosowski  and  K.  Manuszewski, “Classical coloring of graphs,” pp. 1–19, 2004.
[6] K.  P.  Sari,  “Perbandingan  Algoritma Pewarnaan LDO , SDO , dan IDO pada Graf Sederhana.”
[7] F.  Ardiansyah  and  M.  Syaifullah, “Implementasi Algoritma Greedy Untuk Melakukan Graph Coloring: Studi Kasus Peta  Propinsi  Jawa  Timur,” J.  Inform. ,
2012.
[8] A.  M.  Soimah  and  N.  S.  M.  Mussafi, “Pewarnaan  Simpul  Dengan  Algoritma Welch-Powell  Pada  Traffic  Light  Di Yogyakarta,” J. Fourier , vol. 2, no. 2, p. 73, 2013.
[9] Binti  Ida  Umaya,  “Implementasi
Algoritma Tabu Search Dalam Pewarnaan Simpul Graf (STUDI KASUS :  Penjadwalan  mata  kuliah jurusan  matematika  fakultas  sains  dan teknologi  UIN  Alauddin  Makassar),”
Univ. Nusant. PGRI Kediri , vol. 1, pp. 1–
7, 2017.
[10]  H. Turosdiah, Armiati, and M. P. Dewi, “Penerapan  Pewarnaan  Titik  pada  Graf dalam Penyusunan Lokasi Duduk Menggunakan Algoritma Greedy Berbantuan Microsoft Visual Basic 6.0,” UNP J. Math. , vol. 2, no. 1, 2014.
[11]  N.  Selma  Karamy,  “Pewarnaan  Titik Pada Graf Dengan Menggunakan Algoritma Pewarnaan Barisan Sederhana Dalam Penataan Buku Perpustakaan,”  in Conference on Research & Community Services , 2019, pp. 557–565.
[12]  T.  S.  N.  Anggraini,  Lana  Aristya, Rosyida,  Isnaini  ,Asih,  “Penyelesaian Masalah Pewarnaan Graf Dengan
Algoritma  Genetika,”  vol.  8,  no.  1,  pp. 30–39, 2019.
[13]  R.  J.  Noor,  H.  Hendra,  and  W.  Powell, “Implementasi  Algoritma  Baris  dalam Pewarnaan  Titik  pada  Graf  Sederhana
Implementation of Sequent Algorithm in Coloring Vertex on Simple Graph,” vol.
1, no. 1, pp. 19–22, 2013. [14]  P. Studi and T. Informatika, “Perbandingan Algoritma,” no. 13512025, pp. 1–13, 2014.
[15]  M.  Ammar,  “Penyusunan  Jadwal  Ujian Mata  Kuliah  Semester  V  Jurusan Matematika  Uin  Alauddin  Makassar,” pp. 299–303.