APLIKASI TEOREMA MATRIKS POHON UNTUK MENCARI JUMLAH POHON RENTANG PADA GRAF RODA (WN)

Salah satu permasalahan dalam topik graf adalah menentukan jumlah pohon rentang dari suatu graf. Pohon rentang adalah subgraf dari graf G yang mengandung semua simpul dari G dan merupakan suatu pohon. Untuk menentukan pohon rentang dari suatu graf terhubung, biasanya dilakukan dengan cara memotong/memutus sisi-sisi sehingga graf tersebut tidak lagi mengandung suatu sikel. Tujuan penelitian ini adalah untuk menentukan bentuk umum jumlah pohon rentang pada graf roda (Wn) dengan menggunakan teorema matriks-pohon. Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research) dengan langkah-langkah penelitian sebagai berikut: (1) Menggambar graf roda (Wn) dengan n ≥ 3 dan nN; (2) Menentukan matriks berelasi (adjacency matrices) dan matriks derajat (degree matrices) dari graf roda (Wn); (3) Mencari nilai selisih dari matriks derajat dan matriks berelasi (matriks Laplacian) dari graf roda (Wn); (4) Mencari nilai kofaktor dari matriks Laplacian dari graf roda (Wn); (5) Melihat pola jumlah pohon rentang dari graf roda (Wn); (6) merumuskan pola ke dalam teorema; (7) membuktikan teorema. Berdasarkan hasil pembahasan dapat diperoleh bahwa bentuk umum jumlah pohon rentang graf roda (Wn) dengan n ≥ 3 dan n  N adalah τ(W_n )= ((3+√5)/2)^n+((3-√5)/2)^n-2