BAB 1 PENDAHULUAN
1.1 Pendahuluan Seiring dengan berkembangnya ilmu pengetahuan, penyelesaian suatu masalah dapat ditangani oleh suatu algoritma. Jenis masalah dapat berkisar dari masalah yang mudah sampai masalah yang kompleks, seperti masalah pewarnaan graf, pencarian rute terpendek, penjadwalan dan lain sebagainya. Kesulitan suatu masalah berasal dari tidak mungkinnya menghasilkan algoritma yang memberikan hasil yang eksak dalam waktu komputasi yang cepat. Masalah-masalah demikian memerlukan banyak perhitungan serta dengan semakin besarnya ukuran masalah, misalnya pada pewarnaan graf yang merupakan cabang teori graf. Teori graf merupakan suatu pokok bahasan yang sudah tua usianya namun mempunyai banyak terapan bagi seluruh masyarakat sampai saat ini. Salah satu teori graf yang memiliki kontribusi besar bagi perkembangan ilmu pengetahuan adalah pewarnaan graf. Pada masa awal penemuan teori graf, pewarnaan graf telah menjadi masalah yang banyak menarik perhatian matematikawan dunia, pasalnya dalam sejarah perkembangan teori graf, teori mengenai pewarnaan graf selalu berubah sepanjang waktu. Pewarnaan graf merupakan suatu cabang teori graf yang mempelajari cara mewarnai suatu graf. Jadi, pewarnaan graf adalah pemberian warna terhadap verteksverteks graf dimana dua buah verteks yang berdampingan tidak boleh mempunyai warna yang sama.
Universitas Sumatera Utara
Masalah pewarnaan graf merupakan konsep dari graf tak berarah. Diberikan suatu graf tak berarah G(V, E), untuk mewarnakan n verteks dengan mencoba semua kemungkinan yang ada, sehingga setiap verteks yang berdekatan pada graf G menerima warna yang berbeda, disebut sebagai masalah pewarnaan graf. Pewarnaan graf secara tepat dengan jumlah yang minimum pada umumnya merupakan pekerjaan yang rumit, misalnya untuk mewarnakan graf dengan banyak verteks pada umumnya merupakan pekerjaan yang sulit dan perlu dicari solusinya. Salah satu cara untuk menyelesaikan masalah pewarnaan graf adalah dengan menggunakan metode
heuristik. Istilah heuristik berasal dari bahasa Yunani,
heuriskin, yang artinya mencari atau menemukan. Metode heuristik sesuai untuk menangani masalah yang sulit untuk dipecahkan. Metode heuristik tidak memiliki algoritma pencarian solusi optimum yang pasti tetapi memiliki kaidah yang dapat mengekplorasi ruang pencarian solusi optimum atau mendekati. Malguti (2010) menyatakan bahwa dari sekian banyaknya algoritma yang ada untuk menyelesaikan permasalahan pewarnaan graf, algoritma tabu search merupakan salah satu pilihan yang tepat. Algoritma tabu search adalah salah satu metode heuristik untuk penyelesaian permasalahan optimisasi (Glover, 1995). Jadi, permasalahan pewarnaan graf dapat diselesaikan dengan menggunakan algoritma tabu search. Berdasarkan penjelasan tersebut, dalam skripsi ini akan membahas tentang: “Studi Pewarnaan Graf Menggunakan Algoritma Tabu Search”.
1.2 Perumusan Masalah Berdasarkan pendahuluan, didapat rumusan masalah yaitu bagaimana menyelesaikan masalah pewarnaan graf menggunakan algoritma tabu search.
Universitas Sumatera Utara
1.3 Pembatasan Masalah Pada penelitian ini terdapat beberapa batasan masalah sebagai berikut: 1. Graf yang digunakan adalah graf tak berarah. 2. Pewarnaan graf yang akan diimplementasikan yaitu hanya pada bagian pewarnaan verteks saja. 3. Hasil yang ingin dicapai adalah graf dengan setiap verteks yang terhubung oleh suatu edge menerima warna berbeda.
1.4 Tinjauan Pustaka Secara matematis graf g adalah pasangan himpunan (V, E), ditulis dengan notasi G(V, E), yang dalam hal ini V adalah himpunan tidak kosong dari verteks dan E adalah himpunan edge yang menghubungkan sepasang verteks. Terdapat beberapa jenis masalah pewarnaan graf yaitu pewarnaan verteks, pewarnaan edge, dan pewarnaan region. Pewarnaan verteks adalah memberi warna pada verteks didalam graf sedemikian sehingga dua verteks bertetangga mempunyai warna yang berbeda(Munir, 2007). Masalah pewarnaan graf merupakan konsep dari graf tak berarah. Diberikan suatu graf tak berarah G(V, E), bagaimana mewarnakan n verteks dengan k warna tertentu sedemikian sehingga dua verteks yang berdekatan menerima warna yang berbeda disebut masalah pewarnaan graf. Pada masalah pewarnaan graf yang menarik adalah menentukan minimum jumlah warna yang digunakan untuk mewarnakan graf. Graf G yang memerlukan k warna yang berbeda untuk melakukan pewarnaan yang tepat, disebut k kromatik graf dan bilangan k disebut dengan bilangan kromatik dari graf G(Deo, 1986).
Universitas Sumatera Utara
Algoritma tabu search pertama kali diperkenalkan oleh Glover sekitar tahun 1986. Glover menyatakan bahwa algoritma tabu search adalah salah satu prosedur heuristik untuk penyelesaian permasalahan optimisasi kombinatorial. Algoritma tabu search ini dirancang untuk mengarahkan metode-metode lain untuk keluar atau menghindari solusi optimal yang bersifat lokal. Kemampuan algoritma tabu search dalam menghasilkan solusi yang mendekati optimal telah dimanfaatkan dalam beragam permasalahan di berbagai bidang mulai bidang penjadwalan hingga bidang telekomunikasi(Glover, 1995).
1.5 Tujuan Penelitian Tujuan dari penelitian ini adalah sebagai berikut: 1. Untuk menyelesaikan masalah pewarnaan graf menggunakan algoritma tabu search. 2. Untuk mencari solusi optimum dari masalah
pewarnaan graf menggunakan
algoritma tabu search.
1.6 Kontribusi Penelitian Kontribusi setelah melakukan penelitian ini, penulis berharap penelitian ini dapat digunakan sebagai informasi dan wawasan pengetahuan tentang teori graf dan algoritma, khususnya tentang pewarnaan graf dan algoritma tabu search. Penulisan ini juga dapat digunakan untuk bahan pembanding yang ingin mengetahui lebih banyak tentang masalah pewarnaan graf dan algoritma tabu search serta dapat diaplikasikan dalam kehidupan nyata seperti masalah penjadwalan kuliah, penjadwalan pekerjaan, penjadawalan job shop, pewarnaan pada peta, pengaturan lampu lalu lintas, penggunaan frekwensi radio, penyimpanan barang, pengaturan jalan raya, dan lain sebagainya.
Universitas Sumatera Utara
1.7 Metode Penelitian Metode penelitian ini digunakan sebagai pedoman dalam melaksanakan penelitian agar hasil yang dicapai tidak menyimpang dari tujuan yang telah ditentukan sebelumnya. Penulis mengumpulkan data dengan studi literature yaitu menggunakan sumber-sumber otentik dari buku, jurnal, artikel, dan browsing internet untuk mendapatkan data dan informasi yang berkaitan dengan judul yang diambil. Metode penelitian ini bersifat literatur yaitu memperkenalkan teori graf, definisi graf, jenisjenis graph, terminologi dasar graf, graf sederhana khusus, representasi matriks graf, pewarnaan graf, algoritma tabu search, membahas masalah pewarnaan graf, membahas
algoritma
tabu
search
untuk
masalah
pewarnaan
graf
dan
mengimplementasikan algoritma tabu search ke dalam sebuah program komputer dengan menggunakan bahasa pemrograman Java.
Universitas Sumatera Utara
