Volume 3, No. 1, 2021, pp. 41-55 http://dx.doi.org/10.21580/square.2021.3.1.7410

## Aplikasi Pewarnaan Graf Peta Provinsi Riau Menggunakan Algoritma Greedy
Ade Novia Rahma 1 , Rahmawati 2 , Zukrianto 3*
1, 2, 3 UIN Sultan Syarif Kasim Riau
* zukrianto@yahoo.co.id

## ABSTRAK
Penelitian ini membahas tentang aplikasi pewarnaan graf pada peta Provinsi Riau  menggunakan algoritma Greedy .  Dalam  aplikasi  pewarnaan  graf  tersebut,  terdapat  beberapa  langkah  yang dikerjakan. Pertama mengubah gambar peta Provinsi Riau ke dalam bentuk graf. Kedua pewarnaan setiap  kabupaten  di  Provinsi  Riau  menggunakan  algoritma Greedy .  Hasil  akhirnya  didapatkan pewarnaan graf di Provinsi Riau membutuhkan sebanyak empat warna yang berbeda.
Kata kunci: algoritma Greedy , pewarnaan wilayah, teori graf.

## ABSTRACT
This study discusses the application of graphcoloring on maps of Riau Province using the Greedy algorithm. In the coloring graph  application, there are several steps  that are  carried out.  First, change  the  map  image  of  Riau  Province  into  graphic  form.  The  second,  colorizations  for  each district in Riau province use the Greedy algorithm. The final result is that graph coloring in Riau Province requires four different colors.
Keywords: Greedy algorithm, region coloring, graph theory.

## 1. PENDAHULUAN
Teori  graf  merupakan  topik  yang  banyak  mendapat  perhatian  saat  ini,  karena  model- model yang ada pada teori graf berguna untuk aplikasi yang luas. Walaupun teori graf berasal dari bidang ilmu Matematika, namun pada penerapannya, teori graf dapat dihubungkan dengan berbagai bidang ilmu dan juga kehidupan sehari-hari. Sedemikian banyaknya pengaplikasian graf dalam dunia ini, bila perlu dikatakan tidak ada habis-habisnya jika dibahas setiap aplikasi graf, karena setiap bidang ilmu dapat  dikaitkan  dengan graf seperti  masalah dalam jaringan komunikasi, transportasi, ilmu komputer, riset  operasi, ilmu kimia, sosiologi, kartografi dan lain sebagainya.  Teori-teori  mengenai  graf  ini  telah  banyak  dikembangkan  dengan  berbagai algoritma yang memiliki kelebihan dan kelemahan masing-masing dalam menyelesaikannya. Graf adalah himpunan pasangan tak berurut antara simpul ( vertices atau node ) dan sisi ( edges atau arcs ).
Dalam  kartografi,  suatu  peta  dianggap  baik  dan  benar  jika  mudah  dimengerti  oleh pembacanya yaitu jika dilengkapi dengan legenda, skala peta, judul peta, tata warna, simbol, dan  proyeksi  peta  (Sandy,  1986).  Salah  satu  manfaat  tata  warna  peta  yaitu  memudahkan seseorang  dalam  mengenali  beberapa  negara  yang  berbatasan  langsung.  Dalam  sebuah  peta tergambar wilayah-wilayah yang dimiliki antar negara dan untuk membedakan wilayah antar negara tersebut, digunakan beberapa warna yang berbeda-beda. Jumlah warna yang berlebihan menyebabkan peta menjadi tidak efisien. Untuk itu diperlukan sebuah metode untuk melakukan pewarnaan peta menggunakan jumlah warna minimal.
Dalam teori graf, permasalahan dalam penentuan jumlah warna minimal yang bisa dibuat pada suatu representasi graf dikenal dengan bilangan kromatik (Wilson, 2004). Brun (2002) membahas  banyak  dalam  kajiannya,  salah  satunya  tentang  Teorema  Empat  Warna  yang menyatakan bahwa sebuah peta dapat diwarnai dengan menggunakan maksimal empat warna. Teori  pewarnaan  graf  dapat  diaplikasikan  dalam  penentuan  warna  pada  sebuah  peta  yang dikenal sebagai pewarnaan wilayah. Ada beberapa penelitian terdahulu yang berkaitan secara tidak langsung dengan penelitian ini. Penelitian yang dilakukan oleh Hastuti (2011) membahas tentang  pewarnaan  Wilayah  Peta  Kabupaten  Indragiri  Hulu  dan  Kampar  dengan  Aplikasi Algoritma  Greedy.  Selanjutnya  penelitian  Mussafi  (2015)  masih  membahas  tentang Greedy Coloring  Algorithm pada  Peta  Kotamadya  Yogyakarta  Berbasis Four-Colour  Theorem . Kemudian Daswa & Riyadi (2017) melakukan penelitian yang sedikit berbeda Pewarnaan Graf pada Masalah Penyusunan Jadwal Perkuliahan di Universitas Kuningan. Selanjutnya penelitian oleh Supiyandi & Eka (2018) yang telah melakukan penelitian Penerapan Teknik Pewarnaan Graph Pada Penjadwalan Ujian dengan Algoritma Welch-Powell ”. Kemudian pewarnaan graf juga dibahas oleh Bustan & Salim (2019) Pewarnaan Graf Menggunakan Algoritma Welch- Powell untuk Menentukan Jadwal Bimbingan Mahasiswa.
Penelitian  dalam  artikel  ini  sejalan  dengan  penelitian  yang  dilakukan  Mussafi  (2015) yaitu penggunaan Algoritma Greedy untuk menentukan bilangan kromatik suatu graf namun dengan objek penelitian yang berbeda. Tujuan dari penelitian ini adalah menerpkan Algoritma G reedy pada  peta  Provinsi  Riau  sehingga  dapat diperoleh  peta alternatif dengan  pewarnaan minimal melalui analisis graf.

