Teorema Pohon Matriks Untuk Menentukan Banyaknya Pohon Rentangan Graf Bipartisi Komplit ( K m,n )
Novia Dwi Rahmawati

## Universitas Hasyim Asy’ari Jombang
noviadwi_rahmawati87@yahoo.co.id

## 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 ∈ 𝑁 where is:
𝜏 (K m,n ) = 𝑚 𝑛−1 . 𝑛 𝑚 −1
Keywords : complete bipartite graph, the matrix-tree theorem, cofactor, spanning tree

## Abstrak
Penelitian ini bertujuan untuk menentukan bentuk umum banyaknya pohon rentangan pada  graf  bipartisi  komplit  (K m,n )  dengan  menggunakan  teorema  pohon  matriks. Penelitian  ini  adalah  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(K m,n ) dan matriks derajat dari graf bipartisi komplit;  (3)  Mencari nilai selisih dari matrik derajat dan matriks  adjacency  (matriks  laplacian)  dari  graf  bipartisi  komplit;  (4)  Mencari  nilai kofaktor  dari  matriks  laplacian  dari  graf  bipartisi  komplit;  (5)  Melihat  pola banyaknya  pohon  rentangan  dari  graf  bipartisi  komplit;  (6)  Merumuskan  pola  ke dalam teorema; (7) Membuktikan teorema. Penelitian ini menunjukkan 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 𝜏 (K m,n ) = 𝑚 𝑛−1 . 𝑛 𝑚 −1
Kata  Kunci: graf  bipartisi  komplit,  teorema  pohon  matriks,  kofaktor,  pohon rentangan

