## IMPLEMENTASI GRAPH COLORING DALAM PEMETAAN KECAMATAN DI KABUPATEN KEDIRI

## Risky Aswi Ramadhani
Fakultas Teknik, Program Studi Teknik Informatika Universitas PGRI Kediri Email: risky_aswi@unpKediri.ac.id

## ABSTRAK
Kabupaten  Kediri  adalah  kabupaten  yang  cukup  berkembang,  bahkan  saat  ini  perkembangan  kabupaten Kediri  tergolong  pesat.  Kabupaten  Kediri  memiliki  26  kecamatan,  kecamatan  tersebut  saling  terhubung. Hubunngan  antar  kecamatan  ini  yang  akan  mempengaruhi  perkembanganya.  Pada  saat  ini  kabupaten  Kediri melakukan  pembangunan  yang  pesat.  Pembangunan  kabupaten  Kediri  dilaksanakan  pada  kecamatan  yang memiliki  letak  yang  strategis,  mudah  diakses  oleh  kecamatan  disekitarnya.    Kecamatan  yang  memliki degree banyak maka kecamatan tersebut bisa dijadikan proritas pengembngan kabupaten Kediri. Karena kecamatan yang memiliki degree banyak pasti sangat mudah diakses oleh kecamatan disekitarnya. Dengan memanfaatkan metode graph coloring jumlah vertek dan edgee yang ada pemerintah kabupaten Kediri dapat mengetahui posisi setiap kecamatan  dengan  mudah  dan  mengetahui  ke  strategisan  setiap  kecamatan.  Setelah  dilakukan  pencarian degree terbanyak maka pemerintah kabupaten Kediri dapat melakukan pembangunan pada kecamatan tersebut. Dengan melakukan  pembangunan  pada  kecamatan  yang  memiliki degree terbanyak  (strategis),  pembangunan  pusat ekonomi,  kesehatan  dan  pendidikan  akan  dilakukan  pada  kecamatan  tersebut  akan  berimbas  pada  kecamatan disekitarnya,  selain  itu  kecamatan  yang  memiliki degree banyak  sangat  mudah  diakses  oleh  kecamatan disekitarnya.
Kata kunci: edgee , graph coloring , pemetaan, vertex.

## ABSTRACT
Kediri is a district that is developing, even now relatively rapid development of the district keduri. Kediri has 26 districts, the districts are connected. Hubunngan between these districts  which will affect the  current  district  perkemabanganya.Pada Kediri perform  rapid  development. Kediri district development  carried  out  at  district  that  has  a  strategic  location,  easily  accessible  by  kecapamatan surroundings. Districts that discount the degree  many districts can be used as a priority pengembngan Kediri district. Because the district which has many degree  must be very accessible to the surrounding districts. By utilizing the method  graph coloring number edgee existing vertex and district governments Kediri can know the position of each sub-district with ease and knowing strategisan setian district. After searching the highest degree. Kediri district government can do development in these districts. By doing construction  in  the  district  that  has  the  highest  degree  (ideally),  building  the  economy,  health  and education will be conducted in these districts will impact on the surrounding districts, in addition to the degree  many districts that have very easily accessible by the surrounding districts
Keywords: edgee, graph coloring, mapping, vertex.

