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 :
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 :
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.3 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 :
|
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 pohon dianggap 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.
