ALGORITMA PENCARIAN JALUR HAMILTONIAN PADA KUBUS FIBONACCI DAN KUBUS LUCAS

Abstract

Jalur Hamiltonian pada graf terhubung G adalah suatu jalur yang melalui semua simpul didalam G tepat satu kali. Masalah yang muncul adalah “Apakah graf G mempunyai jalur Hamiltonian ?”. Masalah pencarian jalur Hamiltonian pada graf G termasuk dalam kelas NP-complete (waktu pencariannya non polinomial). Namun, khusus untuk beberapa graf tertentu masalah pencarian jalur Hamiltonian bisa diselesaikan dalam waktu polinomial, seperti pada graf kubus Fibonacci dan kubus Lucas. Kubus Fibonacci dan Kubus Lucas adalah subgraf dari graf hypercube dimana simpul-simpulnya merupakan string biner order-p panjang-n ∈ {0,1}n , dan dua simpul akan terhubung bila stringnya berbeda 1 bit tunggal. Simpul-simpul pada kubus Fibonacci merupakan string biner yang tidak mengandung subtring 1p , sedangkan pada kubus Lucas simpul-simpulnya merupakan string biner yang tidak mengandung subtring 1p atau tidak mengandung sekaligus subtring 1ℓ didepan dan subtring 1m dibelakang dengan ℓ + m ≥ p. Pada makalah ini dibangun suatu algoritma pencarian jalur Hamiltonian pada kubus Fibonacci dan Lucas , kemudian ditunjuukan bahwa algoritma dapat diselesaikan dalam waktu O(N*logN), dimana N=2n adalah jumlah simpul kubus dimensi-n . Makalah ini membahas kubus Fibonacci dan kubus Lucas dimensi-n khusus untuk p=2.