Materi Tree (Pohon) (Matematika Diskret)

POHON (TREE)

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   : 

 

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 

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 membuatsatu sirkuit. 

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 :

T1, T2, 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   :

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

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)

Contoh Soal Pohon

1.    Spanning Tree

Perhatikan gambar suatu graf berikut :

Penyelesaian dengan Spanning Tree adalah

2.      Rooted Tree

Diketahui suatu bentuk Pohon Berakar T sebagai berikut :

Pohon diatas mempunyai :

a.       Simpul sebanyak = 8 dan edge = n - 1 = 8 – 1 = 7

b.      Root pada Pohon T diatas adalah Simpul P

c.       Mempunyai daun (Leaf) = 4, yaitu = R, S, V dan W

d.      Level (tingkatan) Pohon = 4 yaitu :

Level 1 = Simpul P 

Level 2 = Simpul Q dan T

Level 3 = Simpul R, S dan U

Level 4 = Simpul V dan W

e.       Ketinggian atau kedalaman = jumlah level = 4

f.       Weight atau berat atau bobot = jumlah daun = 4

Dalam gambar Pohon T diatas dapat dibentuk 2 buah hutan (forest), bila simpul P dihilangkan, yaitu :

Hutan 1 : Q,R,S

Hutan 2 : T,U,V,W

g.      Banyaknya Simpul Maksimum yang dapat terbentuk sampai Level 4 (bila simpul pada pohon dianggap penuh) adalah

2(N) – 1

2(4) – 1 = 16 – 1 = 15

 

h.      Banyaknya Simpul maksimum untuk setiap Level I(bila simpul pada pohondianggap penuh) adalah :

Maksimum Simpul pada level 2 = 2 ( I – 1)=

 2 ( 2 - 1 )  = 2

Maksimum Simpul pada level 3 = 2 (3-1)= 4

Maksimum Simpul pada level 4 = 2 (4-1)= 2

 

3. Terdapat sebuah permainan sederhana sebagai berikut: Seseorang memikirkan

sebuah angka antara 1 sampai 31. Anda harus menebak angka dengan benar.

Anda bertanya, ”Apakah angkanya x?” kemudian orang tersebut menjawab

dengan ”Ya”,”Lebih kecil dari x”, atau ”Lebih besar dari x”. Tunjukkan bahwa Anda

mampu menebak angka tersebut tidak lebih dari 5 kali tebakan.

Penyelesaian :

Petunjuknya adalah dengan selalu menebak angka yang menjadi titik tengah dari

jangkauan angka yang tersisa. Kemudian, jika tebakan salah akan mengurangi

separuh angka, hingga akhirnya akan tersisa satu angka. Gambar 11.6

memperlihatkan bagaimana proses tebakan berlangsung,mulai dari 16.

Setiap verteks adalah titik yang memutuskan nilai benar atau salah, jika salah maka nilai

tersebut berada di salah satu subtree dari dua subtree. Subtree pada sisi kiri berisi

nilai yang lebih kecil, dan subtree pada sisi kanan berisi nilai yang lebih besar.

Tree yang terbentuk hanya empat level, maka diperlukan tidak lebih dari 5 kali

tebakan.