TREE

POHON (Tree)

 A. Definisi

      Pohon (Tree) telah di gunakan sejak tahun 1857 oleh Arthur Cayley (seorang matematikawan asal Inggris) untuk menghitung jumlah senyawa kimia. Pohon (tree) adalah sejenis graf tak berarah yang tidak mengandung sirkuit.

     Sifat-Sifat Pohon

     Misalkan G = (V,E) adalah graf tak-berarah sederhana dan jumlah simpulnya n, maka

1. G adalah pohon.
2. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.
3. G terhubung memiliki m = n-1 buah sisi.
4. G tidak mengandung sirkuit dan memiliki m = n-1 buah sisi.
5. G tidak mengandung sirkuit dan penambahan sati sisi pada graf akan membuat hanya satu sirkuit.
6. G terhubung dan semua sisinya adalah jembatan (jembatan adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen).

 B. Spanning Tree

    

     Adalah subgraf G yang merupakan pohondan mencangkup semua titik dari G. Pohon merentang di peroleh dengan cara menghilangkan sirkuit di dalam graf tersebut.

     Contoh :

      Minimal Spanning Tree dari Labeled Graph

      Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum 

      Contoh :

 C. Rooted Tree (Pohon Berakar)

      

     Adalah suatu tree yang mempunyai akar. Istilah-istilah / unsur-unsur yang ada pada pohon berakar:

1. Akar : Dinyatakan dengan lingkaran.
2. Daun
3. Cabang
4. Tinggi / Level / dept / dalamnya suatu vertex

      Contoh :

     SIfat Utama Pohon Berakar

1. Jika Pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).
2. Mempunyai Simpul Khusus yang disebut Root, jika simpul tersebut memiliki derajat keluar>=0, derajad masuk = 0.
3. Mempunyai simpul yang disebut sebagai daun / Leaf, jika Simpul tersebut berderajat keluar=0, dan berderajat masuk = 1.
4. Setiap simpul memiliki tingkatan / level yang dimulai dar root yang levelnya = 1 sampai  dengan level ke - npada daun paling bawah. Simpul yang mempunyai Level sama disebut bersaudara atau brother atau stribling.
5.  Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi.
6.  Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.
7.  Banyaknya Simpul Maksimim sampai Level N adalah : 2(N) - 1
8.  Banyaknya Simpul untuk setiap Level I adalah :

      Pohon Berurut Berakar (Ordered Rooted Tree)

      Adalah pohon berakar yang diberi label berurut secara sistematis. Sistem itu disebut Universal Address System. 

       Contoh : Dengan memberi nomor urutan.

                       NOL     : Pada akar

                       Nomor atas n gigis pada setiap titik simpul yang berjarak dari n akar.

      Gambar pohon berurut berakar di atas disebut Lexicographic order.

                        Pernyataan Aritmatika (a-b) / [(cxd)+e] dapat digambarkan dalam Lexicographic.

D. Algoritma Prim dan Algoritma Kruskal

   Kedua Algoritma ini berbeda dalam metodeloginya, tetapi keduanya mempunyai tujuan menemukan minimum spanning.

• Algorithm Kruskal menggunakan     edge.
• Algorithm Prim      menggunakan     vertex yang terhubung.

     Perbedaan prinsip antara Algoritma Prim dan Algoritma Kruskal adalah, jika pada Algoritma Prim sisi yang dimasukkan ke dalam T harus bersisihan dengan sebuah simpul di T, maka pada Algoritma Kruskal sisi yang dipilih tidak perlu bersisian dengan sebuah simpul di T, asalkan penambahan sisi tersebut tidak membentuk cyrcle.

     Algoritma Kruskal

     Pada Algoritma Kruskal, sisi (edge) dari Graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan kedalam himpunan T adalah sisi graph G yang sedemikian sehingga T adalah ( Tree ) Pohon. Sisi dari graph G ditambahkan ke T jiika ia tidak membentuk cycle.

1. T masik kosong.
2. Pilih sisi (i,j) dengan bobot minimum.
3. Pilih sisi (i,j) dengan bobot minimum berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T.
4. Ulangi langkah 3 sebanyak (n-2) kali.
5. Total langkah (n-1) kali. 

     Algoritma Prim

     Pada Algoritma Prim, dimulai pada vertex yang mempunyai sisi (edge) dengan bobot terkecil.

     Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang bersisian dengan sebuah simpul di T, sedemikian sehingga T adalah Pohon. Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle.

      (NOTE : Dua atau lebih edge kemungkinan mempunyai bobot yang sama, sehingga terdapat  pilihan vertice, dalam hal ini dapat diambil salah satunya)

1. Ambil sisi (edge) dari graph yang ber bobot minimum, masukkan kedalam T.
2. Pilih sisi (edge) (i,j) yang berbobot minimum dan bersisihan dengan simpul di T, tetapi (i,j) tidak membentuk cycle di T. Tambahkan (i,j) kedalam T.
3. Ulangi prosedur no 2 sebanyak (n-2) kali.