Tree (pohon) Matematika Diskrit

Definisi Pohon dan Hutan 
Pohon (tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama Arthur Cayley untuk menghitung jumlah senyawa kimia.Silsilah keluarga biasanya juga digambarkan pasa bentuk pohon.

Pohon (tree) 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   : 

Berikut adalah beberapa 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 tidakmengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit. 

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 :

 

T3, T4 ® merupakan spanning tree dari G

  

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

Contoh   :

 

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

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, 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)

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.

 

Gambar pohon berurut berakar di atas disebut Lexicographic order.

Pernyataan arimetika (a-b) / [(cxd)+e] dapat digambar dalam Lexicographic