Materi Pohon (tree) Pada Matematika Diskrit

POHON (Tree)

A. Definisi Pohon dan Hutan

          Pohon (tree) pada matematika diskrit adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. Diagram pohon dapat digunakan sebagai alat untuk memecahkan masalah dengan menggambarkan semua alternative  pemecahan.

Jadi, dapat disimpulkan bahwa pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika :

~ Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).

~ Graph tersebut terhubung .

Contoh   : 

Hutan ( forest ) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit.

Ciri – ciri hutan :

banyaknya titik = n

banyaknya pohon = k

banyaknya rusuk = n-k 

B. Sifat Pohon   

1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi.

2. Jika G tidak mempunyai sirkuit maka G merupakan pohon.

3. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.

4. Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.

5.Misalkan G adalah graf sederhana dengan jumlah simpul n,jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit. 

C. Macam Macam Pohon

     1. Spanning Tree

Spanning Tree adalah subgraph G merupakan pohon dan mencakup semua titik dari G.Pohon merentang di peroleh dengan cara menghilangkan sirkuit didalam graf tersebut. 

Contoh :

T₁, T₂, T₃, T₄ ® merupakan spanning tree dari G

Minimal spanning tree dari labeled graph  Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum.

      2. Rooted Tree ( Pohon Berakar )

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

1.  Akar :dinyatakan dengan lingkar-aN

2. Daun

3.  Cabang

4.  Tinggi / level / dept / dalamnya suatu vertex

Sifat 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, dan derajat masuk = 0.

3.      Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.

4.      Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada 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 Maksimum sampai Level N adalah :

2 (N) - 1

8.      Banyaknya Simpul untuk setiap Level I adalah

N              ∑ 2 (I -1)              (I-1)

                  a. macam pohon berakar

      Pohon Berurut Berakar (Ordered Rooted Tree) 

     adalah  pohon berakar yang diberi label berurut secara sistematis. Sistem itu disebut Universal Adress System.

Contoh : dengan memberi nomor urutan; NOL pada akar, kemudian memberikan nomor atas n gugus pada setiap titik simpul yang berjarak n dari akar.