TREE

TREE

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 tidak mengandung 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 :

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.

Contoh   :

ALGORITMA KRUSKAL DAN ALGORITMA PRIM

Baik Algoritma Prim maupun Algoritma Kruskal digunakan untuk membentuk minimum spanning tree (dipelajari dalam Matematika Diskrit). Perbedaan prinsip antara algoritma Prim dan Kruskal adalah jika pada algoritma Prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T, maka pada algoritma Kruskal sisi yang dipilih tidak perlu bersisian dengan simpul di T asalkan penambahan sisi tersebut tidak membentuk sirkuit.

Algoritma Kruskal

Pada algoritma kruskal, sisi (edge) dari Graph diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar.

Sisi yang dimasukkan ke dalam himpunan T adalah sisi graph G yang sedemikian sehingga T adalah Tree (pohon). Sisi dari Graph G ditambahkan ke T jika ia tidak membentuk cycle.

1. T masih 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 Tree (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. Ambilsisi (edge) dari graph ygberbobot minimum, masukkankedalam T
2. Pilihsisi (edge) (i,j) ygberbobot minimum danbersisisandengansimpul di T, tetapi (i,j) tidakmembentuk cycle di T. tambahkan (i,j) kedalam T
3. Ulangiprosedur no 2 sebanyak (n-2) kali

Langkah-langkah dalam algoritma Kruskal adalah sebagai berikut:

1.   Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi dengan bobot terkecil sampai terbesar.

2.  Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit di pohon. Tambahkan sisi tersebut ke dalam pohon.

3.  Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf).

Berdasarkan gambar di atas, maka dilakukan pengurutan sisi pada graf mulai dari sisi dengan bobot terkecil sampai terbesar dapat dilihat pada tabel berikut:

Bobot	Sisi
10	(F,G)
14	(G,H)
15	(A,C)
20	(D,H)
25	(B,E)
30	(D,E)
35	(A,D)
40	(A,B)
45	(C,E)
48	(E,F)
50	(E,G)

Untuk lebih memahami perbedaan algoritma Prim dan algoritma Kruskal yang keduanya merupakan algoritma untuk pohon merentang minimum, maka dari gambar di atas dapat dicari pohon merentang minimumnya dengan menggunakan kedua algoritma tersebut. Langkah-langkah pembentukan pohon merentang minimumnya dapat dilihat pada gambar berikut ini:

 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)

 

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.

Terminologi pada Pohon Berakar

• Child atau children (Anak) dan parent (orangtua)
• Path (lintasan)
• Descendant (Keturunan) dan ancestor (leluhur)
• Sibling (saudara kandung)
• Subtree (subpohon)
• Degree (derajat)
• Leaf (daun)
• Internal nodes (simpul dalam)
• Level (tingkat)
• Height (tinggi) atau depth (kedalaman)

Child atau children (Anak) dan parent (orangtua)

Simpul y dikatakan anak simpul x jika ada sisi dari simpul x ke y dan Orangtua dari simpul y adalah simpul x.
Pada gambar G1 : 

• Simpul b, c dan d à anak dari simpul a 
• Simpul e dan f à anak dari simpul b 
• Simpul a àorangtua dari simpul b, c dan d 
• Simpul b à orangtua dari simpul e dan f  

Path (lintasan)

Lintasan dari simpul v_i ke simpul v_k adalah runtunan simpul-simpul v₁, v₂ ,…, v_k sedemikian hingga v_i adalah orangtua dari v_i+1 untuk 1 <= i <= K.
Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu k – 1. 
Pada gambar G1 : 

• Lintasan dari a ke j adalah a, b, e dan j 
• Panjang lintasan dari a ke j adalah 3

Descendant (Keturunan) dan ancestor (leluhur)

x adalah leluhur dari simpul y jika terdapat lintasan dari simpul x ke simpul y di dalam pohon dan keturunan dari simpul x adalah simpul y.
Pada gambar G1 :