## 1. PENDAHULUAN
Kediri  merupakan kabupaten yang cukup berkembang, untuk mendukung perkembangan kabupaten Kediri diperlukan persiapan yang matang. Persiapan tersebut bisa dimulai dari SDM, Peralatan, maupun analisa  wilayah.  Pada  penelitian  ini  akan  dibahas graph  coloring,  graph  coloring digunakan  sebagai bahan untuk mengembangkankan kabupaten Kediri .
Proses  transformasi  kota  menjadi  metropolitan  ini  umumnya  diawali  oleh  bergabungnya  kota-kota yang  berdekatan[1].  Dengan  membangun  pusat  kecamatan  dari  beberapa  kumpulan  kecamatan diharapakan  kemajuan  setiap  kecamatan  hampir  sama.  Dengan  memilih  salah  satu  kota  yang  paling strategis  untuk  pembengmbangan  kecamatan,  maka  kecamatan  disekitarnya  akan  melakukan  trasnsaksi jual beli di kecamatan yang memiliki degree yang paling banyak. Teori graph merupakan  topik  yang  banyak  mendapat  perhatian  saat  ini,  karena  model-model  yang ada pada teori graph berguna untuk aplikasi  yang  luas[2]. graph coloring sendiri terdiri dari vertex dan edgee . Edgee bisa terbentuk apabila ada beberpa vertex saling terhubung. Pada penelitian ini  yang akan
dijadikan vertex adalah  kecamatan  dikabupaten  Kediri.  Setiap  kecamatan  di  kabupaten  Kediri  saling berbatasan dengan kecamatan lain. Perbatasan ini yang akan dijadikan dasar pembentukan edgee.
Apabila  dilihat  dari  jumlah  kecamatan  yang  ada  di  kabupaten  Kediri  jumlah vertex yang  akan digunakan  adalah  26 vertex,  vertex digambarkan  sebagai  kecamatan,  jika  antara  kecamatan  saling berbatasan maka ada 2 vertex yang bertemu, hal seperti ini disebut edgee. Kota  yang  memiliki edgge paling  besar  adalah  kecamatan  yang  strategis,  yang  dimaksud  strategis adalah,  kecamatan  ini  terhubung  dengan  bnyak  kecamatan  di  sekitarnya.  Kecamatan  yang  memiliki degrre yang paing banyak menjadi central kabupaten. Pengembangan  kabupaten seharusnya terpusat pad kecamatan tersebut.
Kecamatan yang maju saling bergantung ke kecamatan yang lain, kecamatan yang memiliki degree sedikit untuk pengembanganya pasti sulit. harapan membangun kecamatan yang memiliki degree banyak pemerintah  dapat  memusatkan  pembangunan  pusat  ekonomi,  pendidikan  kesehatan  pada  kecamatan tersebut  dan  kecamatan  disekitarnya  mudah  mengakses,  selain  itu  kemajuan  kecamatan  yang  memiliki degree banyak akan berimbas pada kecamatan disekitarnya.

## 2. METODOLOGI PENELITIAN
Metode Penelitian adalah urutan meneliti, berikut ini adalah flowchart metode penelitian yang akan digunakan.  Penelitian  ini  dilakukan  untuk  mencari degree antar  kecamatan  di  kabupaten  Kediri.  Untuk lebih jelasnya silahkan lihat gambar 3.
Mulai Indentifikasi masalah Studi Pustaka Pengumpulan data Data Pertbatasan Kecamatan di Kabupaten Kediri Pembuatan Graf Kesimpulan Selesai Cleaning Data
Gambar 3. Bagan Alur Penelitian
Gambar  3.  Menjelaskan  bagaiaman  langkah-langkah  penelitian  yang  dilakukan  pada  penelitian  ini terdapat 8 langkah yaitu:
1) Indentifikasi  masalah:  permasalahan  yang  didapatkan  pada  penelitian  ini  adalah  bagaimana menentukan kecamatan yang paling strategis di kabupaten Kediri  .
2) Studi Pustaka: Pencarian sumber refrensi baik itu dari jurnal, mupun buku yang berkaitan dengan graph coloring.
3) Pengumpulan data: data perbatasan setiap akecamatan akan dicatat.
4) Data kecamatan dikabupaten Kediri adalah proses input ke nodexl.
5) Cleaning data: saat pengumpulan data biasanya terjadi input data ganda, agar hasil akurat maka perlu dilakukan cek ulang dan dilakukan cleaning.
6) Pembuatan graph dari kecamatan di kabupaten Kediri yang saling berkaitan.
7) Penarikan  kesimpulan  sehingga  hasil  dari  penelitian  ini  dapat  digunakan  sebgai  dasar pengembangan kecamatan di kabupaten Kediri.

