p o h o npancamr.lecture.ub.ac.id/files/2012/03/p-o-h-o-nhandout.pdfgraf lengkap g dan empat buah...

1

P o h o nP o h o n

Oleh:Oleh:Panca Mudji RahardjoPanca Mudji Rahardjo

DefinisiDefinisi

PohonPohon–– Adalah graf tak berarah terhubung yang tidak Adalah graf tak berarah terhubung yang tidak

mengandung sirkuit.mengandung sirkuit.Contoh: GContoh: G11 dan Gdan G22 pohon, Gpohon, G33 dan Gdan G44 bukan pohon.bukan pohon.

2

DefinisiDefinisi

Hutan (forest)Hutan (forest)–– Adalah kumpulan pohon yang saling lepas.Adalah kumpulan pohon yang saling lepas.

Contoh: hutan yang terdiri dari 3 pohonContoh: hutan yang terdiri dari 3 pohon

SifatSifat--sifat pohonsifat pohon

Misalkan T=(V,E) adalah graf takMisalkan T=(V,E) adalah graf tak--berarah sederhana dan berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan dibawah ini jumlah simpulnya n. Maka, semua pernyataan dibawah ini adalah ekivalen:adalah ekivalen:–– T adalah pohon,T adalah pohon,–– Setiap pasang simpul di dalam T terhubung dengan lintasan Setiap pasang simpul di dalam T terhubung dengan lintasan

tunggal,tunggal,–– T terhubung dan memiliki m = n T terhubung dan memiliki m = n –– 1 buah sisi,1 buah sisi,–– T tidak mengandung sirkuit dan memiliki m = n T tidak mengandung sirkuit dan memiliki m = n –– 1 buah sisi,1 buah sisi,–– T tidak mengandung sirkuit dan penambahan satu sisi pada graf T tidak mengandung sirkuit dan penambahan satu sisi pada graf

akan membuat hanya satu sirkuit,akan membuat hanya satu sirkuit,–– T terhubung dan semua sisinya adalah jembatan (jembatan T terhubung dan semua sisinya adalah jembatan (jembatan

adalah sisi yang bila dihapus menyebabkan graf terpecah adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen).menjadi dua komponen).

3

Pohon rentangPohon rentang

Misalkan G = (V,E) adalah graf tak berarah Misalkan G = (V,E) adalah graf tak berarah terhubung yang bukan pohon, yang berarti terhubung yang bukan pohon, yang berarti G terdapat beberapa sirkuit.G terdapat beberapa sirkuit.G dapat diubah menjadi pohon T = (VG dapat diubah menjadi pohon T = (V11,E,E11) ) dengan cara memutuskan sirkuit yang ada.dengan cara memutuskan sirkuit yang ada.T disebut T disebut pohonpohon rentangrentang G bila VG bila V11 = V dan = V dan EE11 ⊂⊂ E. E. Pohon rentang adalah upagraf rentang yang Pohon rentang adalah upagraf rentang yang berupa pohon dari graf terhubung.berupa pohon dari graf terhubung.


Graf lengkap G dan empat buah pohon rentangnya, TGraf lengkap G dan empat buah pohon rentangnya, T11, T, T22, T, T33dan Tdan T44

4


Cabang (branch)Cabang (branch)–– Adalah Adalah sisi pohon rentangsisi pohon rentang, yaitu sisi dari graf , yaitu sisi dari graf

semula.semula.

TaliTali--hubung (chord atau link)hubung (chord atau link)–– Adalah sisi dari graf yang Adalah sisi dari graf yang tidak terdapattidak terdapat di dalam di dalam

pohon rentang.pohon rentang.

Komplemen pohonKomplemen pohon–– Adalah himpunan taliAdalah himpunan tali--hubung beserta simpul hubung beserta simpul

yang bersisian dengannya.yang bersisian dengannya.


Untuk graf Untuk graf terhubungterhubung G dengan n buah G dengan n buah simpul dan m buah sisi:simpul dan m buah sisi:–– Jumlah cabang = n Jumlah cabang = n –– 11–– Jumlah taliJumlah tali--hubung = mhubung = m--n+1n+1

Untuk graf Untuk graf taktak terhubungterhubung dengan k dengan k komponen, m buah sisi dan n buah simpul:komponen, m buah sisi dan n buah simpul:–– Jumlah cabang = n Jumlah cabang = n –– kk–– Jumlah taliJumlah tali--hubung = m hubung = m –– n + kn + k

5


Rank graf GRank graf G–– Adalah jumlah Adalah jumlah cabangcabang pada pohon rentang dari pada pohon rentang dari

sebuah graf Gsebuah graf G

