graf pohon

Click here to load reader

Upload: septi-ratnasari

Post on 25-May-2015

1.001 views

Category:

Education


13 download

DESCRIPTION

Graf Pohon (Matematika Diskrit)

TRANSCRIPT

  • 1. Graf Pohon Septi Ratnasari 4101412082 By Matematika Diskrit Mathematics Department

2. Definisi 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. 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. Matematika Diskrit 3. G 1 G 2 G 3 G 4 a b c d e f a b c d e f a b c d e f a b c d e f Matematika Diskrit 4. Hutan (forest) adalah merupakan kumpulan pohon yang saling lepas. graf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebut adalah pohon. Matematika Diskrit Hutan yang terdiri dari tiga buah pohon 5. Sifat-sifat Pohon Matematika Diskrit 6. Pohon Merentang (spanning tree) Spanning tree dari suatu graf terhubung merupakan subgraf merentang yang berupa pohon. Pohon merentang diperoleh dengan cara menghilangkan sirkuit dalam graf tersebut. Matematika Diskrit 7. G T1 T2 T3 T4 Matematika Diskrit T1, T2, T3, T4 merupakan spanning tree dari graf G. Setiap graf terhubung mempunyai paling sedikit mempunyai satu buah spanning tree. 8. Aplikasi Pohon Merentang 1. Jumlah ruas jalan seminimum mungkin yang menghubungkan semua kota sehingga setiap kota tetap terhubung satu sama lain. 2. Perutean (routing) pesan pada jaringan komputer. Matematika Diskrit (a) (b) Router Subnetwork (a)Jaringan komputer, (b) Pohon merentang multicast 9. Pohon Merentang Minimum Pohon rentang yang mempunyai bobot minimum dinamakan pohon merentang minimum (minimum spanning tree). Dalam menentukan minimum spanning tree dari suatu graf terhubung, kita dapat menggunakan dua cara yaitu Algoritma Prim dan Algoritma Kruskal. Matematika Diskrit 10. Algoritma Prim Langkah-langkah Algoritma Prim : 1. Pilih sisi dari graf G yang berbobot minimum, masukkan ke dalm T. 2. Pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian dengan simpul di T, dengan syarat sisi tersebut tidak membentuk sirkuit di T. Masukkan (u, v) ke dalam T. 3. Ulangi langkah 2 sebanyak n-2 kali. Matematika Diskrit 11. Contoh : Tentukan minimum spanning tree graf berikut : Matematika Diskrit 12. Penyelesaian Matematika Diskrit 1. Pilih sisi fg sehingga kita mempunyai T({f, g}, fg) 2. Pilih sisi ef karena sisi tersebut berbobot minimum yang bersisian dengan simpul f. 3. Pilih sisi ae dan gh karena berbobot minimum yang bersisian dengan simpul pada T, yaitu e dan g. 4. Pilih sisi ac dan ad karena berbobot minimum yang bersisian dengan simpul a. 5. Pilih sisi bc yang bersisian dengan simpul c. Spanning tree tersebut mempunyai total bobot 2+3+4+4+4+4+3=24 13. Algoritma Kruskal Pada Algoritma Kruskal, semua sisi dengan bobot yang minimum dimasukkan ke dalam T secara berurutan. Matematika Diskrit 14. Penyelesaian 1.T masih kosong 2. Pilih fg yang berbobot minimum yang tidak membentuk sirkuit di T. 3. Memasukkan sisi yang berbobot 3, sehingga T berbentuk Matematika Diskrit 15. 4. Memasukkan sisi-sisi yang berbobot 4, sehingga T berbentuk Matematika Diskrit Spanning tree tersebut mempunyai total bobot 2+3+4+4+4+4+3=24 16. Pohon Berakar (rooted tree) Pada suatu pohon yang sisi-sisinya diberi arah sehingga menyarupai graf berarah, maka simpul yang terhubung dengan semua simpul pada pohon dinamakan akar. Pohon yang satu buah simpulnya diperlakukan sebagai akar maka pohon tersebut dinamakan pohon berakar (rooted tree). Matematika Diskrit 17. Contoh : Pohon Berakar (Munir, 2003) Matematika Diskrit (a) Pohon berakar (b) Pohon berakar setelah tanda panah pada sisi dibuang a b c d e f g h i j a b c d e f g h i j Pada pohon berakar di atas: a merupakan akar c, d, f, g, h, i, dan j merupakan daun 18. b sebagai akar e sebagai akar Pohon dan dua buah pohon berakar yang dihasilkan dari pemilihan dua simpul berbeda sebagai akar a b c d e f g h f g a b c d e f g h d e h b a c Matematika Diskrit 19. Terminologi pada Pohon Berakar 1. Anak (child atau children) dan Orangtua (parent) b, c, dan d adalah anak-anak simpul a, dan a adalah orangtua dari anak-anak itu. Matematika Diskrit a b k g j f c d ml i e h 20. 2. Lintasan (path) Lintasan dari a ke h adalah a, b, e, h dengan panjang lintasan adalah 3. 3. Saudara Kandung (sibling) f adalah saudara kandung e, tetapi g bukan saudara kandung e karena orangtua mereka berbeda. Matematika Diskrit a b k g j f c d ml i e h 21. 4. Subpohon (subtree) Matematika Diskrit a b k g j f c d ml i e h 22. 5. Derajat (degree) Derajat sebuah simpul adalah jumlah anak pada simpul tersebut. Contoh: Simpul berderajat nol adalah simpul c, f, h, i, j, l, m. Simpul berderajat 1 adalah simpul d dan g. Simpul berderajat 2 adalah simpul b dan k. Simpul berderajat 3 adalah simpul a dan e. Jadi, derajat yang dimaksud adalah derajat keluar. Derajat maksimum dari semua simpul merupakan derajat pohon itu sendiri. Pohon di samping berderajat 3. Matematika Diskrit a b k g j f c d ml i e h 23. 6. Daun (leaf) Simpul yang berderajat nol (tidak mempunyai anak) disebut daun. Simpul h, i, j, f, c, l, dan m adalah daun. 7. Simpul Dalam (internal node) Simpul yang mrmpunyai anak adalah simpul dalam. Simpul b, d, e, g, dan k adalah simpul dalam Matematika Diskrit a b k g j f c d ml i e h 24. 8. Aras (level) atau Tingkat 9. Tinggi (height) atau Kedalaman (depth) Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon tersebut. Pohon di atas mempunyai tinggi 4. Matematika Diskrit a b k g j f c d ml i e h 0 1 2 3 4 Aras 25. Pohon Terurut (ordered tree) Pohon berakar yang urutan anak-anaknya (diperhatikan), maka dinamakan pohon terurut (ordered tree). Matematika Diskrit (a) (b) (a) dan (b) adalah dua pohon terurut yang berbeda 1 2 6 87 3 4 9 10 5 1 2 68 7 3 4 9 10 5 26. Pohon n-ary Pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak disebut pohon n-ary. Pohon n-ary dikatakan teratur atau penuh (full jika setiap simpul cabangnya mempunyai tepat n anak. Matematika Diskrit Contoh: < sentence> wears A a tall boy red hat Gambar Pohon parsing dari kalimat A tall boy wears a red hat 27. Pohon Biner (binary tree) Pohon n-ary dengan n = 2 Pohon yang paling penting karena banyak aplikasinya Setiap simpul dalam pohon biner mempunyai paling banyak 2 buah anak Dibedakan antara anak kiri (left child) dan anak kanan (right child) Ada berbedaan urutan anak, maka pohon biner adalah pohon terurut Matematika Diskrit 28. Contoh: Matematika Diskrit a b c d a b c d Dua buah pohon biner yang berbeda 29. Gambar Pohon biner penuh Matematika Diskrit Gambar (a) Pohon condong-kiri, dan (b) pohon condong kanan a b c d a b c d (a) (b) 30. Pohon Biner Seimbang Pohon biner yang tinggi subpohon kiri dan tinggi subpohon kanan seimbang, yaitu berbeda maksimal 1. Matematika Diskrit T1 T2 T3 Gambar T1 dan T2 adalah pohon seimbang, sedangkan T3 bukan pohon seimbang. 31. Terapan Pohon Biner 1. Pohon Ekspresi Ekspresi aritmatika (a+b)*((c/(d+e) dapat dinyatakan dalam suatu pohon biner, dimana peubah sebagai daun dan operator aritmatika sebagai simpul dalam dan akar. Matematika Diskrit Gambar Pohon ekspresi dari (a + b)*(c/(d + e)) * + / a b + d e c 32. 2. Pohon Keputusan Matematika Diskrit a : b a : c b : c b : c c > a > b a : c c > b > a a > b > c a > c > b b > a > c b > c > a a > b b > a a >c c > a b > c c > b b > c c > b a >c c > a Gambar Pohon keputusan untuk mengurutkan 3 buah elemen 33. 3. Kode Awalan (prefix code) Kode awalan merupakan himpunan kode (salah satunya adalah kode biner) sedemikian sehingga tidak ada anggota himpunan yang merupakan awalan dari kode yang lain. Contoh: a. {000, 010, 011, 11} merupakan kode awalan. b. {001, 010, 01, 111} bukan merupakan kode awalan, karena 01 merupakan awalan dari 010. Matematika Diskrit 34. 4. Kode Huffman Kode Huffman merupakan salah satu metode pengkodean dalam hal kompresi data. Matematika Diskrit Perhatikan Tabel Kode ASCII berikut: Simbol Kode ASCII A 01000001 B 01000010 C 01000011 D 01000100 Jadi rangkaian bit untuk string ABACCDA: 01000001010000010010000010100000110100000110100010001000001 atau 7 8 = 56 bit (7 bytes). 35. Tabel kekerapan (frekuensi) dan kode Huffman untuk string ABACCDA Matematika Diskrit Simbol Kekerapan Peluang Kode Huffman A 3 3/7 0 B 1 1/7 110 C 2 2/7 10 D 1 1/7 111 Sehingga rangkaian bit untuk string ABACCDA : 0110010101110 atau 13 bit 36. Algoritma Pembentukan kode Huffman 1. Pilih dua simbol dengan peluang (probability) paling kecil (pada contoh di atas yaitu simbol B dan D). Kedua simbol tadi dikombinasikan sebagai simpul orangtua dari simbol B dan D, sehingga menjadi simbol BD dengan peluang 1/7 + 1/7 = 2/7, yaitu jumlah peluang kedua anaknya. 2. Pilih dua simbol berikutnya, termasuk simbol baru, yang mempunyai peluang terkecil. 3. Ulangi langkah 1 dan 2 sampai seluruh simbol habis Matematika Diskrit 37. Matematika Diskrit A = 0, C = 10, B = 110, D =111 38. Pohon Pencarian Biner Matematika Diskrit kunci S < kunci A Kunci T > Kunci A Contoh: Data 50, 32, 18, 40, 60, 52, 5, 25, 70 39. Penelusuran Pohon Biner Berikut ini pohon biner dimana A merupakan akar pohon biner, sementara S dan T merupakan subpohon (subtree) dari pohon biner. Matematika Diskrit 40. Ada 3 jenis penelusuran pohon biner di atas, antara lain: 1. Preorder : A, S, T - kunjungi A - kunjungi S secara preorder - kunjungi T secara preorder 2. Inorder : S, A, T - kunjungi S secara inorder - kunjungi A - kunjungi T secara inorder 3. Postorder : S, T, A - kunjungi S secara postorder - kunjungi T secara postorder - kunjungi A Matematika Diskrit 41. Contoh: Tentukan hasil penelusuran preorder, inorder, dan postorder dari pohon biner berikut: Matematika Diskrit Jawab Preorder : * + a / b c d * e f Inorder : a + b / c * d e * f Postorder : a b c / + d e f * - *