## 2. METODE

## 2.1. Landasan Teori
Metode  penelitian  yang  digunakan  penulis  yaitu  dengan  cara  studi  pustaka  (literatur), yaitu  dengan  mempelajari  buku-buku,  jurnal  atau  artikel  serta  sumber-sumber  yang berhubungan dengan penelitian ini.

## Definisi 1 (Munir, 2014)
“Graf G didefinisikan  sebagai  pasangan  himpunan ) , ( E V dinyatakan  dengan  notasi
) , ( E V
G  . Dalam hal ini, V adalah himpunan tidak kosong dari simpul (vertices dan node) dan E adalah himpunan sisi ( edges atau arcs ) yang menghubungkan sepasang simpul.”
Definisi 2 (Munir, 2014)
“Dua simpul dikatakan bertetangga apabila kedua simpul tersebut terhubung secara langsung oleh suatu sisi. Dengan kata lain, simpul u bertetangga dengan v jika ) , ( v u adalah sebuah sisi pada graf G .”

## Definisi 3 (Munir, 2014)
“Suatu  sisi  dikatakan  bersisian  dengan  dua  simpul  apabila  menghubungkan  kedua  simpul tersebut secara langsung.”
Definisi 4 (Munir, 2014)
“Pada graf tidak berarah, derajat suatu simpul  adalah banyaknya sisi yang bersisian dengan simpul tersebut. Sedangkan dalam graf berarah, derajat suatu simpul ( v ) merupakan jumlah dari banyaknya busur yang masuk ke simpul ( in ) dengan banyaknya busur yang keluar dari simpul ( out ).”

## Definisi 5 (Munir, 2014)
“Lintasan dari sebuah graf adalah barisan satu atau lebih sisi yang dilalui dari suatu simpul awal ke simpul tujuan. Panjang suatu lintasan adalah banyaknya sisi yang dilewati dari simpul awal ke simpul tujuan.”

## Definisi 6 (Munir, 2014)
“Pewarnaan graf adalah  pemberian warna yang biasanya direpresentasikan sebagai bilangan terurut  mulai  dari  1  hingga  seterusnya  atau  dapat  juga  direpresentasikan  langsung  dengan menggunakan  warna  merah,  biru,  atau warna  lainnya  pada  suatu  graf.  Objek  tersebut  dapat berupa  simpul,  sisi  dan  wilayah.  Setiap  simpul  yang  berdekatan  atau  bertetangga  tidak mempunyai warna yang sama).”
Terdapat  persoalan  dalam  pewarnaan  graf,  yaitu  mewarnai  graf  tidak  hanya  sekedar memberikan  warna  pada  simpul-simpul  dengan  warna  yang  berbeda  dengan  warna  simpul tetangganya  saja,  namun  dalam  mewarnainya  juga  menginginkan  jumlah  jenis  warna  yang sedikit.