Nullity graf GNullity graf G–– Adalah jumlah Adalah jumlah talitali--hubunghubung pada graf G.pada graf G.

Rank + nullity = jumlah sisi graf GRank + nullity = jumlah sisi graf GFundamental circuitFundamental circuit–– Adalah sirkuit yang terbentuk dengan penamAdalah sirkuit yang terbentuk dengan penam--

bahan sebuah talibahan sebuah tali--hubung pada pohon rentanghubung pada pohon rentang

Pohon rentang minimumPohon rentang minimum

Jika G adalah graf berbobot, maka bobot Jika G adalah graf berbobot, maka bobot pohon rentang T dari G didefinisikan pohon rentang T dari G didefinisikan sebagai jumlah bobot semua sisi di T.sebagai jumlah bobot semua sisi di T.Di antara semua pohon rentang di G, pohon Di antara semua pohon rentang di G, pohon rentang yang berbobot minimum, disebut rentang yang berbobot minimum, disebut pohonpohon rentangrentang minimumminimum..Terdapat dua buah algoritma:Terdapat dua buah algoritma:–– Algoritma Prim,Algoritma Prim,–– Algoritma Kruskal.Algoritma Kruskal.

6

Pohon rentang minimumPohon rentang minimum

(a)(a) Graf yang menyatakan jaringan jalur kereta api. Bobot pada Graf yang menyatakan jaringan jalur kereta api. Bobot pada tiap sisi menyatakan panjang rel kereta api (x 100 km)tiap sisi menyatakan panjang rel kereta api (x 100 km)

(b)(b) Pohon rentang yang mempunyai jumlah jarak minimumPohon rentang yang mempunyai jumlah jarak minimum

Algoritma PrimAlgoritma Prim

Langkah 1:Langkah 1:–– Ambil sisi dari graf G yang Ambil sisi dari graf G yang berbobotberbobot minimumminimum, ,

masukkan ke dalam T.masukkan ke dalam T.

Langkah 2:Langkah 2:–– Pilih sisi (u,v) yang mempunyai bobot minimum Pilih sisi (u,v) yang mempunyai bobot minimum

dan bersisian dengan simpul di T, tetapi (u,v) dan bersisian dengan simpul di T, tetapi (u,v) tidaktidak membentukmembentuk sirkuitsirkuit di T. Tambahkan (u,v) di T. Tambahkan (u,v) ke dalam T.ke dalam T.

Langkah 3:Langkah 3:–– Ulangi langkah 2 sebanyak nUlangi langkah 2 sebanyak n--2 kali.2 kali.

7

Algoritma PrimAlgoritma Prim

ContohContoh

Algoritma KruskalAlgoritma Kruskal

Langkah 0:Langkah 0:–– PengurutanPengurutan sisi graf dari bobot kecil ke bobot sisi graf dari bobot kecil ke bobot

besarbesarLangkah 1:Langkah 1:–– T masih kosongT masih kosong

Langkah 2:Langkah 2:–– Pilih sisi (u,v) dengan bobot minimum yang tidak Pilih sisi (u,v) dengan bobot minimum yang tidak

membentuk sirkuit di T. Tambahkan (u,v) ke membentuk sirkuit di T. Tambahkan (u,v) ke dalam T.dalam T.

Langkah 3:Langkah 3:–– Ulangi langkah 2 sebanyak n Ulangi langkah 2 sebanyak n –– 1 kali.1 kali.

8

Pohon berakarPohon berakar

Adalah pohon yang satu buah simpulnya Adalah pohon yang satu buah simpulnya diperlakukan sebagai akar dan sisidiperlakukan sebagai akar dan sisi--sisinya di sisinya di beri arah sehingga menjadi graf berarah.beri arah sehingga menjadi graf berarah.AkarAkar mempunyai derajat masuk sama mempunyai derajat masuk sama dengan dengan nolnol, dan , dan simpulsimpul--simpulsimpul lainnyalainnyaberderajat masuk sama dengan berderajat masuk sama dengan satusatu..Daun (simpul terminal): adalah simpul Daun (simpul terminal): adalah simpul dengan dengan derajatderajat keluarkeluar sama dengan sama dengan nolnol..


(a)(a) Pohon berakar,Pohon berakar,(b)(b) Sebagai perjanjian, tanda panah pada sisi dapat dibuang.Sebagai perjanjian, tanda panah pada sisi dapat dibuang.

9


Pohon dan dua buah pohon berakar yang dihasilkan dari Pohon dan dua buah pohon berakar yang dihasilkan dari pemilihan dua simpul berbeda sebagai akar.pemilihan dua simpul berbeda sebagai akar.

