Pewarnaan Wilayah (Region Coloring),...Sagita Charolina,...Sainmatika,...Volume 13,...No.1,...Juni 2016,...60-77

## PEWARNAAN WILAYAH ( REGION COLORING ) PADA PETA KABUPATEN OGAN ILIR SUMATERA SELATAN MENGGUNAKAN ALGORITMA GREEDY
Sagita Charolina Sihombing e-mail: sagita@univpgri-palembang.ac.id
Fakultas MIPA, Universitas PGRI Palembang

## ABSTRACT
Region Coloring is not just make a different color in a Regency. It is also to determine how many color  will be  used optimally. This  research used  graph teory  with  Greedy algorithm to determine the kind of color at the map of Ogan Ilir Regent. Obtained that with four kind of color, Ogan Ilir Regent can be colored.
Keywords: Graph Theory, Greedy Algorithm, Region Coloring

## ABSTRAK
Pewarnaan wilayah bukanlah hanya sekedar memberikan warna yang berbeda pada suatu  wilayah. Tetapi  juga untuk  menentukan jumlah jenis warna  yang optimal pada  pewarnaa  tersebut.  Pada  penelitian  ini,  digunakan  teori  graf  dengan  algoritma Greedy untuk  menentukan jenis  warna  yang optimal pada peta Kabupaten Ogan  Ilir. Didapat bahwa dengan empat jenis warna, Kabupaten Ogan Ilir dapat diwarnai.
Kata kunci: Teori Graf, Algoritma Greedy , Pewarnaan Wilayah

## PENDAHULUAN
Teori graf merupakan topik yang sampai saat  ini menarik  perhatian para ahli karena topik ini dapat diaplikasikan  dalam  banyak  bidang diantaranya  dalam  mencari  lintasan terpendek pengambilan keputusan dengan menggunakan pohon
keputusan,  perancangan  navigasi  web, pemodelan  sidik  jari,  mencari  jumlah warna  minimal  untuk  pewarnaan  peta dan lain sebagainya.
Graf didefinisikan sebagai pasangan  himpunan ,  dengan adalah  himpunan  tidak  kosong  dari simpul-simpul  ( verticers atau node )  =
dan himpunan  sisi ( edges atau arca ) yang menghubungkan sepasang simpul atau dapat ditulis dengan notasi
. Untuk  pewarnaan  suatu  peta, teori graf diperlukan karena peta terdiri atas  sejumah  wilayah.  Wilayah  yang dimaksud dapat menyatakan kecamatan,  kabupaten,  provinsi  atau Negara.  Peta  diwarnai  sedemikian sehingga  dua  wilayah  bertetangga mempunyai warna berbeda.
Kabupaten  Ogan  Ilir  merupakan salah  satu  kabupaten  yang  terdapat  di wilayah  Sumatera  Selatan.  Kabupaten ini  terdiri  dari  16  kecamatan.  Pada penelitian ini, teori graf akan diaplikasikan  pada  pewarnaan  peta
untuk  mencari  jumlah  warna  minimal yang harus digunakan untuk membedakan masing-masing kecamatan. Salah  satu  algoritma  yang  dapat digunakan  untuk  menentukan  jumlah warna  minimum  pada  pewarnaan  graf adalah algoritma Greedy, yang dikembangkan  oleh  Li  Yu,  et  all berjudul  “ Greedy  Agorithms  for  the
Minumum  Sum  Coloring  Problem ”
telah  dipublikasikan  di Logistique  et transport , Souse: Tunisia (2009) Volume I, 28 Januari 2010. Berdasarkan  latar  belakang  tersebut, pada  penelitian  ini  akan  dibahas pewarnaan  peta  dengan  jumlah  warna minimal menggunakan algoritma
Greedy .
Pewarnaan  Graf .  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 mungkin (Munir, 2005).
Algoritma Greedy . Algoritma  Greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi. Cara  kerja  algoritma Greedy dalam pewarnaan  graf  diberikan  sebagai berikut (Amrimirza, 2007):
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

