MATEMATIKA DISKRITMATERI : POHON M-ARY

NAMA: ALBERT KRISTAENNIM: DBC 113 008

J U R U S A N T E K N I K I N F O R M AT I K AF A K U L T A S T E K N I KU N I V E R S I T A S P A L A N G K A R A Y A2 0 1 4

BAB IPENDAHULUAN

Pohon (tree) adalah Graf tak-berarah terhubung yang tidak mengandung sirkuit.Hutan (forest) adalah Graf tak terhubung yang tidak mengandung sirkuit, dalam hal ini setiap komponen di dalam graf terhubung tersebut adalah pohon.Sifat-sifat Pohon :Misalkan G = (V,E) adalah graf tak-berarah sederhana dan jumlah simpulnya n, maka :1. G adalah pohon2. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal3. G terhubung dan memiliki m = n -1 buah sisi4. G tidak mengandung sirkuit dan memiliki m = n 1 buah sisi5. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit6. G terhubung dan semua sisinya adalah jembatan (jembatan adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen)Jika hutan F dengan k komponen mempunyai m = n 1 buah sisi.Contoh :Sebuah pohon mempunyai 2n buah simpul berderajat 1, 3n buah simpul berderajat 2 dan n buah simpul berderajat 3. Tentukan banyaknya simpul dan sisi di dalam pohon tersebut !Penyelesaian : Berdasarkan jumlah jabat tangan :Jumlah semua simpul di dalam graf adalah 2 kali jumlah sisi di dalam graf tersebut :(2n x 1) + (3n x 2) + (n x 3) = 2 |E|11n = 2 |E| (1)Jumlah sisi pada sebuah pohon adalah jumlah simpul minus satu, sehingga :|E| = (2n + 3n + 1) 1 = 6n 1 (2)Persamaan (1) dan (2) menjadi :11n = 2 (6n 1)11n = 12n 2 n = 2Jadi : Jumlah simpul pada pohon 6n = 6 x 2 = 12 buah simpul Jumlah sisi 6n 1 = 11 buah sisi

BAB IIPEMBAHASAN

Pohon m-aryPohon m-ary adalah Pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak. Jika m = 2 maka pohon disebut pohon biner (binary tree). Pohon m-ary dikatakan pohon penuh (full) atau pohon teratur jika setiap simpul cabangnya mempunyai tepat sama m buah anak. Pohon m-ary banyak digunakan di berbagai bidang ilmu maupun dalam kehidupan sehari-hari. Dalam terapannya, pohon m-ary digunakan sebagai model yang merepresentasikan suatu struktur.Contoh penggunaan pohon m-ary seperti misalnya struktur organisasi, silsilah keluarga (dalam bidang genetika), atau bagan pertandingan antara beberapa tim sepakbola dll.Contoh 1 (Struktur Direktori Dalam Komputer)

Contoh 2 (Struktur Organisasi)

Contoh 3 (Struktur Pertandingan Olahraga)

Jumlah daun pohon m-ary penuhPohon m-ary penuh adalah pohon yang setiap simpulnya tepat mempunyai m anak. Pohon m-ary penuh dengan tinggi h mempunyai jumlah daun mh. Jika sebuah pohon bukan pohon m-ary penuh, maka jumlah daun mh .Pada pohon m-ary penuh dengan tinggi h,aras 0 jumlah simpul = m0 = 1aras 1 jumlah simpul = m1aras 2 jumlah simpul = m2. . . aras h jumlah simpul = mhMaka jumlah seluruh simpul pada pohon m-ary adalah:

Jika T bukan pohon m-ary penuh, maka:

h = 2

m = 3

Pohon 3-ary penuh, dengan jumlah daun mh = 32 = 9 daun.

Pohon BinerPohon biner merupakan pohon m-ary jika nilai dari m 2. Pohon biner selalu terdiri atas dua sub pohon, yakni sub pohon kiri dan sub pohon kanan. Pohon Biner selalu memiliki 0, 1 atau 2 anak, Tak lebih dari itu.Pohon biner adalah pohon yang setiap simpul cabangnya mempunyai paling banyak dua buah anak, yaitu anak kiri (left child) dan anak kanan (right child).Pohon yang akarnya merupakan anak kiri disebut upapohon kiri (left subtree). Sedangkan pohon yang akarnya adalah anak kanan disebut upapohon kanan (right subtree). Karena adanya perbedaan anak/upaohon kiri dan anak/upapohon kanan, maka pohon biner bisa juga disebut sebagai pohon terurut.

Meskipun Telihat sama, dengan nilai pada masing-masing cabang merepresentasikan daun yang sama pula, gambar diatas bukan merupakan dua buah pohon biner yang sama.Pohon yang semua simpulnya terletak di bagian kiri saja atau di bagian kanan saja disebut pohon condong (skewed tree). Pohon yang condong ke kiri disebut pohon condong-kiri (skew left). Pohon yang condong ke kanan disebut pohon condong-kanan (skew left).Pohon Condong Kanan

Pohon Condong Kiri

Pohon Binary PenuhPohon Binary Penuh adalah pohon biner yang setiap simpulnya mempunyai tepat dua anak, kiri dan kanan, kecuali simpul pada aras bawah. Pohon biner penuh dengan tinggi h memiliki jumlah daun sebanyak 2h, sedangkan jumlah simpulnya adalah :

Gambar diatas merupakan Pohon Biner Penuh.Pohon biner seimbang (balanced binary tree)Pohon biner seimbang adalah pohon biner yang setiap daunnya mempunyai aras (level) h atau h 1.T1 T2 T2

T1 adalah pohon biner seimbang, karena seluruh daunnya berada pada level 3 dan 4. T2 adalah pohon biner tak seimbang, karena daun-daunnya berada pada level 2, 3, dan 4. Sedangka T3 seimbang, karena seluruh daunnya berada pada level 3.Mengubah pohon umum menjadi Pohon BinerLKJIHGFEDCBA

Contoh diatas merupakan pohon umum dan bukanlah pohon biner, karena salah pada simpul D mempunyai 3 anak, yaitu H, I dan J. Algoritma yang digunakan untuk menjadikan pohon umum kedalam bentuk pohon biner terdiri dari dua langkah, yaitu :1. Tambahkan ruas (edge) baru yang mehubungkan 2 simpul bersaudara yang berdampingan, lalu hapus ruas dari simpul orangtua (parent) sebagai kesimpulan anak bersaudara tersebut, kecuali simpul anak paling kiri. Hasil :

2. Lalu rotasi sebesar 45o, searah jalannya putaran jarum jam dari pohon hasil langkah pertama.Hasil: LJIHKGDFCBEA

Daftar PustakaCatatan Materi Pelajaran : Matematika Diskrit. 2014.Adiwijaya. Bab V : Pohon (Tree). Sekolah Tinggi Telkom. 2010.Slide Materi Matematika Diskrit. 2014. Sumber : Grup TIUP.