## PENDAHULUAN
Alam  semesta  memuat  bentuk-bentuk  dan  konsep  matematika, meskipun  alam  semesta  tercipta  sebelum  matematika  itu  ada.  Alam semesta  serta  segala  isinya  diciptakan  Allah  dengan  ukuran-ukuran yang  cermat  dan  teliti,  dengan  perhitungan-perhitungan  yang  mapan, dan dengan rumus-rumus serta persamaan yang seimbang dan rapi. 1 Allah berfirman dalam Al Qur‟an surat Al Qamar / 54 ayat 49: اَّنِإ َّ ُ ٍ يْ َ ُااَ يْ َ َ ٍ َ َ ِ
“Sesungguhnya  kami  menciptakan  segala  sesuatu  menurut ukuran”(Q.S. Al-Qamar / 54: 49).
Dari  segi  bahasa  kata  tersebut  dapat  berarti kadar  tertentu yang tidak bertambah atau berkurang, atau berarti kuasa . Tetapi karena ayat tersebut  berbicara  tentang  segala  sesuatu  yang  berada  dalam  kuasa Allah, maka adalah lebih tepat memahaminya dalam arti ketentuan dan sistem  yang  telah  ditetapkan  terhadap  segala  sesuatu .  Tidak  hanya terbatas  pada  salah  satu  aspeknya  saja.  Manusia  misalnya,  telah  ada kadar yang ditetapkan Allah baginya. 2
Dalam ayat lain juga disebutkan:
يِذَّلا ُ َل ُ يْ ُ ِااَااَ َّللا ِ يْ ااَا يَْ َا يْذِ َّ َيَ اً َلَا يَْ َا يْ ُ َ ُ َل ٌ  ِ َ ِ ِ يْ ُ يْلا َ َ َ َا َّ ُ ٍ يْ َ ُاَ َّ َ َيَ اً  ِ يْ َيَت ”Yang kepunyaan-Nya-lah kerajaan langit dan bumi, dan dia tidak mempunyai  anak, dan tidak ada sekutu  baginya  dalam kekuasaan (Nya),dan  dia  Telah  menciptakan  segala  sesuatu,  dan  dia menetapkan  ukuran-ukurannya dengan serapi-rapinya”  (Q.S.  Al- Furqaan / 25: 2).
1 Abdusysyakir, Ketika  Kyai  Mengajar  Matematika ,  (Malang:  UIN  Malang Press, 2007), hlm. 79.
2 Shihab,  M.  Quraish, Tafsir  Al-Misbah  Volume  13  Pesan,  Kesan  & Keserasian Al Qur’an , (Ciputat: Lentera Hati, 2003), hlm. 482.
Novia Dwi Rahmawati : Teorema Pohon Matriks | | 89
Ayat  di  atas  menjelaskan  bahwa  segala  sesuatu  yang  ada  di  alam ini  ada  ukurannya,  ada  hitungan-hitungannya,  ada  rumusnya,  atau  ada persamaannya. Ahli matematika atau fisika tidak membuat suatu rumus sedikitpun. Mereka hanya menemukan rumus atau persamaan, sehingga rumus-rumus  yang  ada  sekarang  bukan  diciptakan  manusia  sendiri, tetapi sudah disediakan. Manusia hanya menemukan dan
menyimbolkan dalam bahasa matematika. 3
Dewasa  ini  semakin  banyak  muncul  penggunaan  model matematika  maupun  penalaran  matematika  sebagai  alat  bantu  dalam menyelesaikan  permasalahan  yang  dihadapi  dalam  berbagai  disiplin ilmu. Teori graf merupakan salah satu cabang matematika yang penting dan  banyak  manfaatnya  karena  teori-teorinya  dapat  diterapkan  untuk memecahkan  masalah  dalam  kehidupan  sehari-hari.  Dengan  mengkaji dan  menganalisa  model  atau  rumusan  teori  graf  dapat  diperlihatkan peranan  dan  kegunaannya  dalam  memecahkan  permasalahan. Permasalahan  yang  dirumuskan  dengan  teori  graf  dibuat  sederhana, yaitu  diambil  aspek-aspek  yang  diperlukan  dan  dibuang  aspek-aspek lainnya. 4
Salah  satu  materi  dalam  teori  graf  adalah  pohon  ( tree ).  Pohon ( tree )  didefinisikan  sebagai  graf  tak-berarah  terhubung  yang  tidak memuat  sirkuit.  Menurut  definisi  tersebut,  ada  dua  sifat  penting  pada pohon ( tree ) yaitu terhubung dan tidak memuat sirkuit. 5
Misalkan G graf dan H subgraf dari G . H disebut subgraf rentangan ( spanning  subgraph )  dari  graf G jika  order H sama  dengan  order G, atau dengan kata lain jika V(H)=V(G) . Subgraf rentangan H dari graf G dapat dengan mudah diperoleh dengan cara menghapus satu atau lebih dari  sisi  di G .  Dengan  demikian,  jika F adalah  himpunan  bagian  dari E(G) , maka graf G–F pasti merupakan subgraf rentangan dari G. 6
Berkaitan  dengan  subgraf  rentangan,  maka  permasalahan  yang menarik untuk dikaji adalah menentukan banyaknya subgraf  rentangan yang  berbentuk  pohon  dari  suatu  graf,  yang  dikenal  dengan  sebutan banyaknya pohon rentangan ( spanning tree number) .
3 Abdusysyakir, Ketika  Kyai  Mengajar  Matematika ,  (Malang:  UIN  Malang Press, 2007), hlm. 80.
4 Purwanto, Matematika Diskrit , (Malang: IKIP Malang, 1998), hlm.1.
5 Chartrand,  Gary  dan  Lesniak.  Graphs  and  Digraphs,  (California:  Greg Hubit Bookwords, 1986), p. 67.
6 Op.cit.p.8.
90 | Fokus : Jurnal Kajian Keislaman dan Kemasyarakatan, Vol.1, No. 01, 2016
Misalkan G graf  dengan  order p ( p ≥ 1)  dan  ukuran q serta himpunan  titik V ( G) = v 1 , v 2 ,..., vp . Matriks  keterhubungan  titik (atau matriks  keterhubungan )  dari  graf G ,  dinotasikan  dengan A ( G ),  adalah matriks  ( p x p )  dengan  unsur  pada  baris  ke- i dan  kolom  ke- j bernilai  1 jika titik vi terhubung langsung dengan titik vj serta bernilai 0 jika titik vi tidak terhubung langsung dengan  titik vj .  Dengan kata  lain, matriks adjacency dapat ditulis A ( G) =  [ ij ],1 ≤ i , j ≤ p , dengan:
𝑎 𝑖𝑗 = 1, 𝑗𝑖𝑘𝑎 𝑣 𝑖 𝑣 𝑗 ∈ 𝐸(𝐺) 0, 𝑗𝑖𝑘𝑎 𝑣 𝑖 𝑣 𝑗 ∉ 𝐸(𝐺)
Matriks keterhubungan suatu graf G adalah matriks simetri dengan unsur 0 dan 1 dan memuat nilai 0 pada diagonal utamanya. 7
Matriks  derajat  dari  matriks G ,  dinotasikan  dengan D(G ),  adalah matriks diagonal  yang elemen baris ke- i dan kolom ke- i adalah derajat dari v i , i = 1, 2,3,..., p Jika D ( G )=[ d ij ],1 ≤ i , j ≤ p ,maka d ii = deg v dan d ij = 0 untuk i ≠ j .  Matriks T(G) = D(G )- A ( G ),  disebut  matriks Laplacian dan  sebarang  kofaktor  dari T(G) sama  banyaknya  pohon  rentangan ( spanning tree number ) pada G , yaitu τ( G ). 8
Untuk  menentukan  pohon  rentangan  dari  suatu  graf  terhubung, biasanya  dilakukan  dengan  cara  menghapus  sisi-sisi  sehingga  graf tersebut tidak lagi mengandung sikel. Akan tetapi, cara ini memerlukan waktu  yang  lama,  sehingga  diperlukan  suatu  cara  atau  rumusan  baku untuk  menentukan  banyaknya  pohon  rentangan  dari  suatu  graf,  yaitu dengan cara direpresentasikan dalam bentuk matriks. Bentuk graf yang dinyatakan dalam suatu matriks kemudian diselesaikan dengan metode- metode yang berlaku pada matriks.
7 Op.cit.p.4.
8 Agnarsson,  G.  dan  Greenlaw,  R,  Graph  Teory  :  Modeling,  Applications, and Alghoritms , (New Jersey: Pearson Prentice Hall, 2007), p.112.
Novia Dwi Rahmawati : Teorema Pohon Matriks | | 91
Berdasarkan  pertanyaan  penelitian,  maka  tujuan  penelitian  ini adalah  untuk  menentukan  banyaknya  pohon  rentangan  pada  graf bipartisi komplit 𝐾 𝑚 ,𝑛 dengan  teorema pohon matriks. Penelitian  ini  adalah  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 ( K m,n )  dan  matriks  derajat  dari  graf bipartisi komplit; 3)Mencari nilai selisih dari matrik derajat dan matriks adjacency (matriks 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.

## HASIL DAN PEMBAHASAN Definisi 1
Sisi ( , ) e u v  dikatakan  menghubungkan  titik  u  dan  v.  Jika ( , ) e u v  adalah sisi dari graf G, maka u dan v  disebut terhubung langsung (adjacend), u dan e serta v dan e disebut terkait langsung (incident). Untuk selanjutnya, sisi ( , ) e u v  akan ditulis e uv  . 9
Dari definisi di atas, maka dapat digambarkan sebagai berikut:
u e v
Gambar 1 Graf G dengan Sisi   v u e ,  Menghubungkan Titik u dan v
Karena   v u e ,  sisi  di G ,  maka u dan v disebut  terhubung langsung  ( adjacent ).  Sedangkan e dan u serta e dan v disebut  terkait langsung ( incident ).
Dalam
Islam, definisi adjacent dan incident dapat direpresentasikan  untuk  menggambarkan  peristiwa  Sa‟i  dalam  ibadah
9 Chartrand,  Gary  dan  Lesniak.  Graphs  and  Digraphs,  (California:  Greg Hubit Bookwords, 1986), p. 4.
v 1 v 2
Shafa Marwah
92 | Fokus : Jurnal Kajian Keislaman dan Kemasyarakatan, Vol.1, No. 01, 2016
haji.  Dalam  Al-Quran  dijelaskan  dalam  surat  Al-Baqarah  /  2  ayat  158 yang berbunyi:
ِ يْيَ َع َحاَ ُج لاَ  َ َ َ يْعا ِاَأ َتيْيَيَبيْلا َّجَح يْ َ َ  ِ َّ لا ِ ِئاَعَ  يْ ِ  َةَايْ َ يْلاَا اَفَّصلا َّنِإ ٌييِ َع ٌ ِ اَ  َ َّ لا َّنِ َ  اً يْيَيَ  َ َّ َ َت يْ َ َا اَ ِِ  َ َّ َّ َ  يْنَأ
Sa‟i merupakan salah satu rukun haji dan umrah, dilakukan setelah selesai  melakukan  thawaf.  Sa‟i  adalah  lari  kecil-kecil  yang  dilakukan antara  bukit  Shafa  dan  Marwa.  Terkait  dengan  kejadian  diatas,  maka kejadian  tersebut  dapat  direpresentasikan  pada  graf  yang  terdiri  dari  2 titik dan 1 sisi.

## Gambar 2 Representasi Graf Terhadap Ibadah Sa‟i
Dari  Gambar  1  diatas  merupakan  salah  satu  contoh  dari  bentuk graf  komplit 𝐾 2 yang  terdiri  dari  dua  titik  dan  satu  sisi.  Titik-titiknya adalah bukit shafa dan marwa sedangkan sisinya adalah perjalanan sa‟i itu  sendiri.  Jadi  bukit  shafa  ( 1 v )  dengan  perjalan  sa‟i  (sisi)  adalah incident sedangkan bukit Shafa ( 1 v ) bukit Marwa ( 2 v ) adalah adjacent .

## Definisi 2
Graf  bipartisi  komplit  (complete  bipartite  graph)  adalah  Graf bipartisi  dengan  himpunan  partisi  X  dan  Y  sehingga  masing- masing  titik  di  X  dihubungkan  dengan  masing-masing  titik  di  Y oleh  tepat  satu  sisi.  Jika m X  dan n Y  ,  maka  graf  bipartisi tersebut dinyatakan dengan K m,n. 10
10 Purwanto, Matematika Diskrit , (Malang: IKIP Malang, 1998), hlm.22.
Contoh:
K 1,3 K 2,3 K 3,3
Gambar 3 Graf Bipartisi Komplit
Pada Gambar 3 akan dijelaskan sebagai berikut:
K 1,3 adalah graf bipartisi komplit dengan
} { 1 u X  , 1  X } , , { 3 2 1 v v v Y  , 3  Y
K 2,3 adalah graf bipartisi komplit dengan
} , { 2 1 u u X  , 1  X } , , { 3 2 1 v v v Y  , 3  Y
K 3,3 adalah graf bipartisi komplit dengan } , , { 3 2 1 u u u X  , 1  X } , , { 3 2 1 v v v Y  , 3 

## Y
Dalam  Islam,  definisi  graf  bipartisi  komplit  dapat  dipresentasikan untuk  menggambarkan  rukun  Islam  yang  menjadi  dasar  bagi  umat Islam.
Rukun  Islam  menjadi    landasan  operasional  dari  Rukun  Iman.
Belum  cukup  dikatakan  beriman  hanya  dengan  mengerjakan  Rukun Islam tanpa ada upaya untuk menegakkannya. Rukun Islam merupakan training /pelatihan  bagi  orang  mukmin  menuju  mardhotillah/keridhoan Allah SWT.
Syahadat  adalah agreement (perjanjian)  antara  seorang  muslim dengan  Allah  SWT  [7:172].  Seseorang  yang  telah  menyatakan  Laa
1 u 1 u 2 u 1 u 2 u 3 u 1 v 1 v 1 v 2 v 2 v 2 v 3 v 3 v 3 v
94 | Fokus : Jurnal Kajian Keislaman dan Kemasyarakatan, Vol.1, No. 01, 2016
ilaaha ilallaah berarti telah siap untuk fight (bertarung) melawan segala bentuk ilah di luar Allah SWT di di dalam kehidupannya [29:2].
Shalat adalah training sebagai latihan agar setiap muslim di dalam kehidupannya  adalah  dalam  rangka  sujud  (beribadah)  kepada  Allah SWT [6:162].
Zakat  adalah training ,  yaitu  sebagai  latihan  agar  menginfakkan hartanya, karena setiap harta seorang muslim adalah milik Allah SWT [57:7,  59:7].  “Engkau  ambil  zakat  itu  dari  orang-orang  kaya  mereka dan  engkau  kembalikan  kepada  orang-orang  fakir  mereka”  (HR Mutafaqun „alahi).
Shaum  adalah training ,  yaitu  sebagai  latihan  pengendalian kebiasaan  pada  jasmani,  yaitu  makan  dan  minum  dan  ruhani,  yaitu hawa nafsu [2:185].
Haji adalah training , yaitu sebagai latihan dalam pengorbanan jiwa dan harta di jalan Allah SWT, mengamalkan persatuan dan persamaan derajat dengan sesama manusia [22:27-28].
Rukun Islam dapat direpresentasikan dalam suatu graf yang terdiri dari  6  titik  yang  dipartisi  menjadi  2  bagian,  dan  masing-masing  titik pada  suatu  partisi  terhubung  langsung  dengan  semua  titik  pada  partisi yang lain.
Gambar 4 Representasi Graf  Terhadap Rukun Islam
Dari  Gambar  4  di  atas  merupakan  salah  satu  contoh  dari  bentuk graf  bipartisi  komplit K 1,5 yang  terdiri  dari  dari  6  titik  yang  dipartisi menjadi 2 bagian, dan masing-masing titik pada suatu partisi terhubung langsung dengan semua titik pada partisi yang lain. Titik yang terletak pada  partisi  pertama  adalah  Rukun  Islam,  sedangkan  titik-titik  yang terletak  pada  partisi  kedua  adalah  Syahadat,  Shalat,  Zakat,  Puasa  dan Haji. Rukun Islam Syahadat Shala t Zaka t Puasa Haji
Teorema:
Misal 𝐾 𝑚 ,𝑛 graf    bipartisi  komplit  dengan , m n N  ,  maka banyaknya pohon rentangan dari graf  bipartisi komplit 𝐾 𝑚 ,𝑛 adalah:
 𝐾 𝑚 ,𝑛 =    𝑚 𝑛−1 .   𝑛 𝑚 −1

## Bukti:
Graf  bipartisi  komplit (𝐾 𝑚,𝑛 ) dengan , m n N  dapat  digambar
sebagai berikut:
Gambar 5 Graf Bipartisi Komplit 𝐾 𝑚 ,𝑛
Misal 𝐾 𝑚 ,𝑛 adalah graf bipartisi  komplit dengan , m n N  , maka matriks adjacency dari graf  bipartisi komplit 𝐾 𝑚 ,𝑛 .
 v 3 v 2 v 1 v n u m  u 3 u 2 u 1
v 1 v 2 v 3  v n u 1 u m  u 2 u 3
96 | Fokus : Jurnal Kajian Keislaman dan Kemasyarakatan, Vol.1, No. 01, 2016
  , m n A K 
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0
 
                                                                 
Matriks derajat dari graf bipartisi komplit 𝐾 𝑚 ,𝑛
  , m n D K  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 n n n n m m m m   
                                                               
Setelah mendapatkan bentuk matriks adjacency dan matriks derajat maka  akan  dicari  matriks  laplacian  dan  nilai  kofaktor   11 C matriks laplacian  dari  matriks-matriks  tersebut,  yaitu  dengan  menggunakan persamaan:
𝑇 𝐺     = 𝐷 𝐺  −  𝐴 𝐺 u 1 u 3 u 2 
u m  v 1 v 2 v 3  v n  u 1 u 2 u 3   u m v 1 v 2 v 3 v n
Novia Dwi Rahmawati : Teorema Pohon Matriks | | 97
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
( ) 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 n n n n T G m m m m  
                                                                                        1 1 0 0 0 0
1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0    
                                           
=
0 0 0 1 1 1 1 0 0 0 1 1 1
1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0
1 1 1 1 0 0 0
1 1 1 1 0 0 0 n n n n m m m m                                                                

                                  
Jadi didapatkan matriks laplacian bagi � 〰 𝑚 ,𝑛 adalah
0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1
0 0 0 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 0 0
0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 n n n n m m m m                                                                                                    
98 | Fokus : Jurnal Kajian Keislaman dan Kemasyarakatan, Vol.1, No. 01, 2016
Dengan  banyaknya  kolom  adalah m n  dan  banyaknya  baris
m n  atau matriks dengan orde m n 
Setelah  mendapatkan  matriks  laplacian  maka  selanjutnya  akan dicari nilai kofaktor   11 C dari matriks laplacian, yaitu:
C 11 = (-1) 1+1 det ( M 11 )
11 C dari 0 0
0 1 1 1 1 0 0 0 1 1 1 1
0 0 0 1 1 1 1
0 0 0 1 1 1
1 1 1 1 1 0 0
0 1 1 1 1 0 0
0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 n n n n m m m m                                                                                                     =   2 1  det 0 0 1 1 1 1 0 0 1 1 1 1 0 0
1 1 1
1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 n n n m m m m                                                  
                                 
Dengan  banyaknya  kolom  adalah
1 m n   dan  banyaknya  baris 1 m n   atau matriks dengan orde 1 m n

##  
Melalui  operasi  baris  elementer, M 11 direduksi  menjadi  matriks segitiga atas diperoleh,
2 3 2 2 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 ( 1) ( 1) ( 1) ( 1) 0 0 0 2( 1) ( 1) ( 1) 0 0 0 0 ( 1) ( 1) ( 1) 3( 1) 0 0 0 0 0 2( 1) ( 1) ( ( 2) n n n n n n mn m m m m n n n n m n m m m m m m mn m mn m mn m m n m m m n m m m m m n n m n m                                                                        ( 1) 0 0 0 0 0 0 ( ( 1)) n n n n m n n m m m n n m n m                                                   
Dimana det M 11 tidak lain adalah hasil perkalian  diagonal  matriks segitiga atas tersebut. Jadi,
Det M 11 = n . n . … . n . ( 1) mn m n   . 2 2( 1) ( 1) m n m m mn m     . 3 2 2 3( 1) 2( 1) m n m m m n m m     . … . ( 1)
( ( 1)) n n n n m n n m m m n n m n m      = 1 m n  . 1 n m 
Jadi  terbukti  bahwa  banyaknya  pohon  rentangan  ( K m,n )  = 1 m n  .
1 n m 

## PENUTUP Simpulan
Segala  sesuatu yang  ada  di  alam  ini  ada  ukurannya,  ada  hitungan- hitungannya,  ada  rumusnya,  atau  ada  persamaannya.  Bentuk  umum banyaknya pohon rentangan pada graf bipartisi komplit  ( K m,n ) dengan n ≥ 1 dan m,n  N adalah:
 𝐾 𝑚 ,𝑛 =    𝑚 𝑛−1 .   𝑛 𝑚 −1
Dalam
Islam, definisi adjacent dan incident dapat direpresentasikan  untuk  menggambarkan  peristiwa  Sa‟i  dalam  ibadah haji.
100 | Fokus : Jurnal Kajian Keislaman dan Kemasyarakatan, Vol.1, No. 01, 2016

## DAFTAR PUSTAKA
Abdusysyakir. Ketika  Kyai  Mengajar  Matematika .  Malang.  UIN
Malang Press, 2007.
Agnarsson,  G.  dan  Greenlaw,  R. Graph  Teory  :  Modeling, Applications,  and  Alghoritms. New  Jersey:Pearson  Prentice Hall, 2007.
Chartrand,  Gary  dan  Lesniak. Graphs  and  Digraphs .  California:  Greg Hubit Bookwords, 1986.
Purwanto. Matematika Diskrit . Malang: IKIP Malang, 1998.
Shihab,  M.  Quraish. Tafsir  Al-Misbah  Volume  13  Pesan,  Kesan  &
KeserasianAl Qur’an . Ciputat: Lentera Hati, 2003.