## BAHAN DAN METODE
Metode yang digunakan dalam penelitian  ini  adalah  studi  literatur. Langkah-langkah yang digunakan dalam  pengerjaan  penelitian  ini  adalah sebagai berikut:
1. Menentukan  batas-batas  wilayah kecamatan  untuk  Kabupatan  Ogan Ilir 2. Merepresentasikan batas-batas wilayah  kecamatan  sebagai  sisi dan perpotongan antar batas wilayah sebagai simpul
3. Menentukan graf dual antar wilayah  kecamatan  dari  peta Kabupaten Ogan Ilir
4. Merepresentasikan  graf  dual  antar wilayah  kecamatan  ke  dalam matriks ketetanggaan
5. Menentukan derajat masing-
masing simpul dari matriks
ketetanggaan  yang  sudah  dibuat sebelumnya
6. Melakukan pewarnaan peta Kabupaten Ogan Ilir dengan menggunakan  algoritma Greedy untuk  setiap  simpul  dari  simpul berderajat  tertinggi  sampai  simpul dengan derajat terkecil 7. Menentukan jumlah warna minimum  yang  diperoleh  untuk mewarnai peta

## HASIL DAN PEMBAHASAN
Kabupaten Ogan Ilir berada di wilayah provinsi Sumatera Selatan. Wilayah ini saling  bertetangga  dengan  kabupaten lainnya  di  provinsi  Sumatera  Selatan. Kabupaten  ini  memiliki  luas  2.666,07 Km 2 .
Kabupaten Ogan Ilir berada di wilayah provinsi Sumatera Selatan. Wilayah ini saling  bertetangga  dengan  kabupaten lainnya  di  provinsi  Sumatera  Selatan. Kabupaten  ini  memiliki  luas  2.666,07 Km 2 . Wilayah Kabupaten Ogan Ilir Berdasarkan  data  yang  didapat  dari website Kabupaten Ogan Ilir http://www.oganilirkab.go.id/p/kondisi -wilayah.html diakses pada 15 Agustus
2016  pukul  16:18,  jumlah  kecamatan dan luas wilayah kecamatan Kabupaten Ogan Ilir adalah sebagai berikut: Tabel 1. Nama Kecamatan dan Luas Wilayah Kecamatan

## Kabupaten Ogan Ilir
No Kecamatan Luas Wilayah (Km 2 ) 1 Indralaya 101,22 2 Indralaya Utara 472,33 3 Indralaya Selatan 100,26 4 Pemulutan 122,92 5 Pemulutan Barat 60,00 6 Pemulutan Selatan 61,49 7 Tanjung Batu 263,75 8 Payaraman 180,57 9 Tanjung Raja 70,41 10 Sungai Pinang 42,62 11 Rantau Panjang 40,85 12 Muara Kuang 300,75 13 Rambang Kuang 528,82 14 Lubuk Keliat 207,67 15 Rantau Alai 62,16 16 Kandis 50,25 Total 2.666,07
Pada  Tabel  1  dapat  dilihat  bahwa Kabupaten  Ogan  Ilir  terdiri  dari  16 kecamatan  dengan  wilayah  kecamatan terluas  adalah  Kecamatan  Rambang Kuang  (528,82Km 2 ).  Kecamatan  ini
berbatasan  dengan  Kecamatan  Rantau Alai,  Kecamatan  Kandis,  Kecamatan
Muara Kuang dan Kecamatan Payaraman.  Batasan  wilayah  ini  dapat dilihat pada Gambar 1.
Gambar 1. Peta Wilayah Kabupaten Ogan Ilir Setiap kecamatan bertetanggaan dengan kecamatan lainnya. Kecamatan
Muara  Kuang  bertetangga  dengan Kecamatan  Rambang  Kuang  dan Kecamatan  Lubuk  Keliat.  Sedangkan Kecamatan  Lubuk  Keliat  bertetangga dengan  Kecamatan  Muara  Karang,
Kecamatan Rambang Kuang, Kecamatan  Payaraman,  Kecamatan Rantau  Alai,  dan  Kecamatan  Tanjung Batu.  Masing-masing  kecamatan  ada yang bertetangga dengan dua
kecamatan,  ada  tiga  kecamatan  dan yang  paling  banyak  adalah  Kecamatan Tanjung Batu yang bertetangga dengan tujuh kecamatan.

## Cara  Mempresentasikan  Wilayah
Kabupaten  Ogan  Olir  ke  dalam