Pohon berakar (terminologi)Pohon berakar (terminologi)

Anak (child) dan orang tua (parent)Anak (child) dan orang tua (parent)–– Simpul Y dikatakan Simpul Y dikatakan anakanak simpul X jika ada sisi simpul X jika ada sisi

dari simpul X ke simpul Y.dari simpul X ke simpul Y.–– X disebut X disebut orangtuaorangtua Y.Y.

Contoh: b,c,d adalah anak simpul a.Contoh: b,c,d adalah anak simpul a.

10


Lintasan (path)Lintasan (path)–– Lintasan dari simpul vLintasan dari simpul v11 ke simpul vke simpul vkk adalah adalah

runtutanruntutan simpulsimpul--simpulsimpul vv11, v, v22, , …… vvkk sedemikian sedemikian sehingga vsehingga vii adalah orangtua dari vadalah orangtua dari vi+1i+1 untuk untuk 11≤≤ii≤≤kk

Contoh: lintasan Contoh: lintasan dari a ke j, adalah a,b,e,j.dari a ke j, adalah a,b,e,j.


Keturunan dan leluhurKeturunan dan leluhur–– Jika terdapat lintasan dari simpul X ke simpul Y Jika terdapat lintasan dari simpul X ke simpul Y

di dalam pohon, maka X adalah di dalam pohon, maka X adalah leluhurleluhur simpul Y, simpul Y, dan Y adalah dan Y adalah keturunanketurunan simpul X.simpul X.

–– Contoh: d adalah leluhur simpul m.Contoh: d adalah leluhur simpul m.

11


Saudara kandung (sibling)Saudara kandung (sibling)–– Simpul yang berorangtua sama adalah Simpul yang berorangtua sama adalah saudarasaudara

kandungkandung satu sama lain.satu sama lain.–– Contoh: h saudara kandung i, tetapi bukan saudara Contoh: h saudara kandung i, tetapi bukan saudara

kandung k.kandung k.


Upapohon (subtree)Upapohon (subtree)–– Misal X adalah simpul di dalam pohon T. Yang Misal X adalah simpul di dalam pohon T. Yang

dimaksud dimaksud upapohonupapohon, dengan X sebagai akarnya, , dengan X sebagai akarnya, ialah upagraf Tialah upagraf T’’=(V=(V’’,E,E’’), sedemikian hingga V), sedemikian hingga V’’mengandung X dan semua keturunannya dan Emengandung X dan semua keturunannya dan E’’mengandung sisimengandung sisi--sisi dalam semua lintasan yang sisi dalam semua lintasan yang berasal dari X.berasal dari X.

12


Upapohon (subtree)Upapohon (subtree)–– Upapohon TUpapohon T’’=(V=(V’’,E,E’’) dengan b sebagai akarnya) dengan b sebagai akarnya


Derajat (degree)Derajat (degree)–– DerajatDerajat sebuah simpul adalah jumlah upapohon sebuah simpul adalah jumlah upapohon

(atau jumlah anak) pada simpul tersebut.(atau jumlah anak) pada simpul tersebut.–– Contoh: derajat a adalah 3, derajat b adalah 2, derajat d Contoh: derajat a adalah 3, derajat b adalah 2, derajat d

adalah 1, derajat c adalah 0.adalah 1, derajat c adalah 0.

13


Daun (leaf)Daun (leaf)–– Simpul yang berderajat nol (tidak mempunyai Simpul yang berderajat nol (tidak mempunyai

anak).anak).–– Contoh: simpul h,i,j,f,c,l,dan m adalah daun.Contoh: simpul h,i,j,f,c,l,dan m adalah daun.


Simpul dalam (internal nodes)Simpul dalam (internal nodes)–– Adalah simpul yang mempunyai anak.Adalah simpul yang mempunyai anak.–– Contoh: simpul b,d,e,g, dan k adalah simpul dalam.Contoh: simpul b,d,e,g, dan k adalah simpul dalam.

14


Aras (level) atau tingkatAras (level) atau tingkat–– Akar mempunyai aras = 0, sedangkan aras simpul lainnya Akar mempunyai aras = 0, sedangkan aras simpul lainnya

= 1 + panjang lintasan dari akar ke simpul tersebut.= 1 + panjang lintasan dari akar ke simpul tersebut.


Tinggi (height) atau kedalaman (depth)Tinggi (height) atau kedalaman (depth)–– Aras maksimum suatu pohon disebut Aras maksimum suatu pohon disebut tinggitinggi atau atau

kedalamankedalaman pohon tersebut.pohon tersebut.–– Atau tinggi pohon adalah panjang maksimum Atau tinggi pohon adalah panjang maksimum