## Definisi 7 (Amrimirza, 2007)
Algoritma Greedy merupakan  metode  yang  paling  populer  untuk  memecahkan  persoalan optimasi. Algoritma Greedy dalam pewarnaan graf adalah sebagai berikut.
1. Inisialisasi himpunan solusi dengan himpunan kosong.
2. Pemilihan simpul yang akan diisi warnanya dengan fungsi seleksi simpul.
3. Memilih kandidat warna dengan menggunakan fungsi seleksi warna. Kurangi warna pada kandidat C jika warna diambil dari himpunan kandidat C.
4. Periksa kelayakan warna yang dipilih menggunakan fungsi kelayakan. Warna yang layak digunakan untuk simpul terpilih akan dimasukkan ke dalam himpunan solusi, jika tidak layak maka proses kembali ke langkah 2.
5. Periksa  apakah  solusi  sudah  meliputi  pewarnaan  seluruh  simpul  dengan  solusi  optimal menggunakan  fungsi  objektif.  Proses  pewarnaan  akan  berhenti  jika  pewarnaan  telah mendapatkan solusi optimal, jika belum optimal kembali ke langkah 2.

## 2.2.  Metodologi Penelitian
Penelitian ini bertujuan untuk mendapatkan pewarnaan graf minimum untuk peta wilayah Provinsi Riau dengan langkah-langkah sebagai berikut.
1. Menentukan batas-batas wilayah kabupaten untuk Provinsi Riau.
2. Mempresentasikan peta Provinsi Riau dalam graf dengan menjadikan batas-batas wilayah kabupaten sebagai sisi dan perpotongan antar batas wilayah sebagai simpul.
3. Mentukan derajat masing-masing simpul.
4. Melakukan pewarnaan peta Provinsi Riau menggunakan Algoritma Greedy .
5. Menentukan jumlah warna minimum yang diperoleh untuk mewarnai peta.

## 3. HASIL DAN PEMBAHASAN

## 3.1.   Representasi Graf Peta Wilayah Provinsi Riau
Gambar  1  adalah  gambar  peta  wilayah  Provinsi  Riau.  Provinsi  Riau  terdiri  dari  12 kabupaten yang memiliki batas-batas wilayahnya. Peta Provinsi Riau dapat direpresentasikan ke  dalam  sebuah  graf  dengan  menjadikan  batas-batas  wilayah  kabupaten  sebagai  sisi  dan perpotongan  antar  batas  wilayah  sebagai  simpul.  Representasi  daerah  Provinsi  Riau  dalam suatu graf diperlihatkan pada Gambar 2.
Gambar 1. Peta Provinsi Riau (Sumber: Google)
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11
Gambar 2. Peta Provinsi Riau dalam Bentuk Graf
Pada  Gambar  2,  masing-masing  titik  merepresentasikan  kabupaten-kabupaten  yang berada di Provinsi Riau dengan keterangan sebagai berikut.
r1 : Kabupaten Rokan Hilir r7 : Kabupaten Kampar r2 : Kabupaten Dumai r8 : Kabupaten Kuantan Singgigi r3 : Kabupaten Rokan Hulu r9 : Kabupaten Pelalawan r4 : Kabupaten Bengkalis r10  : Kabupaten Indragiri Hulu r5 : Kabupaten Siak r11  : Kabupaten Indragiri Hilir r6 : Kabupaten Pekanbaru r12  : Kabupaten Kepulauan Meranti
Dari Gambar 2, dapat dibuat Tabel 1 yang meringkas banyaknya derajat pada masing- masing simpul.
Tabel 1. Derajat Simpul Graf Peta Provinsi Riau
Simpul r1 r2  r3  r4  r5  r6  r7  r8 r9  r10  r11  r12 Derajat 3 2 4 4 5 3 5 3 6 3 2 0