## Suatu Graf
Untuk  merepresentasikan  Kabupaten Ogan Ilir ke dalam suatu graf, langkah pertama  adalah  dengan  memberikan indeks sesuai dengan jumlah kecamatan wilayah seperti yang diberikan pada Tabel 2. Tabel  2.  Indeks  Kecamatan  Kabupaten Ogan Ilir Indeks Kecamatan Nama Kecamatan R1 Indralaya R2 Indralaya Utara R3 Indralaya Selatan R4 Pemulutan R5 Pemulutan Barat R6 Pemulutan Selatan R7 Tanjung Batu R8 Payaraman R9 Tanjung Raja R10 Sungai Pinang R11 Rantau Panjang R12 Muara Kuang R13 Rambang Kuang R14 Lubuk Keliat R15 Rantau Alai R16 Kandis
Dengan  pengindeksan  sesuai  dengan yang  diberikan  pada  Tabel  2,  masing- masing  wilayah  kecamatan  dibentuk kedalam  16  indeks.  Adapun  hasil pengindeksan wilayah dinyatakan pada Gambar 2:
Gambar 2. Peta Wilayah Kabupaten Ogan Ilir
Selanjutnya  Kabupaten  Ogan  Ilir dibentuk  ke  dalam  verteks  sebagai perpotongan  antar  wilayah.  Kabupaten Ogan  Ilir  membentuk  27  verteks seperti  yang ditunjukkan pada Gambar 3 di bawah ini.
Gambar 3. Wilayah Kabupaten Ogan Ilir terdiri dari 27 simpul dan  42 sisi
Berdasarkan Gambar 3, didapat bahwa:

## Graf Dual dari Peta Kabupaten Ogan Olir
Berdasarkan Gambar 3, dapat dibuat graf dual dari peta Kabupaten Ogan Ilir dengan simpul dan sisi sebagai berikut:
Graf dual dari peta Kabupaten Ogan Ilir diberikan pada Gambar 4 berikut:
Gambar 4. Graph Dual Peta Kabupaten Ogan Ilir
Membentuk  Matrik  Ketetanggaan

## Peta Kabupaten Ogan Ilir
Adapun  matriks  ketetanggaan  peta Kabupaten  Ogan  Ilir  yang  terdiri  dari 16 kecamatan dapat dibentuk ke dalam matriks sebagai berikut:
Derajat  Simpul  Peta  Kabupaten
Ogan Ilir
Berdasarkan matriks ketetanggaan pada  peta  Kabupaten  Ogan  Ilir,  dapat disusun  derajat  simpul  seperti  pada Tabel 3.
Tabel 3. Derajat Simpul Peta Kabupaten Ogan Ilir No Wilayah Kecamatan Simpul Graf Derajat Simpul 1 Indralaya 1 3 2 Indralaya Utara 2 2 3 Indralaya Selatan 3 5 4 Pemulutan 4 3 5 Pemulutan Barat 5 4 6 Pemulutan Selatan 6 2 7 Tanjung Batu 7 7 8 Payaraman 8 5 9 Tanjung Raja 9 4 10 Sungai Pinang 10 4 11 Rantau Panjang 11 3 12 Muara Kuang 12 5 13 Rambang Kuang 13 3 14 Lubuk Keliat 14 4 15 Rantau Alai 15 4 16 Kandis 16 4
Pewarnaan  Peta  Kabupaten  Ogan Ilir Menggunakan Algoritma Greedy Berikut  ini  diberikan  tahap  dalam pewarnaan Peta Kabupaten Ogan Ilir 1. Membangun himpunan kandidat warna Himpunan kandidat warna yang akan digunakan untuk
mewarnai  peta  kabupaten  ini elemennya  terdiri  dari  10  jenis warna  yang  disebut  sebagai himpunan kandidat C.
C = {Merah, Biru, Hijau, Ungu,
Orange,  Biru  Muda,  Kuning, Pink, Coklat, Abu-abu} 2. Melakukan inisialisasi himpunan solusi S Inisialisasi  himpunan  solusi dengan himpunan kosong karena  pada  tahap  selanjutnya nanti  himpunan  solusi  akan memuat  elemen  warna  yang telah digunakan untuk mewarnai  simpul.  Himpunan  S = {}. 3. Mengurutkan simpul Simpul  diurutkan  berdasarkan jumlah derajat dari  yang paling besar  hingga  yang  paling  kecil. Melakukan  pewarnaan  pada graf  dimulai  dari  simpul  yang memiliki  jumlah  derajat  paling banyak. Tabel 4. Derajat Simpul Peta Kabupaten Ogan Ilir Yang Sudah Diurutkan berdasarkan

