BAB 1
PENDAHULUAN
1.1 Latar Belakang
Teori graph merupakan topik yang banyak mendapat perhatian saat ini, karena modelmodel yang ada pada teori graph berguna untuk aplikasi yang luas. Walaupun teori graph berasal dari bidang ilmu Matematika, namun pada penerapannya, teori graph dapat dihubungkan dengan berbagai bidang ilmu dan juga kehidupan sehari-hari. Sedemikian banyaknya pengaplikasian graph dalam dunia ini, bila perlu dikatakan tidak ada habis-habisnya jika dibahas setiap aplikasi graph, karena setiap bidang ilmu dapat dikaitkan dengan graph seperti masalah dalam jaringan komunikasi, transportasi, ilmu komputer, riset operasi, ilmu kimia, Sosiologi, Kartografi dan lain sebagainya. Teori-teori mengenai graph ini telah banyak dikembangkan dengan berbagai algoritma yang memiliki kelebihan dan kelemahan masing-masing dalam menyelesaikannya.
Graph adalah himpunan pasangan tak berurut antara vertex (titik atau node) dan edge (garis atau arcs). Begitu banyak struktur yang dapat direpresentasikan dengan graph, dan banyak masalah yang bisa diselesaikan dengan bantuan graph. Jaringan persahabatan pada situs pertemanan online atau facebook bisa direpresentasikan dengan graph, vertex-nya adalah para pemakai facebook dan ada edge antara A dan B jika dan hanya jika A berteman dengan B. Perkembangan algoritma untuk menangani graph akan berdampak besar bagi ilmu komputer.
Teori pewarnaan graph merupakan salah satu objek yang menarik dan terkenal dalam bidang teori graph. Pewarnaan graph dibagi dalam 3 bagian, yaitu pewarnaan vertex, pewarnaan edge, dan pewarnaan region. Suatu pewarnaan region dari sebuah graph dapat dilakukan (seperti pemberian warna pada wilayah-wilayah di peta) dengan cara membuat dual dari peta tersebut.
Salah satu aplikasi dalam teori pewarnaan graph adalah menentukan warna-warna yang sesuai pada sebuah peta. Teori pewarnaan wilayah (region coloring) ini diaplikasikan pada peta Kabupaten X. Algoritma yang digunakan dalam menentukan warna pada peta Kabupaten X ini, yaitu algoritma Seguential Coloring meskipun algoritma ini masih bergantung pada urutan penomoran dari vertex pada graph, namun keuntungan dari algoritma Sequential Coloring adalah efiensinya.
Algoritma Sequential Coloring adalah sebuah algoritma untuk mewarnai sebuah graph dengan k-warna, k adalah bilangan integer positif. Metoda yang digunakan algoritma ini adalah dengan pewarnaan langsung pada sebuah graph dengan warna yang sesedikit mungkin. Namun Algoritma Sequential Coloring ini masih bergantung pada urutan penomoran dari vertex-vertex pada graph.
1.2 Rumusan masalah
Apabila pemetaan Kabupaten X dapat dilakukan maka potensi masingmasing kecamatan dan kelurahan di Kabupaten X dapat diketahui dengan cepat. Permasalahannya adalah bagaimana cara mengimplementasikan graph coloring dalam memetakan Kabupaten X agar dengan melihat peta dapat dengan mudah mengetahui potensi daerah X.
1.3 Batasan Masalah
Batasan masalah yang menjadi acuan dalam pengerjaan skripsi ini adalah :
1. Graph Coloring yang akan diimplementasikan yaitu hanya pada bagian region coloring saja.
2. Data yang diinformasikan adalah data yang dapat diperoleh dari kantor Bupati Kabupaten X sampai pada tanggal penelitian X.
3. Perancangan sistem yang dilakukan tidak sampai kepada perancangan sistem online.
1.4 Tujuan Penelitian
Tujuan penelitian ini adalah :
1. Mengimplementasikan graph coloring dalam pemetaan daerah Kabupaten X.
2. Merancang sistem informasi potensi daerah Kabupaten X.
1.5 Manfaat Penelitian
Apabila penelitian ini berhasil, maka diharapkan Bupati Kabupaten X dapat mengetahui peta potensi daerah dengan cepat dan dapat mengakses informasi potensi daerah masing-masing dari sistem yang telah disediakan. Kemudian langkah selanjutnya yaitu dapat dilakukan perencanaan program sistem online di daerah-daerah kecamatan Kabupaten X.
1.6 Metodologi Penelitian
Penelitian ini dilakukan dengan beberapa tahapan, yaitu :
1. Studi literatur tentang graph coloring.
2. Merepresentasikan batas wilayah kecamatan sebagai edge dan perpotongan antara batas wilayah sebagai vertex.
3. Merepresentasikan wilayah Kabupaten X sebagai suatu graph.
4. Mengimplementasikan coloring graph dalam pewarnaan masing-masing daerah kecamatan pada Kabupaten X.
5. Pengumpulan data potensi daerah masing-masing kecamatan Kabupaten X.
6. Perancangan sistem informasi potensi masing-masing kecamatan pada Kabupaten X.
7. Pengujian.
1.7 Sistematika Penulisan
BAB 1 PENDAHULUAN
Bab ini akan menjelaskan mengenai latar belakang pemilihan judul, rumusan masalah, batasan masalah, tujuan penelitian, manfaat penelitian, metode penelitian, dan sistematika penulisan.
BAB 2 LANDASAN TEORI
Bab ini akan membahas teori-teori yang berkaitan dengan graph, graph coloring dan region coloring. Pada bagian teori graph dibahas mengenai definisi graph, sejarah teori graph, jenis-jenis pewarnaan graph termasuk pewarnaan wilayah.
BAB 3 PEMBAHASAN
Bab ini akan membahas bagian yang berkaitan dengan region coloring yang pembahasannya dilakukan dengan menggunakan algoritma dan flowchart.
BAB 4 IMPLEMENTASI SISTEM
Bab ini menjelaskan langkah-langkah bagaimana mengimplementasikan region coloring dalam sebuah program komputer dan dilanjutkan dengan pengujian program tersebut
BAB 5 KESIMPULAN DAN SARAN
Bab terakhir akan memuat kesimpulan isi dari keseluruhan uraian bab-bab sebelumnya dan saran-saran dari hasil yang diperoleh yang diharapkan dapat bermanfaat dalam pengembangan selanjutnya.