Electronic Theses and Dissertation

Abstrak penelitian ini dilakukan untuk mendapatkan sebuah formula penentuan sembarang subgraf kn dengan n vertex dan (???? ? 1) edge merupakan spanning tree atau bukan. hal ini dilakukan dengan cara mengidentifikasi matriks, yaitu pembentukan adjacency matrix dari semua subgraf kn dengan n vertex dan (???? ? 1) edge secara kombinasi dan dilanjutkan dengan menghitung determinan dari matriks b. matriks b adalah matriks yang diperoleh dari penghapusan sebuah baris pada incidence matrix dari subgraf kn dengan n vertex dan (???? ? 1) edge. sembarang subgraf tersebut merupakan spanning tree jika |????????????(????)| = 1. selain itu, terdapat program yang dibuat dengan aplikasi adobe flash cs4 dan codeblocks untuk mempermudah mendapatkan semua subgrafnya yang spanning tree atau bukan untuk 2 ? ???? ? 7. kata kunci: subgraf, vertex, edge, spanning tree, adjacency matrix, incidence matrix, determinan. abstract this research was conducted to obtain a formula determining any subgraph kn with n vertex and (???? ? 1) edge is a spanning tree or not. this is done by identifying the matrix, which is forming the adjacency matrix of all subgraphs kn with n vertex and (???? ? 1) edge in combination and continued by calculating the determinant of matrix b. the b matrix is a matrix obtained from eliminating a line on incidence matrix from subgraph kn with n vertex and (???? ? 1) edge. any subgraph is spanning tree if |???????????? (????)| = 1. in addition, there is the program created with adobe flash cs4 and codeblocks applications to make it easier to get all the subgraphs that are spanning trees or not for 2 ? ???? ? 7. keywords: subgraph, vertex, edge, spanning tree, adjacency matrix, incidence matrix, determinant.