## Jumlah Derajat Simpul
No  Wilayah Kecamatan Simpul Graf Derajat Simpul 1 Tanjung Batu 7 7 2 Indralaya Selatan 3 5 3 Payaraman 8 5 4 Muara Kuang 12 5 5 Pemulutan Barat 5 4 6 Tanjung Raja 9 4 7 Sungai Pinang 10 4 8 Lubuk Keliat 14 4 9 Rantau Alai 15 4 10 Kandis 16 4 11 Indralaya 1 3 12 Pemulutan 4 3 13 Rantau Panjang 11 3 14 Rambang Kuang 13 3 15 Indralaya Utara 2 2 16 Pemulutan Selatan 6 2 4. Fungsi Seleksi
Fungsi  seleksi  ini  terbagi  menjadi dua yaitu:
a. Fungsi seleksi simpul Tahap  seleksi  simpul  ini  akan dipilih  simpul  awal  yang  akan diwarnai  terlebih  dahulu.  Prioritas pengerjaan  dilihat  dari  simpul yang mempunyai simpul terbanyak.  Berdasarkan  seleksi
simpul  dari  Tabel  4,  simpul  yang memiiki  derajat  terbanyak  adalah simpul 7 maka dipilih simpul 7.
b. Fungsi seleksi warna
Tahap  selanjutnya  yaitu  memilih warna  yang  akan digunakan untuk simpul 7, pada tahap seleksi warna ini  dibagi  kembali  kedalam  dua tahap.  Tahap  pertama  adalah dengan  mengambil  warna  dari
himpunan  solusi.  Warna  ini  diuji apakah  layak  untuk  digunakan kembali.  Jika  tidak  satupun  warna dari  himpunan  solusi  layak  atau himpunan  solusi  masih  kosong, akan  diambil  warna  dari  himpuan kandidat C, yaitu warna yang sama sekali belum digunakan.
Seleksi  warna  dari  himpunan kandidat, warna yang akan
digunakan untuk  simpul  7 diambil dari  himpunan  kandidat  warna,
dipilih warna merah yang merupakan kandidat warna pertama  dari  himpunan  kandidat
C.  Selanjutnya,  elemen  himpunan kandidat  C  sekarang  tinggal  9 anggota jenis warna yaitu: C  =  {Biru,  Hijau,  Ungu,  Orange, Biru  Muda,  Kuning,  Pink,  Coklat, Abu-abu}
5. Fungsi Kelayakan
Tahap ini akan memeriksa kelayakan  warna  merah  yang digunakan untuk simpul 7, dengan penyesuaian dari matriks ketetanggaannya. Simpul 7 bertetangga  dengan  tujuh  buah simpul  yang  belum  diwarnai, sehingga  warna  merah  dianggap layak digunakan untuk simpul 7.
6. Himpunan Solusi
Warna merah yang telah digunakan  untuk  simpul  7  di  atas,
dimasukkan  ke  dalam  himpunan solusi  karena  dianggap  layak.
Himpunan  solusi  yang  terbentuk yaitu: S = {Merah} Gambar 5. Pewarnaan pada Simpul 7 7. Fungsi Objektif Fungsi ini untuk memeriksa apakah  solusi  sudah  meliputi pewarnaan  seluruh  simpul  dengan solusi  optimal.  Karena  pewarnaan simpul masih pada simpul 7, maka proses  kembai  ke  langkah  seleksi simpul.
8. Simpul yang akan diwarnai selanjutnya adalah ke simpul yang mempunyai  derajat  paling  banyak kedua,  yaitu  simpul  3,  8,  dan  12, dipilih  simpul  3.  Selanjutnya  akan diseleksi  warna  yang  dianggap layak  digunakan  untuk  simpul  3. Pada  tahap  ini  diambil  warna  dari himpunan  solusi  yaitu  warna merah.  Periksa  kelayakan  warna merah,  dengan  melihat  simpul tetangga  dari  simpul  3.  Simpul yang bertetangga dengannya adalah simpul 7, telah diberi warna merah.  Sehingga,  merah  tidak layak  digunakan  untuk  simpul  3. Selanjutnya untuk simpul 3 diambil warna baru dari himpunan kandidat  warna  yaitu  warna  biru, sehingga  anggota  himpunannya sekarang adalah:
C  =  {Hijau,  Ungu,  Orange,  Biru
Muda, Kuning, Pink, Coklat, Abu- abu} Setelah  warna  diambil  maka  akan diperiksa  kembali  kelayakannya, simpul  yang  bertetangga  dengan simpul  3  tidak  ada  berwarna  biru sehingga  biru  layak  digunakan pada simpul ini.
Pewarnaan  pada  simpul  3  dapat dilihat pada Gambar 6 berikut:
Gambar 6. Pewarnaan pada Simpul 3 Langkah selanjutnya adalah memasukkan warna biru ke dalam himpunan  solusi,  sehingga  S  = {Merah, Biru} 9. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 8
Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Warna  akan  diambil dari  himpunan  solusi,  dipilih elemen  pertama  dari  himpunan solusi  yaitu  merah  yang  akan digunakan. Periksa kelayakan warna dengan melihat simpul yang bertetangga  dengan  simpul  8. Setelah  diperiksa  ternyata  warna tersebut  telah  digunakan  pada
simpul  7  yang bertetangga dengan simpul 8, sehingga warna ini tidak layak  digunakan  untuk  simpul  8. Selanjutnya adalah memilih warna lain  dari  himpunan  solusi  yaitu warna  biru.  Simpul  8  layak  diberi warna biru karena bukan merupakan simpul yang bertetangga  dengan  simpul  3. Sehingga  elemen  himpunan  C masih  sama  dengan  himpunan sebelumnya yaitu: C  =  {Hijau,  Ungu,  Orange,  Biru Muda, Kuning, Pink, Coklat, Abu- abu}.  Simpul  10  yang  telah diwarnai dapat dilihat pada Gambar 4.7 berikut: Gambar 7. Pewarnaan pada Simpul 8 10. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 12
Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Warna  akan  diambil dari  himpunan  solusi,  dipilih elemen  pertama  dari  himpunan solusi  yaitu  merah  yang  akan digunakan. Periksa kelayakan warna dengan melihat simpul yang bertetangga  dengan  simpul  12.
Setelah  diperiksa  ternyata  warna
tersebut  telah  digunakan  pada simpul  7  yang bertetangga dengan simpul  12,  sehingga  warna  ini tidak layak digunakan untuk simpul  12.  Selanjutnya  adalah memilih warna lain dari himpunan solusi yaitu warna biru. Simpul 12 layak  diberi  warna  biru  karena tidak  merupakan  simpul  yang bertetangga  dengan  simpul  3  dan 8.  Sehingga  elemen  himpunan  C masih  sama  dengan  himpunan sebelumnya yaitu:
C  =  {Hijau,  Ungu,  Orange,  Biru Muda, Kuning, Pink, Coklat, Abu- abu}.  Simpul  12  yang  telah diwarnai dapat dilihat pada
Gambar 8  berikut: Gambar 8. Pewarnaan pada
Simpul 12
11. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 5 Selanjutnya dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Karena  warna  Merah dan  Biru  sudah  digunakan  untuk simpul  yang  bertetangga  dengan simpul  5,  maka  warna  Merah  dan
Biru  tidak  layak  digunakan  untuk simpul 5. Selanjutnya untuk
simpul  5  diambil  warna  baru  dari
himpunan  kandidat  warna  yaitu warna  Hijau.  Warna  yang  diambil untuk  mewarnai  simpul  5  diambil dari  himpunan  kandidat  warna, sehingga  anggota  himpunannya sekarang adalah:
C  =  {Ungu,  Orange,  Biru  Muda, Kuning, Pink, Coklat, Abu-abu} Setelah  warna  diambil  maka  akan diperiksa  kembali  kelayakannya, simpul  yang  bertetangga  dengan simpul 5 tidak ada berwarna Hijau sehingga  Hijau  layak  digunakan pada simpul ini.
Pewarnaan  pada  simpul  5  dapat dilihat pada gambar berikut:
Gambar 9. Pewarnaan pada Simpul 5 12. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 9 Selanjutnya dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna Merah.  Setelah  warna  diambil maka  akan  diperiksa  kembali kelayakannya, simpul yang
bertetangga dengan simpul 9 tidak ada  berwarna  Merah  sehingga Merah  layak  digunakan  pada simpul ini.
Pewarnaan  pada  simpul  9  dapat dilihat pada Gambar 10:
Gambar 10. Pewarnaan pada Simpul 9 13. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 10
Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna merah.  Setelah  warna  diambil maka akan diperiksa kelayakannya,  simpul  9  yang bertetangga  dengan  simpul  10 sudah diberi warna Merah sehingga Merah tidak layak digunakan pada simpul ini. Selanjutnya  diambil  warna  lain dari  himpunan  solusi  yaitu  warna Biru.  Simpul  8  yang  bertetangga dengan simpul 10 sudah menggunakan warna Biru, sehingga  warna  Biru  tidak  layak digunakan untuk simpul 10. Selanjutnya  diambil  lagi  warna Hijau  dari  himpunan  solusi  dan kemudian diperiksa kembali kelayakannya. Simpul yang bertetangga  dengan  simpul  10
tidak  ada  yang  berwarna  Hijau
sehingga  Hijau  layak  digunakan pada simpul ini.
Pewarnaan  pada  simpul  10  dapat dilihat pada Gambar 11:
Gambar 11. Pewarnaan pada Simpul 10 14. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 14 Selanjutnya dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna Merah.  Setelah  warna  diambil maka  akan  diperiksa  kembali kelayakannya, simpul yang bertetangga  dengan  simpul  14 tidak ada berwarna Merah sehingga  Merah  layak  digunakan pada  simpul  ini.  Pewarnaan  pada simpul  14  dapat  dilihat  pada Gambar 12:
Gambar 12. Pewarnaan pada
Simpul 14 15. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 15 Selanjutnya akan dilakukan seleksi
warna  yang  akan digunakan untuk simpul ini.
Diambil  warna  dari  himpunan solusi, dipilih warna merah. Setelah  warna  diambil  maka  akan diperiksa kelayakannya, simpul 14 yang  bertetangga  dengan  simpul 15  sudah  diberi  warna  Merah sehingga Merah tidak layak digunakan pada simpul ini. Selanjutnya  diambil  warna  lain dari  himpunan  solusi  yaitu  warna Biru. Simpul  12 yang bertetangga dengan simpul 15 sudah menggunakan warna Biru, sehingga  warna  Biru  tidak  layak digunakan untuk simpul 15. Selanjutnya  diambil  lagi  warna Hijau  dari  himpunan  solusi  dan kemudian diperiksa kembali kelayakannya. Simpul yang bertetangga  dengan  simpul  15 tidak ada berwarna Hijau sehingga Hijau layak digunakan pada simpul ini.
Pewarnaan  pada  simpul  15 dapat dilihat pada Gambar 13:
Gambar 13. Pewarnaan pada Simpul 15 16. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 16 Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul ini.
Diambil  warna  dari  himpunan solusi, dipilih warna Merah.
Setelah  warna  diambil  maka  akan diperiksa kelayakannya, simpul 14 yang  bertetangga  dengan  simpul
16  sudah  diberi  warna  Merah sehingga Merah tidak layak digunakan pada simpul ini. Selanjutnya  diambil  warna  lain dari  himpunan  solusi  yaitu  warna Biru.  Simpul  yang  bertetangga dengan  simpul  16  tidak  ada  yang berwarna Biru sehingga Biru layak digunakan pada simpul ini.
Pewarnaan  pada  simpul  16 dapat dilihat pada Gambar 14.
Gambar 14. Pewarnaan pada Simpul 16 17. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 1 Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna Merah.  Setelah  warna  diambil maka  akan  diperiksa  kembali kelayakannya, simpul yang bertetangga dengan simpul  1 tidak ada yang berwarna Merah
sehingga  Merah  layak  digunakan pada  simpul  ini.  Pewarnaan  pada simpul  1  dapat  dilihat  pada Gambar 15:
Gambar 15. Pewarnaan pada Simpul 1
18. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 4 Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna merah.  Setelah  warna  diambil maka akan diperiksa kelayakannya,  simpul  1  yang bertetangga  dengan  simpul  4 sudah diberi warna Merah sehingga Merah tidak layak digunakan pada simpul ini. Selanjutnya  diambil  warna  lain dari  himpunan  solusi  yaitu  warna Biru.  Simpul    3  yang  bertetangga dengan simpul 4 sudah menggunakan warna Biru, sehingga  warna  Biru  tidak  layak digunakan untuk simpul 4. Selanjutnya  diambil  lagi  warna Hijau  dari  himpunan  solusi  dan kemudian diperiksa kembali kelayakannya. Simpul yang bertetangga dengan simpul 4 tidak ada  berwarna  Hijau  sehingga Hijau layak digunakan pada simpul ini.
Pewarnaan  pada  simpul  4  dapat dilihat pada gambar berikut:
Gambar 16. Pewarnaan pada Simpul 4
Pewarnaan Wilayah (Region Coloring),...Sagita Charolina,...Sainmatika,...Volume 13,...No.1,...Juni 2016,...60-77
19. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 11 Selanjutnya dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna merah.  Setelah  warna  diambil maka akan diperiksa kelayakannya,  simpul  7  yang bertetangga  dengan  simpul  11 sudah diberi warna Merah sehingga Merah tidak layak digunakan pada simpul ini. Selanjutnya  diambil  warna  lain dari  himpunan  solusi  yaitu  warna Biru.  Simpul  8  yang  bertetangga dengan simpul 11 sudah menggunakan warna Biru, sehingga  warna  Biru  tidak  layak digunakan untuk simpul 11. Selanjutnya  diambil  lagi  warna Hijau  dari  himpunan  solusi  dan kemudian diperiksa kembali kelayakannya. Simpul yang bertetangga  dengan  simpul  11 tidak ada berwarna Hijau sehingga Hijau layak digunakan pada simpul ini. Pewarnaan  pada  simpul  11  dapat dilihat pada gambar berikut:
Gambar 17. Pewarnaan pada Simpul 11
20. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul
13 Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna merah.  Setelah  warna  diambil maka akan diperiksa kelayakannya,  simpul  7  yang bertetangga  dengan  simpul  13 sudah diberi warna Merah sehingga Merah tidak layak digunakan pada simpul ini. Selanjutnya  diambil  warna  lain dari  himpunan  solusi  yaitu  warna Biru.  Simpul  12  yang  bertetangga dengan simpul 13 sudah menggunakan warna Biru, sehingga  warna  Biru  tidak  layak digunakan untuk simpul 13. Selanjutnya  diambil  lagi  warna Hijau  dari  himpunan  solusi  dan kemudian diperiksa kembali kelayakannya.  Simpul  15  yang bertetangga  dengan  simpul  13 sudah  menggunakan  warna  Hijau, sehingga  warna  Hijau  tidak  layak digunakan untuk simpul 13. Selanjutnya  adalah  mengambil warna  dari  himpunan  kandidat warna  yaitu  warna  Ungu.  Simpul 13 layak diberi warna Ungu karena tidak  ada  warna  Ungu  yang bertetangga dengan simpul 13.
Pewarnaan  pada  simpul  13 dapat dilihat pada gambar berikut:
Gambar 18. Pewarnaan pada
Simpul 13 21. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 2 Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna merah.  Setelah  warna  diambil maka akan diperiksa kelayakannya,  simpul  1  yang bertetangga  dengan  simpul  2 sudah diberi warna Merah sehingga Merah tidak layak digunakan pada simpul ini. Selanjutnya  diambil  warna  lain dari  himpunan  solusi  yaitu  warna Biru.  Simpul  3  yang  bertetangga dengan simpul 2 sudah menggunakan warna Biru, sehingga  warna  Biru  tidak  layak digunakan untuk simpul 2. Selanjutnya  diambil  lagi  warna Hijau  dari  himpunan  solusi  dan kemudian diperiksa kembali kelayakannya. Simpul yang bertetangga dengan simpul 2 tidak ada yang berwarna Hijau sehingga Hijau layak digunakan pada simpul ini.
Pewarnaan  pada  simpul  2  dapat dilihat pada gambar berikut:
Gambar 19. Pewarnaan pada Simpul 2 22. Tahap berikutnya kembali menyeleksi  simpul  terpilih  simpul 6
Selanjutnya akan dilakukan seleksi warna  yang  akan digunakan untuk simpul  ini.  Diambil  warna  dari himpunan  solusi,  dipilih  warna merah.  Setelah  warna  diambil maka akan diperiksa kelayakannya,  simpul  9  yang bertetangga  dengan  simpul  6 sudah diberi warna Merah sehingga Merah tidak layak digunakan pada simpul ini.
Selanjutnya  diambil  warna  lain dari  himpunan  solusi  yaitu  warna Biru.  Simpul  yang  bertetangga dengan  simpul 6  tidak  ada berwarna Biru sehingga Biru layak digunakan pada simpul ini. Pewarnaan  pada  simpul  6  dapat dilihat pada Gambar 20:
Gambar 20. Pewarnaan pada
Simpul 6 23. Fungsi Objektif Karena semua simpul sudah diwarnai,  maka  proses  berhenti. Didapat  himpunan  solusi  S  = {Merah, Biru, Hijau, Ungu}.

