Abstract

Penelitian ini bertujuan untuk mengetahui bagaimana cara menentukan banyaknya pohon rentangan pada sebuah graf G dengan menggunakan teorema pohon matriks, serta menentukan banyaknya pohon rentangan pada graf wheels Wn untuk n = 2, 3, 4, dan 5 dan graf kipas Fn untuk n = 3, 4, 5, dan 6 menggunakan teorema pohon matriks. Metode penelitian yang digunakan adalah studi pustaka. Pada penelitian ini dapat disimpulkan: 1) teorema pohon matriks menjelaskan bahwa dalam menentukan banyaknya pohon rentangan pada suatu graf G dapat dilakukan dengan mencari nilai kofaktor dari matriks Laplacian L=D-A. Dalam hal ini D adalah matriks derajat dan A adalah matriks ketetanggaan dari graf G, dan nilai dari setiap kofaktor Cij pada matriks Laplacian adalah sama, 2) banyaknya pohon rentangan pada graf wheels Wn untuk n = 2, 3, 4,dan 5 dengan n anggota N adalah tho(W2) = 5, tho(W3) = 16, tho(W4) =45, dan tho(W5) = 121 , 3) banyaknya pohon rentangan pada graf kipas Fn untuk n= 3, 4, 5, dan 6 dengan adalah tho(F3) = 8, tho (F4) = 21 , tho(F5) = 55, dan tho(F6) = 108