• Simpul b adalah leluhur dari simpul h
• Simpul h adalah keturunan dari simpul b

Sibling (saudara kandung)

Sibling atau saudara kandung adalah simpul yang berorangtua sama
Pada gambar G1 :

• Simpul f saudara kandung dari e
• Simpul g bukan saudara kandung dari e karena orangtua berbeda 

Subtree (subpohon) 

Subtree dengan x sebagai akarnya adalah subgraf T’ = (V’,E’) sedemikian hingga V’ mengandung x dan semua keturunannya dan E’ mengandung sisi-sisi dalam semua lintasan yang berasal dari x
Pada gambar G2 :

• V’ = {b, e, f, h, i, j}
• E’ = {(b, e), (b, f), (e, h), (e, i), (e, j)}
• b adalah simpul akar 

Degree (derajat) 

Derajat sebuah simpul pohon berakar adalah jumlah subtree (jumlah anak) pada simpul tersebut. Derajat pohon berakar merupakan derajat keluar
Pada gambar G1 :

• Derajat simpul a : 3, simpul b : 2, simpul c : 0 dan simpul d : 1
• Derajat tertinggi (maksimum) : 3 

Leaf (daun)

Adalah simpul yang berderajat nol (tidak mempunyai anak) 
Pada gambar G1 :

• Merupakan daun : simpul c, f, h, i, j, l dan m.

Internal nodes (simpul dalam) 

Adalah simpul yang mempunyai anak
Pada gambar di samping :

• Merupakan simpul dalam : simpul b, d, e, g dan k

Level (tingkat) 

Akar mempunyai level = 0
Level simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut (gambar G3).

Height (tinggi) atau depth (kedalaman)

Adalah level maksimum dari suatu pohon
Nama lain : panjang maksimum lintasan dari akar ke daun
Pada gambar di samping :

• Pohon mempunyai tinggi atau kedalaman : 4

Ordered Tree (Pohon Berakar Terurut)

Adalah pohon berakar yang urutan anak-anaknya penting. Sistem universal dalam pengalamatan simpul-simpul pada pohon terurut adalah dengan memberi nomor setiap simpulnya seperti penomoran bab (beserta subbab) di dalam sebuah buku

Pohon m-ary

Adalah pohon berakar yang setiap simpul cabangnya mempunyai banyak n buah anak. Jika m = 2 --> Pohon biner (binary tree).
Pohon m-ary dikatakan pohon penuh (full) atau pohon teratur jika setiap simpul cabangnya mempunyai tepat m buah anak.

Penggunaan pohon m-ary

• Penurunan kalimat (dalam bidang bahasa)
• Direktori arsip di dalam komputer
• Struktur organisasi
• Silsilah keluarga (dalam bidang genetika)
• Struktur bab atau daftar isi di dalam buku
  Bagan pertandingan antara beberapa tim sepak bola
  Dll

Struktur direktori arsip di dalam sistem operasi Windows

Jumlah Daun pada Pohon m-ary Penuh

Pada pohon m-ary penuh dengan tinggi (height) h, jumlah daun (leaf) adalah : mh
Jika T bukan pohon m-ary penuh  ? jumlah daun ? mh
Jumlah seluruh simpul pohon m-ary pada pohon m-ary penuh dengan tinggi h :
    level 0    --> jumlah simpul = m0 = 1
    level 1    --> jumlah simpul = m1
    level 2    --> jumlah simpul = m2
            …
    level h    --> jumlah simpul = mh
    sehingga jumlah seluruh simpul adalah :





Sehingga jumlah seluruh simpul untuk T bukan pohon m-ary penuh :

 

 

Hubungan Jumlah Daun dan Simpul Dalam pada Pohon m-ary Penuh

Misalkan :
i = banyaknya simpul dalam
t = banyaknya simpul daun di dalam pohon biner penuh
m = banyaknya simpul child
    Sehingga : (m – 1) i = t – 1

Pohon biner

Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.