Pada graf pohon berakar rooted tree yang dimaksud dengan derajat sebuah simpul adalah
Pohon yang satu buah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah sehingga menjadi graf berarah dinamakan pohon berakar (rooted tree).
1. Pohon berakar adalah pohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar. 2. Akar mempunyai derajat masuk nol dan simpul-simpul lainnya berderajat masuk sama dengan satu. 3. Daun atau simpul terminal adalah simpul yang mempunyai derajat keluar sama dengan nol. 4. Simpul dalam atau simpul cabang adalah simpul yang mempunyai derajat keluar tidak sama dengan nol Terminologi pada Pohon Berakar 1. Child atau children (Anak) dan parent (orangtua) 3. Descendant (Keturunan) dan ancestor (leluhur) 4. Sibling (saudara kandung) 8. Internal nodes (simpul dalam) 10. Height (tinggi) atau depth (kedalaman)
1. Child atau children (Anak) dan parent (orangtua)
· 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
Lintasan dari simpul vi ke simpul vk adalah
runtunan simpul-simpul v1, v2 ,…, vk sedemikian
hingga vi adalah orangtua dari vi+1 untuk
1 <= i <= K. · Lintasan dari a ke j adalah a, b, e dan j · Panjang lintasan dari a ke j adalah 3 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. · Simpul b adalah leluhur dari simpul h · Simpul h adalah keturunan dari simpul b 4. Sibling (saudara kandung)
Sibling atau saudara kandung adalah simpul yang berorangtua
sama · Simpul f saudara kandung dari e · Simpul g bukan saudara kandung dari e karena orangtua berbeda
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 · V’ = {b, e, f, h, i, j} · E’ = {(b, e), (b, f), (e, h), (e, i), (e, j)}
Derajat sebuah simpul pohon berakar adalah jumlah subtree
(jumlah anak) pada simpul tersebut. Derajat pohon berakar merupakan derajat
keluar · Derajat simpul a : 3, simpul b : 2, simpul c : 0 dan simpul d : 1 · Derajat tertinggi (maksimum) : 3
Adalah simpul yang berderajat nol (tidak mempunyai
anak) · Merupakan daun : simpul c, f, h, i, j, l dan m. 8. Internal nodes (simpul dalam)
Adalah simpul yang mempunyai anak · Merupakan simpul dalam : simpul b, d, e, g dan k
Akar mempunyai level = 0 10. 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 setiap simpul cabangnya mempunyai banyak n buah anak. Jika m = 2 --> Pohon biner (binary tree).
· Penurunan kalimat (dalam bidang bahasa) · Direktori arsip di dalam komputer · Silsilah keluarga (dalam bidang genetika) · Struktur bab atau daftar isi di dalam buku · Bagan pertandingan antara beberapa tim sepak bola |