lintasan dari akar ke daun.lintasan dari akar ke daun.

15

Pohon terurutPohon terurut

Adalah pohon berakar yang urutan anakAdalah pohon berakar yang urutan anak--anaknya anaknya penting.penting.Pada pohon terurut, urutan anakPada pohon terurut, urutan anak--anak dari simpul anak dari simpul dalam dispesifikasikan dalam dispesifikasikan dari kiri ke kanandari kiri ke kanan..–– Contoh: (a) urutan anak simpul 1 adalah 2,3,4. Contoh: (a) urutan anak simpul 1 adalah 2,3,4. –– (b) urutan anak simpul 1 adalah 3,4,2.(b) urutan anak simpul 1 adalah 3,4,2.

Pohon mPohon m--aryary

Adalah pohon berakar yang setiap Adalah pohon berakar yang setiap simpul simpul cabangnya mempunyai paling banyakcabangnya mempunyai paling banyak m m buah anak.buah anak.–– m=2 disebut biner, m=3 disebut pohon 3m=2 disebut biner, m=3 disebut pohon 3--aryary

Pohon mPohon m--ary dikatakan ary dikatakan teraturteratur atau atau penuhpenuh(full) jika setiap simpul cabangnya (full) jika setiap simpul cabangnya mempunyai tepat m anak.mempunyai tepat m anak.

16


Pohon parsing dari kalimat Pohon parsing dari kalimat ‘‘ a tall boy wears a red hata tall boy wears a red hat’’


Jumlah daun pada pohon mJumlah daun pada pohon m--ary teratur.ary teratur.–– Pada pohon mPada pohon m--ary teratur dengan tinggi h, ary teratur dengan tinggi h,

jumlah daun adalah mjumlah daun adalah mhh..–– Contoh: pohon 3Contoh: pohon 3--ary teratur dengan jumlah daun = 3ary teratur dengan jumlah daun = 322 = 9= 9

17


Jumlah seluruh simpul pada pohon mJumlah seluruh simpul pada pohon m--ary ary teratur dengan tinggi h:teratur dengan tinggi h:

11....

1210

−−

=++++=+

mmmmmmS

hh


Hubungan antara jumlah daun simpul dalam Hubungan antara jumlah daun simpul dalam pada pohon mpada pohon m--ary teratur :ary teratur :

–– Dimana: Dimana: mm = jumlah anak= jumlah anakii = jumlah simpul dalam dengan m anak= jumlah simpul dalam dengan m anaktt = jumlah daun= jumlah daun

1)1( −=− tim

18


Pohon pertandingan turnamen tenis dengan sistem gugurPohon pertandingan turnamen tenis dengan sistem gugur

Pohon binerPohon biner

Merupakan kasus khusus pohon mMerupakan kasus khusus pohon m--ary jika ary jika m = 2, setiap simpul cabang mempunyai m = 2, setiap simpul cabang mempunyai maksimum dua buah anak.maksimum dua buah anak.Gambar 7.16Gambar 7.16

19


Pohon condong kiri, pohon condong kanan.Pohon condong kiri, pohon condong kanan.


Pohon biner penuh. Pohon biner penuh.

20


Pohon biner seimbangPohon biner seimbang–– Pada beberapa aplikasi, diinginkan tinggi upapohon Pada beberapa aplikasi, diinginkan tinggi upapohon

kiri dan tinggi upapohon kanan seimbang, yaitu beda kiri dan tinggi upapohon kanan seimbang, yaitu beda maksimal 1.maksimal 1.

–– Untuk menyeimbangkan tinggi keduanya, tingi pohon Untuk menyeimbangkan tinggi keduanya, tingi pohon secara keseluruhan harus dibuat seminimal mungkin.secara keseluruhan harus dibuat seminimal mungkin.

–– Untuk memperoleh tinggi minimum, setiap aras Untuk memperoleh tinggi minimum, setiap aras harus mengandung jumlah simpul sebanyak harus mengandung jumlah simpul sebanyak mungkin, dengan menyebarkan setengah dari jumlah mungkin, dengan menyebarkan setengah dari jumlah simpul di upapohon kiri dan setengah dari jumlah simpul di upapohon kiri dan setengah dari jumlah simpul di upapohon kanan.simpul di upapohon kanan.


T1 dan T2 adalah pohon seimbang, sedangkan T3 T1 dan T2 adalah pohon seimbang, sedangkan T3 bukan pohon seimbang. bukan pohon seimbang.

21

In progress In progress ………………..

p o h o npancamr.lecture.ub.ac.id/files/2012/03/p-o-h-o-nhandout.pdfgraf lengkap g dan empat buah...

Documents