## Menentukan Jumlah Warna Minimum Peta Kabupaten Ogan Ilir
Gambar 21. Pewarnaan Wilayah Kecamatan Peta Kabupaten Ogan Ilir
Keterangan:
R1: Kecamatan Indralaya, terdapat 17 desa dan 3 kelurahan R2: Kecamatan Indralaya Utara, terdapat 15 desa dan 1 kelurahan R3: Kecamatan Indralaya Selatan, terdapat 14 desa R4: Kecamatan Pemulutan, terdapat 25 desa
R5: Kecamatan Pemulutan Barat, terdapat 11 desa R6: Kecamatan Pemulutan Selatan, terdapat 15 desa R7: Kecamatan Tanjung Batu, terdapat 19 desa dan 2 kelurahan R8: Kecamatan Payaraman, terdapat 11 desa dan 2 kelurahan R9: Kecamatan Tanjung Raja, terdapat 15 desa dan 4 kelurahan R10: Kecamatan Sungai Pinang, terdapat 12 desa dan 1 kelurahan R11: Kecamatan Rantau Panjang, terdapat 12 desa R12: Kecamatan Muara Kuang, terdapat 13 desa dan 1 kelurahan R13: Kecamatan Rambang Kuang, terdapat 13 desa R14: Kecamatan Lubuk Keliat, terdapat 10 desa R15: Kecamatan Rantau Alai, terdapat 13 desa R16: Kecamatan Kandis, terdapat 12 desa