## 3.2.   Pewarnaan Peta Provinsi Riau Menggunakan Algoritma Greedy
Pewarnaan  peta  Provinsi  Riau  dengan  menggunakan  Algoritma  Greedy  mengikuti langkah-langkah berikut.
1. Membangun Himpunan Kandidat C
Himpunan kandidat C akan digunakan untuk mewarnai peta Provinsi Riau elemen- elemen-nya  terdiri  dari  7  jenis  warna,  yakni  C  =  {Merah, Biru,  Ungu,  Kuning,  Coklat, Hijau, Pink }.

## 2. Inisialisasi Himpunan Solusi S
Inisialisasi  himpunan  solusi  dengan  kosong  karena  pada  tahap  selanjutnya  nanti himpunan  solusi  akan  memuat  elemen  warna  yang  telah  digunakan  untuk  mewarnai simpul. Himpunan S = { }.

## 3. Mengurutkan Simpul
Berdasarkan  Tabel  1,  dapat  dibentuk  kembali  Tabel  2  yang  berisikan  urutan berdasarkan jumlah derajat dari yang paling banyak hingga yang paling sedikit.
Tabel 2. Pengurutan Simpul Peta Provinsi Riau berdasarkan Jumlah Derajat Terbanyak
Simpul r9 r5  r7  r3  r4  r1  r6  r8  r10  r2  r11  r12 Derajat 6 5 5 4 4 3 3 3 3 2 2 0

## 4. Fungsi Seleksi
a. Fungsi Seleksi Simpul
Tahap  seleksi  simpul  ini  akan  dipilih  simpul  awal  yang  akan  di  warnai  terlebih dahulu. Simpul yang memiliki jumlah derajat terbanyak menjadi prioritas pengerjaan. Berdasarkan Tabel 2, simpul yang memiliki derajat terbanyak adalah simpul r9 maka dipilih simpul r9.
b. Fungsi Seleksi Warna
Tahap selanjutnya yaitu memilih warna yang akan digunakan untuk simpul r9, pada tahap seleksi warna dibagi kembali kedalam dua tahap. Tahap pertama adalah dengan mengambil  warna  dari  himpunan  solusi.  Warna  diuji  apakah  layak  untuk  digunakan kembali.  Jika  tidak  satupun  warna  dari  himpunan  solusi  layak  atau  himpunan  solusi masih  kosong,  akan  diambil  warna  dari  himpunan  kandidat  C  yang  belum  pernah digunakan.
Seleksi warna dari himpunan kandidat, warna yang akan digunakan simpul r9 ambil dari himpunan kandidat warna, dipilih warna merah yang merupakan kandidat warna pertama dari himpunan kandidat C. Selanjutnya, karena elemen kandidat warna pertama telah digunakan satu elemen maka elemen himpunan kandidat C tinggal 6 anggota yaitu C = {Biru, Ungu, Kuning, Coklat, Hijau, Pink }.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11
Gambar 3. Pewarnaan pada Simpul r9

