Teorema Pohon Matriks Untuk Menentukan Banyaknya Pohon Rentangan Graf Bipartisi Komplit (Km,n)

Abstract

This research aims to observes panning tree number of complete bipartite graph (Km,n) by matrix-tree theorem.This research was using library research method which the step are:(1)Drawing complete bipartite graph (Km,n) where m= 1,2,3,4,and; (2)Determinin adjacency matrix and degree matrix of complete bipartite graph (Km,n); (3)Observing the different between degree matrix and adjacency matrix (laplacian matrix) from complete bipartite graph (Km,n); (4)Observing cofactor value of laplacian matrix from complete bipartite graph (Km,n); (5)Observing spanning tree number pattern from complete bipartite graph (Km,n); (6)Forming the formula within theorem; (7)Proving the theorem. The results of this research are as follows that the general form spanning tree number incomplete bipartite graph(Km,n) with m=1,2,3,4, n 1 and m, n ∈N where is: τ(Km,n) = m^(n-1).n^(m-1)

Keywords

• complete bipartite graph
• the matrix-tree theorem
• cofactor
• spanning tree