## KESIMPULAN
Berdasarkan  pembahasan  di  atas  dapat disimpulkan  bahwa  untuk  pewarnaan peta  Kabupaten  Ogan  Ilir  memerlukan 4  jenis  warna  yang  berbeda.  Untuk pewarnaan  yang  digunakan  adalah himpunan  solusi  S  =  {Merah,  Biru, Hijau, Ungu}.

## DAFTAR PUSTAKA
Amrimirza, Muhammad., Aplikasi Algoritma Greedy pada Pewarnaan  Peta , Makalah  IF2251 Strategi Algoritmik Institut Teknologi Bandung, 2007 Li,  Yu.,  Lucet  Corinne.,  Moukrim, Aziz.,  Sghiouer,  Kaoutar.,  Greedy Algorithms  for  the  Minimum
Coloring  Problem,  Logistique  et transport,  Sousse:  Tunisia  (2009), Page-00451266,  Volume  I,  28 Januari 2010
Munir,  Rinaldi., Matematika  Diskrit , Edisi Ketiga, Informatika: Bandung, Indonesia Murali, T.M., Greedy Graph Algorithms , Lecture Notes, 2008 http://www.oganilirkab.go.id/p/kondisi
-wilayah.html diakses  pada  15 Januari 2016 pukul 16:18