Aplikasi matriks pohon untuk menetukan banyaknya pohon rentangan pada graf komplit (K_n)

INDONESIA:

Salah satu permasalahan dalam topik graf adalah menentukan banyaknya pohon rentangan dari suatu graf. Pohon rentangan adalah subgraf dari graf G yang mengandung semua titik dari G dan merupakan suatu pohon. Untuk menentukan pohon rentangan dari suatu graf terhubung, biasanya dilakukan dengan cara memotong/ memutus sisi-sisi sehingga graf tersebut tidak lagi mengandung sikel.

Tujuan penelitian ini adalah untuk menentukan bentuk umum banyaknya pohon rentangan pada graf komplit (Kn) dengan menggunakan aplikasi matriks pohon.

Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research) dengan langkah-langkah penelitian sebagai berikut: (1) menggambar graf (Kn) dimana n ≥ 2 dan n N; (2) Menentukan matriks D(Kn) – A(Kn) yaitu matriks derajat graf komplit dikurangi matriks adjacency graf komplit; (3) Menentukan kofaktor dari matriks D(Kn) – A(Kn); (4) Melihat pola banyaknya pohon rentangan graf komplit (Kn). Kemudian merumuskan teorema yang dilengkapi dengan bukti-bukti.

Berdasarkan hasil pembahasan dapat diperoleh bahwa bentuk umum banyaknya pohon rentangan pada graf komplit (Kn) dengan n ≥ 2 dan n N
adalah Pohon rentangan (Kn) = nn-2
Penggunaan matriks pohon untuk menentukan banyaknya pohon rentangan pada graf komplit (Kn) ini masih terbuka bagi peneliti lain untuk digunakan pada jenis-jenis graf yang lain seperti graf lintasan, graf sikel dan lain sebagainya.