Teori Pohon “Begin at the beginning … and go on /ll you come to the end: then stop.” – Lewis Caroll, Alice’s Adventures in Wonderland, 1865
Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
1
Pohon Suatu graf tak berarah terhubung yang Hdak memiliki sirkuit (atau beberapa referensi menyebut dengan terminologi sirkuit sederhana), disebut sebagai pohon. NB: Mengenai isHlah sirkuit, terdapat perbedaan terminologi pada beberapa buku referensi. Jika terdapat suatu lintasan pada graf dengan simpul awal dan simpul akhir yang sama, kemudian Hdak ada sisi yang dilalui lebih dari satu kali, maka beberapa referensi menyebutnya sebagai sirkuit, sedangkan referensi lain menyebutnya sebagai sirkuit sederhana. Bagi referensi yang menggunakan terminologi sirkuit sederhana, maka terminologi sirkuit merujuk pada lintasan dengan simpul awal dan akhir yang sama. Sehingga pada referensi tersebut, suatu sirkuit dapat melalui sisi lebih dari satu kali. Matema(ka Komputasi -‐ Teori Pohon 2 Agi Putra Kharisma, ST., MT.
Hutan Suatu graf disebut hutan jika tak berarah, tak terhubung, dan Hdak memiliki sirkuit (sirkuit sederhana).
Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
3
Pohon Pohon Bukan Pohon Hutan
Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
4
KarakterisHk Pohon 1. Suatu pohon yang memiliki lebih dari satu simpul, memiliki minimal dua buah simpul berderajat 1. 2. Simpul berderajat 1 disebut daun (atau simpul terminal). 3. Simpul berderajat > 1 disebut cabang (atau simpul internal). 4. Untuk suatu bilangan bulat posiHf n, suatu pohon dengan n simpul memiliki (n – 1) sisi. Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
5
Pohon Berakar 1. Orang tua dari b adalah a 2. Anak dari b adalah e,f 3. Keturunan dari b adalah e,f,h,i,j 4. Saudara dari b adalah c,d 5. a terletak pada level 0 6. b terletak pada level 1 7. h terletak pada level 3 8. Pohon disamping memiliki keHnggian/kedalaman 3
Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
6
Sub Pohon
Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
7
Pohon Biner Pohon berakar yang urutan anak-‐anaknya penHng (diperhaHkan) maka pohon yang demikian dinamakan pohon terurut (ordered tree). Sedangkan pohon berakar yang seHap simpul cabangnya mempunyai paling banyak n buah anak disebut pohon n-‐ary. Jika n = 2, pohonnya disebut pohon biner (binary tree). Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
8
Pohon Merentang (Spanning Tree) Pohon merentang untuk suatu graf G adalah subgraf dari G yang berupa pohon yang memuat semua simpul G.
Pohon merentang graf di atas adalah sebagai berikut: (Sumber: Susanna S.Epp)
Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
9
Pohon Merentang Minimum Graf berbobot adalah graf dimana seHap sisi diasosiasikan dengan bilangan riil posiHf sebagai bobotnya. Jumlah bobot pada semua sisi adalah bobot total suatu graf.
Pohon merentang minimum adalah pohon merentang dengan kemungkinan bobot terkecil dibanding pohon merentang lainnya dari suatu graf terhubung.
Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
10
Algoritma Prim
Sumber: Susanna S. Epp – Discrete Mathema/cs with Applica/ons 4th Ed. Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
11
Algoritma Kruskal
Sumber: Susanna S. Epp – Discrete Mathema/cs with Applica/ons 4th Ed. Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
12
Sumber: Susanna S. Epp – Discrete Mathema/cs with Applica/ons 4th Ed. Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
13
Sumber: Kenneth H. Rosen – Discrete Mathema/cs and Its Applica/ons, 7th Ed Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
14
Referensi Susanna S .Epp. Discrete Mathema-cs with Applica-ons 4th Ed. Kenneth H. Rosen. Discrete Mathema-cs and Its Applica-ons 7th Ed. Rinaldi Munir. Matema-ka Diskrit edisi ke-ga. Matema(ka Komputasi -‐ Teori Pohon Agi Putra Kharisma, ST., MT.
15
