TREE (POHON)
Pohon ( Tree ) adalah graf tak-berarah terhubung yang tidak mengandung sirkuit.
Keterangan gambar (dari kiri ).
1. Graf Pohon
2. Graf Pohon
3. Graf Tidak Pohon
4. Graf Tidak Pohon
1. Graf Pohon
2. Graf Pohon
3. Graf Tidak Pohon
4. Graf Tidak Pohon
Hutan ( Forest ) adalah kumpulan pohon yang saling lepas, graf yang tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf tersebut adalah pohon.
Sifat-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.
Ciri – ciri hutan :
Banyaknya titik = n
Banyaknya pohon = k
Banyaknya rusuk = n-k
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. Setiap graf terhubung mempunyai paling sedikit satu buah spanning tree. Graf tak-terhubung dengan k komponen mempunyai k buah hutan merentang yang disebut spanning forest.
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.
Ciri – ciri hutan :
Banyaknya titik = n
Banyaknya pohon = k
Banyaknya rusuk = n-k
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. Setiap graf terhubung mempunyai paling sedikit satu buah spanning tree. Graf tak-terhubung dengan k komponen mempunyai k buah hutan merentang yang disebut spanning forest.
Terminilogi pada Pohon Berakar
Child atau children (Anak) dan parent (orangtua)
Path (lintasan)
Descendant (Keturunan) dan ancestor (leluhur)
Sibling (saudara kandung)
Subtree (subpohon)
Degree (derajat)
Leaf (daun)
Internal nodes (simpul dalam)
Level (tingkat)
Height (tinggi) atau depth (kedalaman)
Child atau children (Anak) dan parent (orangtua)
Path (lintasan)
Descendant (Keturunan) dan ancestor (leluhur)
Sibling (saudara kandung)
Subtree (subpohon)
Degree (derajat)
Leaf (daun)
Internal nodes (simpul dalam)
Level (tingkat)
Height (tinggi) atau depth (kedalaman)
Child atau children (Anak) dan parent (orangtua)
Simpul y dikatakan anak simpul x jika ada sisi dari simpul x ke y dan Orangtua dari simpul y adalah simpul x.
Pada gambar G1 :
Simpul b, c dan d adalah anak dari simpul a
Simpul e dan f adalah anak dari simpul b
Simpul a adalah orangtua dari simpul b, c dan d
Simpul b adalah orangtua dari simpul e dan f
Pada gambar G1 :
Simpul b, c dan d adalah anak dari simpul a
Simpul e dan f adalah anak dari simpul b
Simpul a adalah orangtua dari simpul b, c dan d
Simpul b adalah orangtua dari simpul e dan f
Path (lintasan)
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.
Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu k – 1.
Pada gambar G1 :
Lintasan dari a ke j adalah a, b, e dan j
Panjang lintasan dari a ke j adalah 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.
Pada gambar G1 :
Simpul b adalah leluhur dari simpul h
Simpul h adalah keturunan dari simpul b
Sibling (saudara kandung)
Sibling atau saudara kandung adalah simpul yang berorangtua sama
Pada gambar G1 :
Simpul f saudara kandung dari e
Simpul g bukan saudara kandung dari e karena orangtua berbeda
Subtree (subpohon)
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
Pada gambar G2 :
V’ = {b, e, f, h, i, j}
E’ = {(b, e), (b, f), (e, h), (e, i), (e, j)}
B adalah simpul akar
Degree (derajat)
Derajat sebuah simpul pohon berakar adalah jumlah subtree (jumlah anak) pada simpul tersebut. Derajat pohon berakar merupakan derajat keluar
Pada gambar G1 :
Derajat simpul a : 3, simpul b : 2, simpul c : 0 dan simpul d : 1
Derajat tertinggi (maksimum) : 3
Leaf (daun)
Adalah simpul yang berderajat nol (tidak mempunyai anak)
Pada gambar G1 :
Merupakan daun : simpul c, f, h, i, j, l dan m.
Internal nodes (simpul dalam)
Adalah simpul yang mempunyai anak
Pada gambar di samping :
Merupakan simpul dalam : simpul b, d, e, g dan k
Level (tingkat)
Akar mempunyai level = 0
Level simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut (gambar G3).
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.
Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan, yaitu k – 1.
Pada gambar G1 :
Lintasan dari a ke j adalah a, b, e dan j
Panjang lintasan dari a ke j adalah 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.
Pada gambar G1 :
Simpul b adalah leluhur dari simpul h
Simpul h adalah keturunan dari simpul b
Sibling (saudara kandung)
Sibling atau saudara kandung adalah simpul yang berorangtua sama
Pada gambar G1 :
Simpul f saudara kandung dari e
Simpul g bukan saudara kandung dari e karena orangtua berbeda
Subtree (subpohon)
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
Pada gambar G2 :
V’ = {b, e, f, h, i, j}
E’ = {(b, e), (b, f), (e, h), (e, i), (e, j)}
B adalah simpul akar
Degree (derajat)
Derajat sebuah simpul pohon berakar adalah jumlah subtree (jumlah anak) pada simpul tersebut. Derajat pohon berakar merupakan derajat keluar
Pada gambar G1 :
Derajat simpul a : 3, simpul b : 2, simpul c : 0 dan simpul d : 1
Derajat tertinggi (maksimum) : 3
Leaf (daun)
Adalah simpul yang berderajat nol (tidak mempunyai anak)
Pada gambar G1 :
Merupakan daun : simpul c, f, h, i, j, l dan m.
Internal nodes (simpul dalam)
Adalah simpul yang mempunyai anak
Pada gambar di samping :
Merupakan simpul dalam : simpul b, d, e, g dan k
Level (tingkat)
Akar mempunyai level = 0
Level simpul lainnya = 1 + panjang lintasan dari akar ke simpul tersebut (gambar G3).
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
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 urutan anak-anaknya penting. Sistem universal dalam pengalamatan simpul-simpul pada pohon terurut adalah dengan memberi nomor setiap simpulnya seperti penomoran bab (beserta subbab) di dalam sebuah buku.
Adalah pohon berakar yang urutan anak-anaknya penting. Sistem universal dalam pengalamatan simpul-simpul pada pohon terurut adalah dengan memberi nomor setiap simpulnya seperti penomoran bab (beserta subbab) di dalam sebuah buku.
Komentar
Posting Komentar