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 Bn dan graf matahari Sn 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 Bn dan graf matahari Sn dengan menggunakan matriks laplacian.