## 5. Fungsi Kelayakan
Akan diperiksa kelayakan warna merah yang digunakan untuk simpul r9, dapat dilihat dari  matriks  ketetanggaannya.  Simpul  r9  bertetangga  dengan  enam  buah  simpul  yang belum diwarnai, sehingga warna merah layak digunakan untuk simpul r9.
6. Himpunan Solusi
Warna  merah  yang  sudah  digunakan  untuk  simpul  r9  otomatis  masuk  ke  dalam himpunan solusi. Himpunan solusi yang terbentuk yaitu S = {Merah}.
7. Fungsi Objektif
Tahap ini untuk memeriksa apakah solusi sudah meliputi pewarnaan seluruh simpul dengan solusi optimal, jika sudah maka berhenti dan jika belum kembali ke langkah seleksi simpul, karena pewarnaan simpul masih simpul r9, maka proses kembali ke langkah seleksi simpul.
8. Langkah Seleksi Simpul r5
Simpul yang akan diwarnai selanjutnya adalah simpul yang memiliki derajat paling banyak kedua yaitu simpul r5 dan simpul r7. Simpul yang dipilih simpul r5. Lalu diseleksi warna yang dianggap layak digunakan untuk simpul r5, ditahap sebelumnya warna merah diambil sebagai kandidat warna,  sehingga pada  tahap ini diambil kembali warna merah sebagai kandidat warna dengan diperiksa kelayakannya dengan melihat simpul tetangga dari simpul r5. Ternyata simpul r5 bertetangga dengan simpul r9 sehingga warna merah tidak layak sebagai himpunan solusi.
Selanjutnya  dilakukan  seleksi  warna  kembali  dan  kandidat  warna  diambil  dari himpunan kandidat warna yang baru yaitu warna biru sehingga anggota himpunan kandidat warnanya  sekarang  adalah  C  =  {Ungu,  Kuning,  Coklat,  Hijau, Pink }.  Setelah  warna diambil  maka  akan  diperiksa  kembali  kelayakannya.  Simpul  yang  bertetangga  dengan simpul  r5  tidak  berwarna biru sehingga  biru  layak  digunakan  pada  simpul r5.  Langkah selanjutnya adalah memasukkan warna biru ke himpunan solusi S = {Merah, Biru}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11
Gambar 4. Pewarnaan pada Simpul r5

## 9. Langkah Seleksi Simpul r7
Selanjutnya  akan  dilakukan  seleksi  warna  yang  akan  digunakan  untuk  simpul  r7. Warna diambil dari himpunan solusi, dipilih elemen pertama dari himpunan solusi yaitu warna merah. Periksa kelayakan warna merah dengan melihat simpul tetangga dari simpul r7. Ternyata simpul r7 bertetangga dengan simpul r9 sehingga warna merah tidak layak sebagai himpunan solusi.
Selanjutnya  pilih  warna  dari himpunan  solusi  dan  dipilih  warna  kedua yaitu  warna biru. Periksa kelayakan warna biru pada simpul r7. Ternyata simpul r7 bertetangga dengan simpul r5 sehingga warna biru juga tidak layak sebagai himpunan solusi.
Selanjutnya  diambil  warna  baru  dari  himpunan  kandidat  warna  yaitu  warna  ungu. Sehingga anggota himpunan kandidatnya sekarang menjadi C = {Kuning, Coklat, Hijau, Pink }.  Setelah  warna  diambil  maka  akan diperiksa kembali  kelayakannya,  simpul yang bertetangga dengan simpul r7 tidak berwarna ungu sehingga ungu layak digunakan pada simpul  r7.  Langkah  selanjutnya  adalah  memasukkan  warna  ungu  ke  himpunan  solusi sehingga S = {Merah, Biru, Ungu}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11

## Gambar 5. Pewarnaan pada Simpul r7

## 10. Langkah Seleksi Simpul r3
Selanjutnya  dilakukan  seleksi warna  yang  akan  digunakan  untuk  simpul  r3.  Warna diambil dari himpunan solusi, dipilih warna merah. Periksa kelayakan warna merah dengan melihat  simpul  tetangga  dari  simpul  r3.  Simpul  r3  layak  diwarnai  menggunakan  warna merah  karena  tidak  ada  simpul  tetangganya  memiliki  warna  yang  sama.  Langkah selanjutnya adalah memasukkan warna merah ke himpunan solusi sehingga S = {Merah, Biru, Ungu}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11

## Gambar 6. Pewarnaan pada Simpul r3

