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 bipartisi komplit (Km,n) dengan menggunakan aplikasi teorema matriks-pohon. Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research) dengan langkah-langkah penelitian sebagai berikut: (1) Menggambar graf bipartisi komplit (Km,n) dengan m = 1, 2, 3, 4, 1 n dan m, n ; (2) Menentukan matriks adjacency dan matriks derajat dari graf bipartisi komplit ; (3) Mencari nilai selisih dari matrik derajat dan matriks adjacency (matrik laplacian) dari graf bipartisi komplit ; (4) Mencari nilai kofaktor dari matrik laplacian dari graf bipartisi komplit ; (5) Melihat pola banyaknya pohon rentangan dari graf bipartisi komplit ; (6) Merumuskan pola ke dalam teorema; (7) Membuktikan teorema.
126. Aplikasi Teorema Matriks-Pohon untuk Menentukan Banyaknya Pohon Rentangan pada Graf Bipartisi Komplit
ABSTRAK
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 bipartisi komplit (Km,n) dengan menggunakan aplikasi teorema matriks-pohon. Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research) dengan langkah-langkah penelitian sebagai berikut: (1) Menggambar graf bipartisi komplit (Km,n) dengan m = 1, 2, 3, 4, 1 n dan m, n ; (2) Menentukan matriks adjacency dan matriks derajat dari graf bipartisi komplit ; (3) Mencari nilai selisih dari matrik derajat dan matriks adjacency (matrik laplacian) dari graf bipartisi komplit ; (4) Mencari nilai kofaktor dari matrik laplacian dari graf bipartisi komplit ; (5) Melihat pola banyaknya pohon rentangan dari graf bipartisi komplit ; (6) Merumuskan pola ke dalam teorema; (7) Membuktikan teorema.
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 bipartisi komplit (Km,n) dengan menggunakan aplikasi teorema matriks-pohon. Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research) dengan langkah-langkah penelitian sebagai berikut: (1) Menggambar graf bipartisi komplit (Km,n) dengan m = 1, 2, 3, 4, 1 n dan m, n ; (2) Menentukan matriks adjacency dan matriks derajat dari graf bipartisi komplit ; (3) Mencari nilai selisih dari matrik derajat dan matriks adjacency (matrik laplacian) dari graf bipartisi komplit ; (4) Mencari nilai kofaktor dari matrik laplacian dari graf bipartisi komplit ; (5) Melihat pola banyaknya pohon rentangan dari graf bipartisi komplit ; (6) Merumuskan pola ke dalam teorema; (7) Membuktikan teorema.
