Pohon Oleh: Panca Mudji Rahardjo
Definisi
Pohon – Adalah graf tak berarah terhubung yang tidak mengandung sirkuit.
Contoh: G1 dan G2 pohon, G3 dan G4 bukan pohon.
1
Definisi
Hutan (forest) – Adalah kumpulan pohon yang saling lepas.
Contoh: hutan yang terdiri dari 3 pohon
Sifat-sifat pohon
Misalkan T=(V,E) adalah graf taktak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan dibawah ini adalah ekivalen: – T adalah pohon, – Setiap pasang simpul di dalam T terhubung dengan lintasan tunggal, – T terhubung dan memiliki m = n – 1 buah sisi, – T tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi, – T tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit, – T terhubung dan semua sisinya adalah jembatan (jembatan adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen).
2
Pohon rentang
Misalkan G = (V,E) adalah graf tak berarah terhubung yang bukan pohon, yang berarti G terdapat beberapa sirkuit. G dapat diubah menjadi pohon T = (V1,E1) dengan cara memutuskan sirkuit yang ada. T disebut pohon rentang G bila V1 = V dan E1 ⊂ E. Pohon rentang adalah upagraf rentang yang berupa pohon dari graf terhubung.
Pohon rentang
Graf lengkap G dan empat buah pohon rentangnya, T1, T2, T3 dan T4
3
Pohon rentang
Cabang (branch) – Adalah sisi pohon rentang, rentang, yaitu sisi dari graf semula.
Tali-hubung (chord atau link) – Adalah sisi dari graf yang tidak terdapat di dalam pohon rentang.
Komplemen pohon – Adalah himpunan talitali-hubung beserta simpul yang bersisian dengannya.
Pohon rentang
Untuk graf terhubung G dengan n buah simpul dan m buah sisi: – Jumlah cabang = n – 1 – Jumlah talitali-hubung = mm-n+1
Untuk graf tak terhubung dengan k komponen, m buah sisi dan n buah simpul: – Jumlah cabang = n – k – Jumlah talitali-hubung = m – n + k
4
Pohon rentang
Rank graf G – Adalah jumlah cabang pada pohon rentang dari sebuah graf G
Nullity graf G – Adalah jumlah talitali-hubung pada graf G.
Rank + nullity = jumlah sisi graf G Fundamental circuit – Adalah sirkuit yang terbentuk dengan penampenambahan sebuah talihubung pada pohon rentang tali
Pohon rentang minimum
Jika G adalah graf berbobot, maka bobot pohon rentang T dari G didefinisikan sebagai jumlah bobot semua sisi di T. Di antara semua pohon rentang di G, pohon rentang yang berbobot minimum, disebut pohon rentang minimum. Terdapat dua buah algoritma: – Algoritma Prim, – Algoritma Kruskal.
5
Pohon rentang minimum (a)
(b)
Graf yang menyatakan jaringan jalur kereta api. Bobot pada tiap sisi menyatakan panjang rel kereta api (x 100 km) Pohon rentang yang mempunyai jumlah jarak minimum
Algoritma Prim
Langkah 1: – Ambil sisi dari graf G yang berbobot minimum, minimum, masukkan ke dalam T.
Langkah 2: – Pilih sisi (u,v) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi (u,v) tidak membentuk sirkuit di T. Tambahkan (u,v) ke dalam T.
Langkah 3: – Ulangi langkah 2 sebanyak nn-2 kali.
6
Algoritma Prim
Contoh
Algoritma Kruskal
Langkah 0:
– Pengurutan sisi graf dari bobot kecil ke bobot besar
Langkah 1:
– T masih kosong
Langkah 2:
– Pilih sisi (u,v) dengan bobot minimum yang tidak membentuk sirkuit di T. Tambahkan (u,v) ke dalam T.
Langkah 3:
– Ulangi langkah 2 sebanyak n – 1 kali.
7
Pohon berakar
Adalah pohon yang satu buah simpulnya diperlakukan sebagai akar dan sisi-sisinya di beri arah sehingga menjadi graf berarah. Akar mempunyai derajat masuk sama dengan nol, dan simpul-simpul lainnya berderajat masuk sama dengan satu. Daun (simpul terminal): adalah simpul dengan derajat keluar sama dengan nol.
Pohon berakar (a) (b)
Pohon berakar, Sebagai perjanjian, tanda panah pada sisi dapat dibuang.
8
Pohon berakar
Pohon dan dua buah pohon berakar yang dihasilkan dari pemilihan dua simpul berbeda sebagai akar.
Pohon berakar (terminologi)
Anak (child) dan orang tua (parent) – Simpul Y dikatakan anak simpul X jika ada sisi dari simpul X ke simpul Y. – X disebut orangtua Y.
Contoh: b,c,d adalah anak simpul a.
9
Pohon berakar (terminologi)
Lintasan (path) – Lintasan dari simpul v1 ke simpul vk adalah runtutan simpulsimpul-simpul v1, v2, … vk sedemikian sehingga vi adalah orangtua dari vi+1 untuk 1≤i≤k
Contoh: lintasan dari a ke j, adalah a,b,e,j.
Pohon berakar (terminologi)
Keturunan dan leluhur – Jika terdapat lintasan dari simpul X ke simpul Y di dalam pohon, maka X adalah leluhur simpul Y, dan Y adalah keturunan simpul X. – Contoh: d adalah leluhur simpul m.
10
Pohon berakar (terminologi)
Saudara kandung (sibling) – Simpul yang berorangtua sama adalah saudara kandung satu sama lain. – Contoh: h saudara kandung i, tetapi bukan saudara kandung k.
Pohon berakar (terminologi)
Upapohon (subtree) – Misal X adalah simpul di dalam pohon T. Yang dimaksud upapohon, upapohon, dengan X sebagai akarnya, ialah upagraf T’ T’=(V’ =(V’,E’ ,E’), sedemikian hingga V’ V’ mengandung X dan semua keturunannya dan E’ E’ mengandung sisisisi-sisi dalam semua lintasan yang berasal dari X.
11
Pohon berakar (terminologi)
Upapohon (subtree) – Upapohon T’ T’=(V’ =(V’,E’ ,E’) dengan b sebagai akarnya
Pohon berakar (terminologi)
Derajat (degree) – Derajat sebuah simpul adalah jumlah upapohon (atau jumlah anak) pada simpul tersebut. – Contoh: derajat a adalah 3, derajat b adalah 2, derajat d adalah 1, derajat c adalah 0.
12
Pohon berakar (terminologi)
Daun (leaf) – Simpul yang berderajat nol (tidak mempunyai anak). – Contoh: simpul h,i,j,f,c,l,dan m adalah daun.
Pohon berakar (terminologi)
Simpul dalam (internal nodes) – Adalah simpul yang mempunyai anak. – Contoh: simpul b,d,e,g, dan k adalah simpul dalam.
13
Pohon berakar (terminologi)
Aras (level) atau tingkat – Akar mempunyai aras = 0, sedangkan aras simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut.
Pohon berakar (terminologi)
Tinggi (height) atau kedalaman (depth) – Aras maksimum suatu pohon disebut tinggi atau kedalaman pohon tersebut. – Atau tinggi pohon adalah panjang maksimum lintasan dari akar ke daun.
14
Pohon terurut
Adalah pohon berakar yang urutan anakanak-anaknya penting. Pada pohon terurut, urutan anakanak-anak dari simpul dalam dispesifikasikan dari kiri ke kanan. kanan. – Contoh: (a) urutan anak simpul 1 adalah 2,3,4. – (b) urutan anak simpul 1 adalah 3,4,2.
Pohon m-ary
Adalah pohon berakar yang setiap simpul cabangnya mempunyai paling banyak m buah anak. – m=2 disebut biner, m=3 disebut pohon 33-ary
Pohon m-ary dikatakan teratur atau penuh (full) jika setiap simpul cabangnya mempunyai tepat m anak.
15
Pohon m-ary
Pohon parsing dari kalimat ‘ a tall boy wears a red hat’ hat’
Pohon m-ary
Jumlah daun pada pohon m-ary teratur. – Pada pohon mm-ary teratur dengan tinggi h, jumlah daun adalah mh. – Contoh: pohon 33-ary teratur dengan jumlah daun = 32 = 9
16
Pohon m-ary
Jumlah seluruh simpul pada pohon m-ary teratur dengan tinggi h:
m h +1 − 1 S = m + m + m + .... + m = m −1 0
1
2
h
Pohon m-ary
Hubungan antara jumlah daun simpul dalam pada pohon m-ary teratur :
( m − 1)i = t − 1 – Dimana: m = jumlah anak i = jumlah simpul dalam dengan m anak t = jumlah daun
17
Pohon m-ary
Pohon pertandingan turnamen tenis dengan sistem gugur
Pohon biner
Merupakan kasus khusus pohon m-ary jika m = 2, setiap simpul cabang mempunyai maksimum dua buah anak. Gambar 7.16
18
Pohon biner
Pohon condong kiri, pohon condong kanan.
Pohon biner
Pohon biner penuh.
19
Pohon biner
Pohon biner seimbang – Pada beberapa aplikasi, diinginkan tinggi upapohon kiri dan tinggi upapohon kanan seimbang, yaitu beda maksimal 1. – Untuk menyeimbangkan tinggi keduanya, tingi pohon secara keseluruhan harus dibuat seminimal mungkin. – Untuk memperoleh tinggi minimum, setiap aras harus mengandung jumlah simpul sebanyak mungkin, dengan menyebarkan setengah dari jumlah simpul di upapohon kiri dan setengah dari jumlah simpul di upapohon kanan.
Pohon biner
T1 dan T2 adalah pohon seimbang, sedangkan T3 bukan pohon seimbang.
20
In progress ……….
21