## 11. Langkah Seleksi Simpul r4
Selanjutnya  akan  diseleksi  warna  yang  dianggap  layak  digunakan  untuk  simpul  r4. Diambil  warna  dari  himpunan  solusi,  dipilih  warna  merah.  Diperiksa  kelayakan  warna merah,  simpul  r4  bertetangga  dengan  simpul  r3  yang  berwarna  merah  sehingga  warna merah tidak layak digunakan untuk simpul r4.
Selanjutnya diambil warna lain dari himpunan solusi yaitu warna biru. Simpul r5 yang bertetangga dengan simpul r4 sudah menggunakan warna biru sehingga warna biru tidak layak digunakan untuk simpul r4.
Selanjutnya  diambil  warna  ungu  dari  himpunan  solusi  kemudian  periksa  kembali kelayakannya. Simpul yang bertetangga dengan simpul r4 tidak ada yang berwarna ungu sehingga  warna  ungu  layak  digunakan  pada  simpul  r4.  Langkah  selanjutnya  adalah memasukkan warna ungu ke himpunan solusi sehingga S = {Merah, Biru, Ungu}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11
Gambar 7. Pewarnaan pada Simpul r4

## 12. Langkah Seleksi Simpul r1
Selanjutnya  akan diseleksi  warna yang dianggap  layak  digunakan  untuk  simpul r1. Diambil  warna  dari  himpunan  solusi,  dipilih  warna  merah.  Diperiksa  kelayakan  warna merah,  simpul  r1  bertetangga  dengan  simpul  r3  yang  berwarna  merah  sehingga  warna merah tidak layak digunakan untuk simpul r1.
Selanjutnya  diambil  warna  biru  dari  himpunan  solusi  kemudian  periksa  kembali kelayakannya. Simpul yang bertetangga dengan simpul r1 tidak ada yang berwarna biru sehingga  warna  biru  layak  digunakan  pada  simpul  r1.  Langkah  selanjutnya  adalah memasukkan warna biru ke himpunan solusi sehingga S = {Merah, Biru, Ungu}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11

## Gambar 8. Pewarnaan pada Simpul r1

## 13. Langkah Seleksi Simpul r6
Selanjutnya  akan diseleksi  warna yang dianggap  layak  digunakan  untuk  simpul r6. Diambil  warna  dari  himpunan  solusi,  dipilih  warna  merah.  Diperiksa  kelayakan  warna merah,  simpul  r6  bertetangga  dengan  simpul  r9  yang  berwarna  merah  sehingga  warna merah tidak layak digunakan untuk simpul r6.
Selanjutnya diambil warna lain dari himpunan solusi yaitu warna biru. Simpul r5 yang bertetangga dengan simpul r6 sudah menggunakan warna biru sehingga warna biru tidak layak  digunakan untuk  simpul  r6. Selanjutnya diambil warna lain  dari himpunan solusi yaitu  warna  ungu.  Simpul  r7  yang  bertetangga  dengan  simpul  r6  sudah  menggunakan warna ungu sehingga warna ungu juga tidak layak digunakan untuk simpul r6.
Selanjutnya diambil warna baru dari himpunan kandidat warna yaitu warna kuning. Sehingga  anggota  himpunan  kandidatnya  sekarang  menjadi  C  =  {Coklat,  Hijau, Pink }. Setelah  warna  diambil  maka  akan  diperiksa  kembali  kelayakannya,  simpul  yang bertetangga  dengan  simpul  r6  tidak  berwarna  kuning  sehingga  kuning  layak  digunakan pada  simpul  r6.  Langkah  selanjutnya  adalah  memasukkan  warna  kuning  ke  himpunan solusi sehingga S = {Merah, Biru, Ungu, Kuning}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11

## Gambar 9. Pewarnaan pada Simpul r6

