PENERAPAN MATRIKS LAPLACIAN UNTUK MENENTUKAN BANYAKNYA POHON RENTANG PADA GRAF KINCIR, GRAF BUKU DAN GRAF MATAHARI

Abstract

Graf berlabel pada titik adalah graf yang setiap titiknya diberi label. Untuk menentukan banyaknya unsur graf berlabel dapat dilakukan dengan membedakan mana graf yang tidak identik. Sehingga jumlah graf berlabel lebih banyak daripada jumlah graf yang tidak berlabel. Sebuah pohon yang terbentuk dari graf sederhana yang terhubung, dimana memuat semua titik pada graf tersebut dinamakan pohon rentang. Pohon rentang dari sebuah graf tidaklah tunggal. Dengan kata lain sebuah graf dapat mempunyai satu atau lebih pohon rentang. Untuk menentukan pohon rentang digunakan graf berlabel. Sedangkan untuk menentukan banyaknya pohon rentang pada graf kincir 𝐾 𝑛 (𝑚 ) , graf buku B n dan graf matahari S menggunakan matriks laplacian. Dimana matriks laplacian didapat dari pengurangan matriks derajat dengan matriks adjacent. Tujuan penelitian adalah mengetahui cara mencari rumus umum untuk menentukan banyaknya pohon rentang pada graf kincir 𝐾 , graf buku B n dan graf matahari S n n dengan menggunakan matriks laplacian. Penelitian dilakukan dalam beberapa langkah. Langkah pertama adalah menentukan matriks laplacian dari graf kincir 𝐾 𝑛 (𝑚 ) , graf buku B dan graf matahari S n n dengan. Langkah kedua adalah menghapus baris pertama dan kolom pertama pada matriks laplacian. Langkah ketiga adalah menghitung determinan dari matriks yang telah dihapus baris pertama dan kolom pertama. 𝑛 (𝑚 )

Berdasarkan kajian yang telah dilakukan, didapatkan hasil bahwa dengan menghapus salah satu sisi pembuat sikel pada graf matahari maka akan didapatkan pohon rentang dari graf tersebut. Sedangkan dari perhitungan matriks laplacian didapatkan rumus umum untuk banyaknya pohon rentang pada graf kincir 𝐾 𝑛 (𝑚 ) adalah 𝑛 𝑛𝑚 −2𝑚 . Untuk banyaknya pohon rentang pada graf buku B didapat rumus umumnya adalah (3 𝑛 −1 )(n+3). Sedangkan rumus umum untuk banyaknya pohon rentang pada graf matahari S n adalah n.