Aplikasi teorema matriks-pohon untuk menentukan banyaknya pohon rentangan pada graf bipartisi komplit (K_m,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 bipartisi komplit (K_m,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 (K_m,n) dengan m=1,2,3,4, n≥1 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.

Berdasarkan hasil pembahasan dapat diperoleh bahwa bentuk umum banyaknya pohon rentangan pada graf bipartisi komplit (K_m,n) dengan m=1,2,3, 4,n≥1 dan m,n∈... adalah τ(Km,n)= m^n-1.n^m-1

Penggunaan teorema matriks-pohon untuk menentukan banyaknya pohon rentangan pada graf bipartisi komplit (K_m,n) ini masih terbuka bagi peneliti lain untuk digunakan pada jenis-jenis graf yang lain seperti graf lintasan, graf sikel dan lain sebagainya.

ENGLISH:

One main problem in graph topic is to determine spanning tree number at graph. Spanning tree is subgraph of graph G which contain all spot from G that part of a tree. To determining spanning tree of connected graph, it usually done cut sides therefore those not bring along the sikel.

The objection of this research is to observe spanning tree number of complete bipartite graph (Km,n) by application of matrix-tree theorem.

Method of this research was using library research method which the step are: (1) Drawing complete bipartite graph (K_m,n) where m = 1, 2, 3, 4,...n and m,n...N; (2) Determining adjacency matrix and degree matrix of complete bipartite graph(K_m,n); (3) Observing the different between degree matrix and adjacency matrix (laplacian matrix) from complete bipartite graph (K_m,n); (4) Observing cofactor value of laplacian matrix from complete bipartite graph (K_m,n); (5) Observing spanning tree number pattern from complete bipartite graph (Km,n); (6) Forming the formula within theorem; (7) Proving the theorem.

According to the result of this research can be concluded that the general form spanning tree number in complete bipartite graph (Km,n) with m = 1, 2, 3, 4, where m,n...N is...

Application of matrix-tree theorem is to determine spanning tree number of complete bipartite graph (K_m,n) thus, this theorem is still open for another researcher to aplly it in other kind of graph, such as path graph, sycle graph etc.