P O H O N ( T R E E )
Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang menghubungkan pasangan simpul tersebut. Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon (tree). Dengan kata lain, pohon (tree) merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit.
Hutan (forest) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon. Pada gambar 6. 1 G4 merupakan salah satu contoh hutan, yaitu hutan yang terdiri dari dua pohon.
Berikut adalah beberapa sifat pohon :
1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi. Jika G tidak mempunyai sirkuit maka G merupakan pohon.
2. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.
Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.Misalkan G 3.adalah graf sederhana dengan jumlah simpul n, jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit.
Contoh :
Tentukan minimum spanning tree dari graf dibawah ini :
Berikut adalah beberapa sifat pohon :
1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi. Jika G tidak mempunyai sirkuit maka G merupakan pohon.
2. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.
Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.Misalkan G 3.adalah graf sederhana dengan jumlah simpul n, jika G tidak mengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuat satu sirkuit.
Contoh :
Tentukan minimum spanning tree dari graf dibawah ini :
Jawab :
• Pilih sisi fg sehingga kita mempunyai T ({f, g}, fg)
• Langkah selanjutnya dapat dipilih sisi ef karena sisi tersebut berbobot minimum yang bersisian dengan simpul f .
• Selanjutnya pilih sisi ae atau gh karena sisi tersebut berbobot minimum yang bersisian dengan simpul pada T, yaitu e dan g.
Jika proses ini dilanjutkan terus maka akan diperoleh minimum spanning tree seperti dibawah ini :
• Pilih sisi fg sehingga kita mempunyai T ({f, g}, fg)
• Langkah selanjutnya dapat dipilih sisi ef karena sisi tersebut berbobot minimum yang bersisian dengan simpul f .
• Selanjutnya pilih sisi ae atau gh karena sisi tersebut berbobot minimum yang bersisian dengan simpul pada T, yaitu e dan g.
Jika proses ini dilanjutkan terus maka akan diperoleh minimum spanning tree seperti dibawah ini :
Terlihat bahwa spanning tree tersebut mempunyai total bobot 2 + 3 + 4 + 4 + 4 + 4 + 3 = 24.
Langkah-langkah dalam algoritma Kruskal agak berbeda dengan algoritma Prim. Pada algoritma Kruskal, semua sisi dengan bobot yang minimal dimasukan kedalam T secara berurutan.
Pohon Berakar
Pada suatu pohon, yang sisi-sisinya diberi arah sehingga menyerupai graf berarah, maka simpul yang terhubung dengan semua simpul pada pohon tersebut dinamakan akar. Suatu pohon yang satu buah simpulnya diperlakukan sebagai akar maka pohon tersebut dinamakan pohon berakar (rooted tree). Simpul yang berlaku sebagai akar mempunyai derajat masuk sama dengan nol. Sementara itu, simpul yang lain pada pohon itu memiliki derajat masuk sama dengan satu. Pada suatu pohon berakar, Simpul yang memiliki derajat keluar sama dengan nol dinamakan daun.
Pada pohon berakar diatas :
• a merupakan akar
• c, d, f, g, h, i, dan j merupakan daun
Terminologi pada Pohon Berakar.
a. Anak (child atau children) dan Orangtua (parent)
b, c, dan d adalah anak-anak simpul a,
a adalah orangtua dari anak-anak itu
b. Lintasan (path)
Lintasan dari a ke h adalah a, b, e, h. dengan pnjang lintasannya adalah 3.
f adalah saudara kandung e, tetapi, g bukan saudara kandung e, karena orangtua mereka berbeda.
c. Derajat (degree)
Derajat sebuah simpul adalah jumlah anak pada simpul tersebut.
Contoh :
Simpul yang berderajat 0 adalah simpul c, f, h, I, j, l, dan m.
Simpul yang berderajat 1 adalah simpul d dan g.
Simpul yang berderajat 2 adalah simpul b dan k.
Simpul yang berderajat 3 adalah simpul a dan e.
Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar.
Derajat maksimum dari semua simpul merupakan derajat pohon itu sendiri. Pohon di atas berderajat 3
d. Daun (leaf)
Simpul yang berderajat nol (atau tidak mempunyai anak) disebut daun. Simpul h, i, j, f, c, l, dan m adalah daun.
e. Simpul Dalam (internal nodes)
Simpul yang mempunyai anak disebut simpul dalam. Simpul b, d, e, g, dan k adalah simpul dalam.
f. Aras (level) atau Tingkat
g. Tinggi (height) atau Kedalaman (depth)
Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon tersebut. Pohon di atas mempunyai tinggi 4.
Pohon berakar yang urutan anak-anaknya penting (diperhatiakn) maka pohion yang demikian dinamakan pohon terurut (ordered tree). Sedangka, pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak disebut pohon n-ary. Jika n = 2, pohonnnya disebut pohon biner (binary tree).
2. Pohon keputusan
Langkah-langkah dalam algoritma Kruskal agak berbeda dengan algoritma Prim. Pada algoritma Kruskal, semua sisi dengan bobot yang minimal dimasukan kedalam T secara berurutan.
Pohon Berakar
Pada suatu pohon, yang sisi-sisinya diberi arah sehingga menyerupai graf berarah, maka simpul yang terhubung dengan semua simpul pada pohon tersebut dinamakan akar. Suatu pohon yang satu buah simpulnya diperlakukan sebagai akar maka pohon tersebut dinamakan pohon berakar (rooted tree). Simpul yang berlaku sebagai akar mempunyai derajat masuk sama dengan nol. Sementara itu, simpul yang lain pada pohon itu memiliki derajat masuk sama dengan satu. Pada suatu pohon berakar, Simpul yang memiliki derajat keluar sama dengan nol dinamakan daun.
Pada pohon berakar diatas :
• a merupakan akar
• c, d, f, g, h, i, dan j merupakan daun
Terminologi pada Pohon Berakar.
a. Anak (child atau children) dan Orangtua (parent)
b, c, dan d adalah anak-anak simpul a,
a adalah orangtua dari anak-anak itu
b. Lintasan (path)
Lintasan dari a ke h adalah a, b, e, h. dengan pnjang lintasannya adalah 3.
f adalah saudara kandung e, tetapi, g bukan saudara kandung e, karena orangtua mereka berbeda.
c. Derajat (degree)
Derajat sebuah simpul adalah jumlah anak pada simpul tersebut.
Contoh :
Simpul yang berderajat 0 adalah simpul c, f, h, I, j, l, dan m.
Simpul yang berderajat 1 adalah simpul d dan g.
Simpul yang berderajat 2 adalah simpul b dan k.
Simpul yang berderajat 3 adalah simpul a dan e.
Jadi, derajat yang dimaksudkan di sini adalah derajat-keluar.
Derajat maksimum dari semua simpul merupakan derajat pohon itu sendiri. Pohon di atas berderajat 3
d. Daun (leaf)
Simpul yang berderajat nol (atau tidak mempunyai anak) disebut daun. Simpul h, i, j, f, c, l, dan m adalah daun.
e. Simpul Dalam (internal nodes)
Simpul yang mempunyai anak disebut simpul dalam. Simpul b, d, e, g, dan k adalah simpul dalam.
f. Aras (level) atau Tingkat
g. Tinggi (height) atau Kedalaman (depth)
Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon tersebut. Pohon di atas mempunyai tinggi 4.
Pohon berakar yang urutan anak-anaknya penting (diperhatiakn) maka pohion yang demikian dinamakan pohon terurut (ordered tree). Sedangka, pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak disebut pohon n-ary. Jika n = 2, pohonnnya disebut pohon biner (binary tree).
2. Pohon keputusan
Tidak ada komentar:
Posting Komentar