Diagram Pohon
(Tree Diagram)
Matematika Diskrit
Pengenalan Tree Diagram
Diagram pohon (tree) adalah sebuah graf tak berarah yang
terhubung (connected), yang tidak mengandung sirkuit sederhana,
tidak ada loop, dan tidak terdapat garis parallel.
Tree Non-Tree
Istilah-Istilah dalam Tree
1. Pohon Semu (Trivial Tree) : tree yang hanya terdiri dari
sebuah titik
2. Pohon Kosong (Empty Tree) : tree yang tidak mempunyai
titik
3. Hutan (Forest) : Kumpulan tree yang tidak memuat sirkuit
dan tidak saling berhubungan antar tree-nya.
4. Daun (leaf / terminal vertex) : titik dalam tree yang
berderajat 1
5. Titik cabang (Branch / Internal Vertex) : titik dalam tree
yang berderajat > 1
Contoh Soal 1
Tentukan leaf dan branch pada gambar di atas!
Jawab :
Leaf v4, v5, v6, v7, v8
Branch v1, v2, v3
∞ Akar (Root) : titik yang dikhususkan dari titik yang lainnya atau
parent tertinggi
∞ Tingkat (Level) titik : banyaknya garis antara titik tersebut
dengan akar
∞ Tinggi (Height) tree : tingkat maksimum yang dimiliki oleh
titik-titik tree
∞ Anak (Children) dari titik v : semua titik yang berhubungan
langsung dengan v, tetapi mempunyai tingkat yang lebih tinggi
dari v.
∞ Orang tua (Parent) : jika w anak dari v, maka v adalah parent
dari w
∞ Saudara (Sibling) : titik-titik dengan parent yang sama
Contoh Soal 2
Dari tree di atas, tentukan :
a) Tingkat tiap titik!
b) Tinggi tree!
c) Children, Parent, dan Sibling titik v4!
∞ Ancestors : titik-titik pada lintasan dari root ke titik tersebut, di luar
titik itu sendiri dan termasuk root
∞ Descendants titik v : titik-titik dengan v sebagai ancestors-nya
∞ Contoh soal 3 :
∞ Tentukan Parent c, Children g, Sibling h, Ancestors e,
descendants b, leaf, branch, dan tinggi tree!
Binary Tree
Pohon Biner (Binary Tree) adalah tree yang setiap titiknya
mempunyai paling banyak 2 anak, yaitu Anak Kiri (Left Child) dan Anak
Kanan (Right Child).
Kegunaan Binary Tree :
- Sorting
- Searching
Binary Tree Non-Binary Tree
Full Binary Tree
Pohon Biner Penuh (Full Binary Tree) adalah binary tree yang setiap
titiknya (kecuali leaf) mempunyai tepat 2 anak.
Tingkat 1
Tingkat 2
….
….
….
Tingkat k
Catatan :
Jika Tree terdapat 2k+1 – 1 buah vertex, maka mempunyai 2k+1 -
2 buah garis
Jika Tree terdapat n vertex, maka memiliki n - 1 garis (Full
Binary Tree)
Untuk Tree Full m-ary :
Jika terdapat i branch , maka mempunyai :
n = mi + 1 vertex
L = (m – 1) i + 1 leaf
Jika terdapat n vertex, maka mempunyai :
i = (n – 1) / m branch
L = [(m – 1) n + 1] / m leaf
Contoh Soal 4
1) Berapa jumlah leaf dari tree full 3-ary yang
memiliki 100 vertex?
2) Nyatakan ekspresi aljabar berikut ini ke dalam
binary tree :
a) (x / y) + z
b) (x – y) z + (u / v)
Sub-Tree
Sub-tree dibagi 2 :
1. Left Sub-Tree adalah binary tree yang :
∞ Titik-titiknya adalah anak kiri dan semua turunannya
∞ Garis-garisnya adalah garis-garis dalam yang
menghubungkan titik-titik sub-tree kiri
∞ akarnya adalah anak kiri tersebut
2. Right Sub-Tree didefinisikan secara analog
Struktur Sub-Tree
Contoh Soal 5
Tentukan dari ketiga tree berikut ini, manakah tree yang
balance?
Minimum Spanning Tree (MST)
MST merupakan suatu tree yang dibentuk dari sebuah graph
untuk menentukan jumlah bobot terkecil (minimum) semua garis yang
berhubungan.
Contoh :
Untuk membentuk tree dari suatu graph, beberapa garis dapat
dihilangkan dengan memilih bobot terkecil diantaranya.
Syaratnya :
- Jumlah garis harus : (n - 1)
dimana n = total vertex
- setiap vertex nya terhubung atau tidak ada titik yang terisolasi
Contoh :
Selesai…