Algoritma Pencarian Jalur Hamiltonian Pada Kubus Fibonacci dan Kubus Lucas

Ernastuti, Ernastuti (2006) Algoritma Pencarian Jalur Hamiltonian Pada Kubus Fibonacci dan Kubus Lucas. Proceedings, Komputer dan Sistem Intelejen (KOMMIT 2006). ISSN 1411-6286

[img]
Preview
Text
ALGORITMA PENCARIAN JALUR HAMILTONIAN_UG.pdf - Submitted Version

Download (237Kb) | Preview

Abstract

Jalur Haimiltonian pada graf terhuhung G adalah suatu jalur yang inelalui sernua simpul didalarn G tepat satu kali. Masalah yang muncul adalah “Apakah graf G mempunyai jalur Hamiltonian ? “. Masalah pencarianjalur Hamiltonian pada graf G termasuk dalatn kelas NP-complete (waktu pencariannya non polinomial. Namun, khusus untuk beberapa graf tertentu masalah pencarian jalur Hamiltonian bisa diselesaikan dalarn waktu polinomial, seperti pada graf kubus Fibonacci dun kubus Lucas. Kubus Fibonacci Kubus Lucas adalah subgraf dan graf kipercube ditnana simpul—simpu/iwa merupakan string hiner order—p panjang—n E (0, if’ , dun dua simpul akan terhubung bila stringnva berbeda 1 bit tunggal. Simpul-simpul pada kubus Fibonacci merupakan string biller yang tidak mengandung subtring F sedan gkan pada kuhus Luca.c simpul-simpuinva merupakan string hi ncr yang tidak mengandung subtring F atait tidak mengandung sekaligus suhtring 1’ didepan dan subtring jm dibelakang dengan l + m > p. Pada makalah mi diban gun suatu algoritma pencarian jalur Hamiltonian pada kuhus Fibonacci dan Lucas, kemudian ditunjuukan huh wa a igorit in a dapat diselesaikan dalam waktu O(N*IogN,), dim an a N=2” adalah jumlah simpul kubus dimensi-n . Makalah ini membahas kubus Fibonacci dan kubus Lucas dimensi-n khusus untuk p = 2

Item Type: Article
Uncontrolled Keywords: Hypercube; kubus Fibonnacci; kubus Lucas; string Fibonacci; string Lucas; kode Gray; Jalur Hamiltonian
Subjects: A General Works > AI Indexes (General)
Divisions: Fakultas Ilmu Komputer dan Teknologi Informasi > Program Studi Sistem Informasi
Depositing User: Mr Reza Chandra
Date Deposited: 25 Feb 2014 03:52
Last Modified: 25 Feb 2014 03:52
URI: http://repository.gunadarma.ac.id/id/eprint/38

Actions (login required)

View Item View Item