## 14. Langkah Seleksi Simpul r8
Selanjutnya  akan  diseleksi  warna  yang  dianggap  layak  digunakan  untuk  simpul  r8. Diambil  warna  dari  himpunan  solusi,  dipilih  warna  merah.  Diperiksa  kelayakan  warna merah,  simpul  r8  bertetangga  dengan  simpul  r9  yang  berwarna  merah  sehingga  warna merah tidak layak digunakan untuk simpul r8.
Selanjutnya  diambil  warna  biru  dari  himpunan  solusi  kemudian  periksa  kembali kelayakannya. Simpul yang bertetangga dengan simpul r8 tidak ada yang berwarna biru sehingga  warna  biru  layak  digunakan  pada  simpul  r8.  Langkah  selanjutnya  adalah memasukkan warna biru ke himpunan solusi sehingga S = {Merah, Biru, Ungu, Kuning}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11

## Gambar 10. Pewarnaan pada Simpul r8

## 15. Langkah Seleksi Simpul r10
Selanjutnya akan diseleksi warna yang dianggap layak digunakan untuk simpul r10. Diambil  warna  dari  himpunan  solusi,  dipilih  warna  merah.  Diperiksa  kelayakan  warna merah,  simpul r10 bertetangga dengan  simpul r9  yang berwarna merah sehingga warna
merah  tidak  layak  digunakan  untuk  simpul  r10.  Selanjutnya  diambil  warna  lain  dari himpunan solusi yaitu warna biru. Simpul r8 yang bertetangga dengan simpul r10 sudah menggunakan warna biru sehingga warna biru tidak layak digunakan untuk simpul r10.
Selanjutnya  diambil  warna  ungu  dari  himpunan  solusi  kemudian  periksa  kembali kelayakannya. Simpul yang bertetangga dengan simpul r10 tidak ada yang berwarna ungu sehingga  warna  ungu  layak  digunakan  pada  simpul  r10.  Langkah  selanjutnya  adalah memasukkan warna ungu ke himpunan solusi sehingga S = {Merah, Biru, Ungu, Kuning}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11
Gambar 11. Pewarnaan pada Simpul r10

## 16. Langkah Seleksi Simpul r2
Selanjutnya  akan diseleksi  warna yang dianggap  layak  digunakan  untuk  simpul r2. Diambil  warna  dari  himpunan  solusi,  dipilih  warna  merah.  Diperiksa  kelayakan  warna merah, simpul yang bertetangga dengan simpul r2 tidak ada yang berwarna merah sehingga warna merah layak digunakan pada simpul r2 . Langkah selanjutnya adalah memasukkan warna merah ke himpunan solusi sehingga S = {Merah, Biru, Ungu, Kuning}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11
Gambar 12. Pewarnaan pada Simpul r2

## 17. Langkah Seleksi Simpul r11
Selanjutnya akan diseleksi warna yang dianggap layak digunakan untuk simpul r11. Diambil  warna  dari  himpunan  solusi,  dipilih  warna  merah.  Diperiksa  kelayakan  warna merah,  simpul r11 bertetangga dengan  simpul r9  yang berwarna merah sehingga warna merah tidak layak digunakan untuk simpul r11.
Selanjutnya diambil warna lain dari himpunan solusi yaitu warna biru. Simpul yang bertetangga dengan simpul r11 tidak ada yang berwarna biru sehingga warna biru layak digunakan  pada  simpul  r11.  Langkah  selanjutnya  adalah  memasukkan  warna  biru  ke himpunan solusi sehingga S = {Merah, Biru, Ungu, Kuning}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11

## Gambar 13. Pewarnaan pada Simpul r11

## 18. Langkah Seleksi Simpul r12
Selanjutnya  akan  dilakukan  seleksi  warna  yang  akan  digunakan  untuk  simpul  r12. Warna diambil dari himpunan solusi, dipilih warna merah. Periksa kelayakan warna merah dengan melihat simpul tetangga dari simpul r12. Simpul r12 layak diwarnai menggunakan warna  merah  karena  tidak  memiliki  simpul  tetangganya.  Langkah  selanjutnya  adalah memasukkan warna merah ke himpunan solusi sehingga S = {Merah, Biru, Ungu, Kuning}.
r7 r10 r8 r9 r4 r1 r2 r5 r3 r12 r6 r11
Gambar 14. Pewarnaan pada Simpul r12
19. Fungsi Objektif
Karena seluruh simpul sudah diwarnai maka proses pewarnaan graf berhenti. Didapat himpunan solusi S = {Merah, Biru, Ungu, Kuning}.