## 3. HASIL DAN PEMBAHASAN
Kebutuhan  masyarakat  akan  penentuan  atau  pencarian  letak  suatu  bangunan  atau  tempat  dengan korelasi yang ada antara suatu tempat dengan tempat yang lain dan dengan kemajuan teknologi terutama pada  visualisasi.  Sehingga  masyarakat  sekarang  cenderung  mengerti  atau  mengatahui  suatu  lokasi berdasarkan  apa  yang  pernah  mereka  perkirakan  atau  apa  yang  dilihat  sebelumnya.  Oleh  karena  itu, diperlukan  suatu  penyajian  peta  yang  menarik  dan  mudah  dipahami  dengan  mengandung  kaidah kartografi  pada  setiap  objek  bangunan  yang  cenderung  lebih  disukai  dibanding  dengan  pembedaan kategori nominal, terutama bagi masyarakat awam dalam membaca informasi-informasi pada peta[3].
Pada  Penelitian  ini  akan  dibahas  bagaimana  membuat  graph  coloring  dari  sebuah  peta,  peta  yang digunakan adalah peta kabupaten Kediri. Graph coloring digunakan untuk melihat perbatasan antara peta yang saling terhubung. Berikut ini adalah peta kabupaten Kediri.

## Gambar 4. Peta Kabupaten Kediri
Sumber: Pemerintah kabupaten Kediri
Gambar 3 adalah peta kabupaten Kediri, pada peta kabupaten Kediri gambar ini digunakan sebagai rujukan  untuk  melakukan  pengambilan  data  perbatasan  anatar  kecamatan  di  kabupaten  Kediri.  Setiap kecamatan yang saling terhubungang akan ditandai sebagai edge.
Secara informal, suatu graph adalah himpunan benda-benda yang disebut simpul ( vertex atau node ) yang  terhubung  oleh  sisi  ( edge )  atau  busur  ( arc ).  Biasanya graph digambarkan  sebagai  kumpulan  titik- titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan  busur).  Suatu  sisi  dapat  menghubungkan  suatu  simpul  dengan  simpul  yang  sama.  Sisi
yang  demikian  dinamakan  gelang  ( loop ).  Secara  matematis,  graph  G  didefinisikan  sebagai  pasangan himpunan (V, E), yang dalam hal ini, V adalah himpunan tidak kosong dari simpul-simpul (vertices atau node). Dan E adalah himpunan sisi (edges atau arcs ) yang menghubungkan sepasang simpul[4]. Edges  menggambarkan  bagaiamana  setiap  kecamatan  di  kabupaten  Kediri  saling  terhubung, misalnya  saja  kecamatan  Ngadiluwih  berbatasan  langsung  dengan  kecamatan  Kras.  Pada  bagian  ini digunakan  untuk  menghubungkan  anatara  kecamatan  Ngadiluwih  dan  Kras,  untuk  lebih  jelas  silahkan lihat pada gambar 5 dibawah ini.
Gambar 5. Edges Kecamatan Ngadiluwih Dan Kecamatan Kras

## 3.1 Degree
Setiap  Kecamatan  di  Kabupaten  Kediri memiliki  central,  kecamatan  yang  memiliki degree terbanyak diaganggap sebgai kecamatan yang paling strategis, degree merupakan jumlah link yang menghubungkan suatu node dengan node lain[5]. Sentral adalah diamana kecamatan tersebut dapat terhubung dengan banyak kecamatan pada bagian ini kecamatan yang  diangkat adalah kecamatan wates, kecamatan wates menjadi sentral karena terhubung dengan  kecamatan  Ngadiluwih,  Kras,  Plosokaten,  Gurah,  dan  Ngancar.  Untuk  lebih  jelasnya  bisa  dilihat  pada gambar 6.

## Gambar 6. Degree Kecamatan Wates
Setiap Kecamatan  memiliki degree yang berbeda, berikut ini adalah daftar 5 kecamatan dengan degree paling tinggi.
Tabel 1. Daftar Degree Kabupaten Kediri No Nama Kota Degree 1 Pare 7 2 Pagu 6 3 Gurah 5 4 Gampeng Rejo 5 5 Wates 5
Tabel 1 menjelaskan bahwa  kecamatan pare memiliki letak paling strategis degree yang didapatkan adalah 7,  Kecamatan pagu memiiliki 6 degree.

