PENENTUAN BANYAKNYA POHON PERENTANG MENGGUNAKAN TEOREMA POHON MATRIKS

Abstract

Setiap graf terhubung G pasti memuat pohon perentang T, yaitu subgraf dari G yang berupa pohon dan memuat semua titik G. Banyaknya pohon perentang dari graf G adalah berhingga. Dalam penelitian ini dibahas terkait penentuan banyaknya pohon perentang dari graf G dengan menggunakan teorema pohon matriks. Suatu graf bisa direpresentasikan menjadi bentuk matriks, seperti matriks derajat (D), matriks ketetanggaan (A), dan matriks Laplacian (L). Tujuan dari penelitian ini ialah untuk menganalisis matriks Laplacian (L) dan membuktikan teorema pohon matriks. Matriks L adalah selisih antara matriks D dan A dengan matriks D dan A ialah matriks hasil representasi dari graf G. Matriks L ini dapat digunakan pada teorema pohon matriks untuk mencari banyaknya pohon perentang dari graf G, yaitu dengan mencari nilai sebarang kofaktor dari matriks L. Pada penelitian ini dapat disimpulkan bahwa teorema pohon matriks bisa digunakan untuk mencari banyaknya pohon perentang dari graf G dengan graf G merupakan graf sederhana terhubung dan graf tak berarah, sehingga banyaknya pohon perentang dari graf G ialah sama dengan nilai sebarang kofaktor dari matriks L.

Kata Kunci : representasi graf, matriks Laplacian, kofaktor.