## 3.3.   Menentukan Jumlah Warna Minimum Peta Provinsi Riau
Jumlah warna minimum atau bilangan kromatik yang telah diperoleh setelah dilakukan pewarnaan  graf  menggunakan  Algoritma Greedy pada  peta  Provinsi  Riau  dapat  diwarnai menggunakan empat warna seperti pada Gambar 15.
Gambar 15. Pewarnaan Wilayah Provinsi Riau
Keterangan: r1 : Kabupaten Rokan Hilir r7 : Kabupaten Kampar r2 : Kabupaten Dumai r8 : Kabupaten Kuantan Singgigi r3 : Kabupaten Rokan Hulu r9 : Kabupaten Pelalawan r4 : Kabupaten Bengkalis r10  : Kabupaten Indragiri Hulu r5 : Kabupaten Siak r11  : Kabupaten Indragiri Hilir r6 : Kabupaten Pekanbaru r12  : Kabupaten Kepulauan Meranti

## 4. SIMPULAN
Dari hasil pembahasan yang telah dilakukan dapat disimpulkan bahwa pewarnaan peta Provinsi Riau dengan Algoritma Greedy diperoleh bilangan kromatik χ (G) = 4. Hal ini sesuai dengan  pembahasan  Brun  (2002)  tentang the  four  colour  theorem yang  menyatakan  bahwa sebuah peta dapat diwarnai dengan maksimal empat warna. Dari hasil pewarnaan peta Provinsi Riau menggunakan Algoritma Greedy, diperoleh bahwa algoritma ini lebih rinci dan sistematis. Banyak  langkah-langkah  yang  dilakukan  pada  Algoritma  Greedy  sehingga  membutuhkan ketelitian yang lebih.

## 5. DAFTAR PUSTAKA
Amrimirza,  M.  (2007)  Aplikasi  Algoritma  Greedy  pada  Pewarnaan  Peta, Makalah  IF2251 Strategi Algoritmik . 1-4.
Brun, Yuriy. (2002). The Four-Color Theorem. Undergraduate Journal of Mathematics. 21–28.
Bustan, A. W., & Salim, M. R. (2019). Penerapan Pewarnaan Graf Menggunakan Algoritma Welch-Powell Untuk Menentukan Jadwal Bimbingan Mahasiswa. Jurnal THEOREMS (The Original Research of Mathematics), 4(1), 79-86.
Daswa  &  Riyadi,  M.  (2017).  Aplikasi  Pewarnaan  Graf  Pada  Masalah  Penyususnan  Jadwal Perkuliahan Di Universitas Kuningan. JES-MAT, 3(2), 217-226 .
Hastuti, W. F. (2011). Aplikasi algoritma Greedy untuk pewarnaan wilayah (region coloring) pada  peta  kabupaten  indragiri  hulu  dan  kampar  di  provinsi  riau .  Program  Sarjana Universitas Islam Negeri Sultan Syarif Kasim Riau, Pekanbaru.
Munir, R. (2014). Matematika Diskrit Revisi Kelima. Bandung: Penerbit Informatika Bandung.
Mussafi,  N.  S.  M.  (2015).  Penerapan  Greedy  Coloring  Algorithm  Pada  Peta  Kotamadya Yogyakarta Berbasis Four-Colour Theorem. Kaunia, vol. XI No. 1, April, 19-26.
Supiyandi &  Eka, M. (2018). Penerapan Teknik  Pewarnaan  Graph Pada  Penjadwalan  Ujian dengan Algoritma Welch-Powell. ALGORITMA: Jurnal Ilmu Komputer dan Informatika, 03(01), 58-63.
Rosen, K. H. (1999). Discrete Mathematics & Applications. McGraw-Hill.