## 3.2 Graph Coloring
Graph  Coloring adalah  pemberian  warna  terhadap vertex-vertex graph  di  mana  2  buah  vertexyang berdampingan  tidak  boleh  mempunyai  warna  yang  sama.  Selain  itu Graph  coloring meruakan  solusi untuk pemecahan masalah-masalah yang berhubungan dengan link antar node[6].
Bilangan kromatis dari G = K(G) adalah jumlah minimum warna yang dibutuhkan. Algoritma yang dapat  digunakan  untuk  mendapatkan  bilangan  kromatis  dari  sebuah graph adalah  algoritma Welch- Powell .
Adapun langkah-langkahnya adalah:
1) Urutkan vertex-vertex berdasarkan derajatnya.Dari besar ke kecil.
2) Warnai.
Pada  Penelitian  ini  Graph  Coloring  akan  digunakan  untuk  mengetahui  letak  kecamatan  kecamatan saling  terhubung.  Kecamatan  yang  memiliki  jaringan  yang  banyak  yang  meiliki  degree    yang  banyak adalah  kecamatan  yang  memilikiletak  paling  strategis,  kecamatan  yang  memiliki  letak  paling  strategis akan dibangun dan dijadikan pusat ekonomi untuk beberapa kecamatan disekitarnya. Pada gambar 7 akan dijelaskan hibungan atar kecamatan, hubungan antar kecamatan ini dilihat dari perbatasan wilayah.

## Gambar 7. Graph Coloring Kabupaten Kediri
Graph Coloring yang ditampilkan gambar 7 terbagi menjadi tujuh warna yaitu
1) Hijau: Tarokan, Grogol, Banyakan, Semen Biru.
2) Biru Muda: Purwosari, Kunjang, Papar, Palemahan, Kayen Kidul, Pagu.
3) Hijau Tua: Badas, Kandangan, Kepung.
4) Merah: Ngadiluwih, Kras.
5) Merah Hati: Plosokaten, Puncu.
6) Hitam: Wates,Kandat, Ringirejo, Ngase.
7) Hijau Tua: Pare.

## 4. KESIMPULAN
Dari  hasil  penelitian  berupa  pewarnaan  grap  ( graph  coloring )  pada  peta  Kabupaten  Kediri  dapat diperoleh beberapa keseimpulan sebagai berikut:
1) Jumlah vertex (Kecamatan) yang terdapat di peta Kabupaten Kediri berjumlah 26.
2) Kecamatan Pare memiliki edgee yang paling banyak yaitu 7 edgee .
Dengan  memanfaatkan graph  coloring maka  pengembangan  Kecamatan  akan  lebih  mudah  karena pihak-pihak  yang  terkait  mengetahui  kecamatan  yang  paling  strategis.  Kecamatan  yang  paling  strategis adalah kecamatan yang memiliki edge paling banyak.

## DAFTAR PUSTAKA
[1] Winarso,  Haryo  ‘et  al.’.  2006  “ Metropolitan  di  Indonesia:Kenyataan  dan  Tantangan  dalam PenataanRuang” .” Direktorat Jenderal Penataan Ruang, Departemen Pekerjaan Umum”.
[2] Hutabarat, Fisi. 2009. “Implementasi Graph Coloring Dalam Pemetaan Daerah Kabupaten Serdang Bedagai”.  Medan.
[3] Kartanegara,  Uman,  2013.”Peninjauan  Secara  Kartografis  Dalam  Pembuatan  Peta  Kampus Universitas Diponegoro”.
[4] Lyanda,  Vivi,  2012  “Pemanfaatan  Algoritma  Sequential  Search  dalam  Pewarnaan  Graph  untuk Alokasi Memori Komputer”, Bandung
[5] Aini,  Viva.  2014.”  Analisis  Pada  Peringkat  Top  Brand  Menggunakan  Jejaring  Sosial Percakapan Dengan Social Network Analysis ( Studi Kasus Pada Smartphone Samsung, Blackberry,
Nokia, Iphone Di Indonesia)” . Universitas Telkom
[6] Barenboim,  Leonid.  2013.”Distributed  Graph  Coloring:  Fundamentals  and  Recent Developments”. Ben-Gurion University of the Negev.