BILANGAN FIBONACCI BERDASARKAN HIMPUNAN BEBAS GRAF DAYUNG KAYAK

Abstract

Konsep bilangan Fibonacci suatu graf G, yang didefinisikan oleh Prodinger dan Tichy pada tahun 1982 sebagai banyaknya himpunan bebas pada G, menyediakan landasan penting dalam teori graf. Himpunan bebas adalah himpunan simpul di mana tidak ada dua simpul yang saling bertetanggaan. Telah diketahui bahwa bilangan Fibonacci untuk graf lintasan P_n adalah ​ F_n+2 dan untuk graf siklus C_n​ adalah bilangan Lucas L_n. Penelitian ini bertujuan untuk menyelidiki dan menentukan sifat-sifat kelas himpunan bebas dari graf dayung kayak, KP_(k,m,l), sebuah graf yang terbentuk dari dua siklus dengan panjang k dan m yang dihubungkan oleh sebuah lintasan dengan panjang l dalam kaitannya dengan bilangan Fibonacci. Metode yang digunakan adalah analisis kombinatorial terhadap struktur graf dayung kayak untuk menghitung banyaknya himpunan bebasnya. Hasil penelitian menetapkan relasi rekursif untuk banyaknya himpunan bebas, yang dinotasikan i(KP_(k,m,l)). Secara spesifik, i(KP_(k,m,l)) ditunjukkan sebagai jumlah dari i(KP_(k,m,l-1)) dan i(KP_(k,m,l-2)); sifat rekursif serupa juga berlaku untuk panjang siklus k dan m. Selain itu ketika k=3 atau m=3, banyaknya himpunan independen berkaitan dengan bilangan Lucas dan Fibonacci, menunjukkan bahwa graf dayung kayak mengikuti pola pertumbuhan rekursif.