pohon

POHON

Pohon (tree) sudah digunakan dari 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, 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 

   

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. 

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   :

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.

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.

 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.

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: