Penerapan Algoritma Tabu Search pada Pelabelan Graceful Ganjil Suatu Graf

Abstract

Pelabelan graf adalah suatu pemetaan himpunan sisi atau himpunan titik ke himpunan bilangan bulat non-negatif yang disebut label dengan syarat tertentu.. Pelabelan yang dikaji pada skripsi ini adalah pelabelan graceful ganjil. Pelabelan graceful ganjil didefinisikan oleh Gnanajothi sebagai variasi dari pelabelan graceful yaitu pelabelan titik dari graf 𝐺 sedemikian hingga label sisi adalah selisih 2 label titik yang bertetangga dan bernilai ganjil. Seiring berkembangnya ilmu pengetahuan dan teknologi, pelabelan suatu graf dapat dicari dengan menerapkan salah satu algoritma dari metode matheuristik yaitu tabu search. Algoritma tabu search merupakan suatu metode optimasi yang melakukan pencarian lokal berdasarkan tetangga dari solusi awal. Metode tabu search mencegah proses pencarian ulang (cycling) pada ruang solusi yang pernah ditelusuri dengan memanfaatkan struktur memori yang disebut dengan tabu list.