Date post: | 06-Jul-2018 |
Category: |
Documents |
Upload: | niwayan-septi-sadevi |
View: | 223 times |
Download: | 0 times |
of 52
8/17/2019 Modul 4. Pohon (2x Pert)
1/52
Modul 4
Pohon
Prof. Dr. H. Nanang Priatna, M.Pd.
alam modul-modul sebelumnya Anda telah mempelajari graph
terhubung tanpa sikel, misalnya model graph untuk molekul C4H10,hierarki administrasi suatu organisasi, pengklasifikasian buku-buku di
perpustakaan, pensortiran surat-surat di kantor pos sebelum disampaikan ke
alamat masing-masing, dan silsilah raja. Graph semaam ini dikenal sebagai
pohon.
D
Kirchoff (1824 - 1887) mengembangkan teori pohon untuk diterapkan
dalam jaringan listrik. !elanjutnya Arthur Cayley (1821 - 1895)
mengembangkan graph jenis ini se"aktu menaah isomer hidrokarbon
jenuh CnH#n$#. !ekarang pohon digunakan seara luas dalam linguistik danilmu komputer.
%odul 4 ini terdiri dari # kegiatan belajar. &egiatan 'elajar 1
menguraikan tentang sifat-sifat pohon, pohon rentang, pohon berakar dan
pohon jumlah. !edangkan pada &egiatan 'elajar # akan dijelaskan mengenai
algoritma &ruskal, algoritma (rim, dan pohon 'iner.
!etelah mempelajari modul ini, diharapkan Anda dapat memahami
pengertian pohon, pohon rentang, pohon berakar, pohon jumlah, algoritma
&ruskal, algoritma (rim, dan pohon 'iner. !elain itu, Anda diharapkan dapatmenggunakannya dalam kehidupan sehari-hari dan dapat mengajarkannya
dengan pendekatan tertentu yang sesuai. !eara khusus tujuan dari penyajian
modul ini adalah agar Anda dapat)
a. menjelaskan pengertian pohon pada teori graph,
b. membuktikan sifat-sifat pohon,
. menentukan pohon rentang dari beberapa graph,
d. menjelaskan pengertian pohon berakar,
e. menentukan pohon jumlah dari suatu graph,f. menentukan pohon jumlah minimal dengan algoritma &ruskal,
g. menentukan pohon biner optimal dengan algoritma Huffman.
PENDAHULUAN
8/17/2019 Modul 4. Pohon (2x Pert)
2/52
Kegiatan Belajar 1
Pohon, Pohon Berakar, dan Pohon Jumlah
ada bagian ini Anda akan mempelajari graph khusus yang disebut
pohon *tree+. Contoh-ontoh dan sifat-sifat penting akan disajikan di
bagian a"al, sedangkan beberapa permasalahan nyata yang berkaitan dengan
pohon diberikan pada bagian akhir.
P
DEFINII 1
(ohon ialah graph terhubung yang tidak memiliki sikel.
Contoh 1
Hierarki administrasi organisasi !! suatu !%A berbentuk seperti pada
Gambar 4.1.
Gambar 4.1
Contoh 2
(ada ahun 1/, Arthur Cayley mempelajari hidrokarbon, ikatan kimia
yang terbentuk dari atom hidrogen dan karbon. 2ia mengetahui bah"a atom
hidrogen terikat *seara kimia+ dengan satu atom yang lainnya, dan setiap
atom karbon terikat dengan empat atom lainnya. (erhatikan Gambar 4.#
berikut.
8/17/2019 Modul 4. Pohon (2x Pert)
3/52
Gambar 4.2
2iagram kimia di atas dapat digambar kembali sebagai graph yang
diilustrasikan pada Gambar 4.3.
Gambar 4.3
Contoh 3
Gambar 4.4
8/17/2019 Modul 4. Pohon (2x Pert)
4/52
Gambar 4.4 *a+ dan 4.4 *b+ merupakan pohon, sedangkan Gambar 4.4 *+
dan 4.4 *d+ bukan pohon, karena Gambar 4.4 *+ graphnya tidak terhubung,
sedangkan Gambar 4.4 *d+ graphnya memiliki sikel.'eberapa sifat dasar dari sebuah pohon, akan diuraikan dalam teorema-
teorema berikut.
Teorema 1
ika pohon, maka untuk setiap dua titik u dan v yang berbeda di
terdapat tepat satu lintasan * path+ yang menghubungkan kedua titik tersebut.
Bukti%isalkan ada lintasan * path+ berbeda yang menghubungkan titik u dan
titik 5 di , katakanlah e1 dan e#, dengan e16e#. %aka e1 dan e# akan
menghubungkan titik u dan titik 5, sehingga ada dua lintasan yang terhubung
pada kedua titik tersebut dan membentuk sikel. 'erdasarkan definisi, tidak
memiliki sikel. 2engan demikian, haruslah e17e#. Hal ini bertentangan
dengan pemisalan bah"a e16e#. adi, terbukti bah"a setiap dua titik yang
berbeda di memiliki tepat satu lintasan yang menghubungkan kedua titik
tersebut.
Teorema 2
'anyaknya titik dari sebuah pohon sama dengan banyaknya sisi ditambah
satu atau ditulis)
ika pohon, maka 89 *+8 7 8: *+8 $1
Bukti
&ita buktikan teorema di atas dengan induksi pada 89*+8. ika pohon
mempunyai satu titik, jelas banyak sisi adalah nol. adi teorema benar
untuk pohon dengan satu titik. Asumsikan bah"a pernyataan dalam
teorema benar untuk pohon dengan k titik, artinya jika pohon mempunyai
paling banyak k titik, maka 89*+8 7 8:*+8 $ 1.
Akan ditunjukkan bah"a jika pohon mempunyai k $ 1 titik maka 8
9*+8 7 8:*+8 $ 1. %isalkan adalah pohon dengan k $ 1 titik dan
adalah sebuah sisi . %aka - memiliki tepat dua komponen 1 dan #,
dan masing-masing komponen adalah pohon dengan titik kurang dari k $ 1.
!ehingga menurut asumsi, 89*i
+8 7 8:*i
+8 $ 1 ; i 7 1,#.
8/17/2019 Modul 4. Pohon (2x Pert)
5/52
!elanjutnya 8:*+8 7 8:*1+8 $ 8:*
#+8 $ 1, sehingga
89*+8 7 89*1+8 $ 89*
#+8
7 8:*1+8 $ 1 $ 8:*#+8 $ 1
7 *8:*1+8 $ 8:*
#+8 $ 1+ $ 1
7 8: *+8 $ 1
2engan demikian teorema terbukti.
Contoh 4
2inas rahasia Amerika !erikat *CA+ telah membentuk jaringan kerja antara
10 agen rahasia yang bekerja di bidang teknologi industri tingkat tinggi.
(enting bagi setiap agen untuk dapat berkomunikasi dengan agen lain seara
langsung atau tidak langsung *salah satu+ melalui suatu mata rantai.
(enentuan lokasi rahasia sulit dilakukan, dan CA ingin agar ada sesedikit
mungkin tempat-tempat pertemuan rahasia itu.
8/17/2019 Modul 4. Pohon (2x Pert)
6/52
Teorema 4
(ernyataan berikut ini ekui5alen untuk pohon .
a. adalah pohon. b. terhubung dan banyak titiknya lebih satu dari banyak sisinya.
. tidak memiliki sikel dan banyak titiknya lebih satu dari banyak sisinya.
d. Ada tepat satu lintasan * path+ sederhana antara setiap dua titik di .
e. terhubung dan penghapusan sembarang sisi pada menghasilkan
graph yang tidak terhubung.
f. tidak memiliki sikel dan penambahan sembarang sisi menghasilkan
sikel pada graph itu.
Teorema 5
ika ( 7 *v0, v
1, v
#, ..., v
n+ sebuah lintasan terpanjang di pohon , maka
d*v0+ 7 d*v
n+ 7 1.
Bukti
%isalkan adalah sebuah pohon dari ( 7 *v0, v
1, v
#, . .., v
n+ lintasan
terpanjang di . Andaikan d*v0+ ≠ 1, maka d*v
0+ = 1. 'erarti ada paling sedikit
dua sisi yang terkait *insiden+ dengan v0. %isalkan e ≠ v
0v
1 adalah sisi
yang terkait dengan v0. &arena ( lintasan terpanjang di dan sederhana,
sisi e harus menghubungkan v0 dengan sebuah titik lain di (, katakan titik v
k ,
k ≠ 0,1. Akibatnya *v0, v
1, v
#, ..., v
k , v
n+ membentuk sikel di , ini
bertentangan dengan kenyataan bah"a sebuah pohon. 2engan kata lain
d*v0+ 7 1. 2engan argumen yang serupa, dapat ditunjukkan d*v
n+ 7 1 .
eorema terbukti.
DEFINII 2
Hutan adalah graph tanpa sikel.
Contoh 5
Gambar 4.
8/17/2019 Modul 4. Pohon (2x Pert)
7/52
Gambar 4. adalah suatu hutan yang terdiri atas 3 komponen.
DEFINII !%isalkan G adalah sebuah graph. !ebuah pohon di G yang memuat
semua titik G disebut pohon rentang (spanning tree+ dari G.
Contoh 6
%isalkan kita mempunyai graph G seperti pada gambar 4.> di ba"ah ini.
erdapat 3 pohon rentang dari graph G, yaitu graph A, ', dan C. ampak
jelas bah"a graph A, ', dan C masing-masing memuat semua simpul dari
graph G serta mengandung sisi-sisi dari G demikian sehingga tidak terbentuk sikel.
Gambar 4.!
Teorema 6
Graph G terhubung jika dan hanya jika G memuat pohon rentang.
Bukti
ika graph G memuat pohon rentang, jelas G terhubung. &ita buktikan
kon5ers pernyataan ini dengan induksi pada 8:*G+8. ika G terhubung dan 8:*G+8 7 0, maka G 7 &
1, sehingga jelas G memuat pohon rentang.
Asumsikan) setiap graph terhubung dengan k $ 1 sisi, maka G memuat
pohon rentang.
(andang sebuah graph terhubung G dengan k $ 1 sisi. ika G tidak
memuat sikel, maka G sebuah pohon rentang. ika G memuat sikel, dan
misalkan e adalah sebuah sisi dari sikel di G, maka graph G1 7 G - e
terhubung dengan k sisi. !ehingga berdasarkan asumsi, G1 memuat pohon
rentang. !ebut , pohon rentang di G1. elas, adalah juga pohon rentang
dari G. eorema terbukti.
8/17/2019 Modul 4. Pohon (2x Pert)
8/52
!ebuah graph terhubung mungkin memuat lebih dari satu pohon rentang,
seperti terlihat pada Gambar 4.. Graph G memuat pohon rentang 1,
#, dan
3.
Gambar 4."
!elanjutnya τ *G+ melambangkan banyaknya pohon rentang pada graph
G. Adakah ara yang dapat dipakai untuk menentukan banyaknya pohon
rentang di dalam sebuah graph? a"abnya akan diberikan dalam teorema
berikut, namun sebelumnya kita perlu memahami notasi-notasi berikut.
%isalkan e adalah sebuah sisi dari graph G. !ebuah graph yang diperoleh
dari G dengan menghapus sisi e dari G dan menyatukan kedua titik akhir darie, dilambangkan dengan G.e *lihat Gambar 4./+.
Gambar 4.#
(erhatikan bah"a banyaknya komponen G sama dengan banyaknya
komponen G.e, begitu pula 8:*G.e+8 7 8:*G+8 - 1 dan 89*G.e+8 7 89*G+8 - 1.
(erlu diatat bah"a jika adalah pohon dan e sisi dari , maka .e juga
sebuah pohon.
8/17/2019 Modul 4. Pohon (2x Pert)
9/52
DEFINII 4
(ohon berakar adalah graph berarah *digraph+ yang mempunyai dua
syarat)1. 'ila arah sisi-sisi pada diabaikan, hasil graph tidak berarahnya
merupakan sebuah pohon, dan
#. Ada titik tunggal @ sedemikian hingga derajat masuk @ adalah 0 dan
derajat masuk sembarang titik lainnya adalah 1. itik @ disebut akar dari
pohon berakar itu.
Contoh 7
Graph pada Gambar 4. *a+ adalah pohon berakar dengan akar A karena *1+ bila arah pada sisinya diabaikan, graph hasilnya merupakan pohon, dan *#+ A
berderajat masuk 0, dan semua titik lainnya berderajat masuk 1. Cara biasa
untuk menggambarkan graph itu ditunjukkan pada Gambar 4. *b+.
Gambar 4.$
itik-titik 2, H, :, dan ' disebut titik terminal , yaitu titik dengan derajat
keluar 0. !edangkan titik-titik A, C, B, dan G disebut titik internal , yaitu titik
yang memiliki derajat keluar yang tidak nol.
Contoh 8
2alam gambar di ba"ah ini konsep pohon berakar digunakan untuk
menggambarkan hubungan antara pasal-pasal dan bab-bab dalam sebuah
buku.
8/17/2019 Modul 4. Pohon (2x Pert)
10/52
Gambar 4.1%
Teorema 7
(ada pohon berakar dengan akar @)
a. 'anyak titik lebih satu dari banyak sisi berarah.
b. idak ada sikel berarah.
. Ada path sederhana berarah yang tunggal dari @ ke setiap titik lain.
Bukti
(embuktian *a+ dan *b+ segera diperoleh karena menjadi pohon bila arahsisinya diabaikan. &emudian, akan ditunjukkan bah"a ada path berarah *dan
karena itu ada path berarah sederhana+ dari @ ke setiap titik lain 9 7 @
karena derajat masuk 9 adalah 1, ada titik 91 7 9 dan sisi berarah dari 9
1 ke
9. ika 91 7 @, pekerjaan telah selesai. ika tidak, ada titik 9
# 7 9
1, dan sisi
berarah dari 9# ke 9
1, karena derajat masuk 9
1 adalah 1. 2an karena tidak
ada sikel berarah, maka 9# 7 9. ika 9
# 7 @, maka pekerjaan selesai. ika
tidak demikian, maka proses ini dapat diulangi, dengan setiap iterasi
*pengulangan+ menghasilkan titik baru. &arena banyak titiknya hingga,
akhirnya pasti @ diapai. adi, telah dibuat path berarah dari @ ke 9.
8/17/2019 Modul 4. Pohon (2x Pert)
11/52
unggalnya path berarah dari @ ke 9 diperoleh seperti pada bagian *a+ dan
*b+.
!ekarang akan diperlihatkan ontoh yang menggunakan pohon berakar untuk mendapatkan penyelesaian suatu masalah.
Contoh 9
Andaikan ada tujuh mata uang yang identik. %ata uang yang kedelapan
kelihatan sama, tetapi sebenarnya lebih berat. 2engan menggunakan neraa
diupayakan menemukan mata uang yang berbeda itu dengan penimbangan
yang sesedikit mungkin dilakukan. %ata uang itu diberi label 1, #, 3, ..., /.
Catat bah"a bila mata uang itu diletakkan pada dua lengan neraa maka
salah satu lengan itu turun atau kedua lengan itu seimbang *terjadi salahsatu+. 2apat di konstruksi sebuah pohon berakar seperti pada Gambar 4.11
yang memberikan pendekatan sistematis untuk melakukan penimbangan.
abel yang diberikan disamping setiap titik menunjukkan mata uang
mana yang ditimbang pada setiap lengan timbangan. Contoh) D1,#E - D3,4E
berarti bah"a mata uang 1 dan # ditimbang pada lengan kiri dan mata uang 3
serta 4 ditimbang di lengan kanan. ika lengan kanan turun, maka dilanjutkan
dengan anak di sebelah kanan untuk penimbangan berikutnya. 2ilakukan hal
yang sama jika lengan kiri turun. Contoh) dimulai dengan membandingkanmata uang 1, #, 3, dan 4 di lengan kiri dan mata uang , >, , dan / di lengan
kanan. ika lengan kiri turun, maka dibandingkan lagi mata uang 1 dan #
terhadap mata uang 3 dan 4. ika pada penimbangan ini lengan kanan turun,
maka berikutnya dibandingkan mata uang 3 dan 4. ika dalam penimbangan
ini lengan kanan turun lagi, maka diapai titik terminal yang menunjukkan
bah"a titik 4 adalah mata uang yang palsu. &arena setiap titik terminal
berada di akhir path berarah sederhana yang panjangnya 3 dari akar, terlihat
bah"a skema ini membutuhkan adanya tiga penimbangan untuk mendapatkan mata uang palsu.
Gambar 4.11
8/17/2019 Modul 4. Pohon (2x Pert)
12/52
Apakah ada pendekatan lain untuk dapat menemukan mata uang palsu
dengan banyak penimbangan yang lebih sedikit? &arena dengan yang
setimbang memiliki 3 hasil yang mungkin, dapat dibuat pohon berakar yangmemiliki tiga anak dan bukan dua anak seperti yang dikerjakan di atas.
Gambar 4.1#. menunjukkan kemungkinan itu. &ita berjalan menuju ke anak
yang di tengah bila dua lengan setimbang. &arena setiap titik terminal berada
di ujung path berarah sederhana yang panjangnya dua dari akar, maka uang
palsu dapat ditemukan dengan hanya melakukan dua kali penimbangan.
Gambar 4.12
(ohon pada Gambar 4.11 dan 4.1# disebut pohon keputusan, disebabkan
karena ara pohon itu menstrukturkan proses pembuatan keputusan.
DEFINII 5
(ohon jumlah graph G adalah pohon *yang dibentuk dengan
menggunakan sisi dan titik graph G+ yang memuat semua titik graph G.
ika Graph G merupakan pohon, maka pohon jumlah satu-satunya adalah
G sendiri. !uatu graph dapat memiliki lebih dari satu pohon jumlah. Ada
beberapa ara untuk memperoleh pohon jumlah suatu graph. !alah satunya
dengan menghapuskan sebuah sisi dari setiap sikel. %etode ini digunakan
untuk menentukan sistem fundamental sirkuit dalam jaringan kerja listrik.
(roses ini diilustrasikan dalam ontoh berikut.
Contoh 10
Graph pada Gambar 4.13 *a+ bukan pohon karena graph itu memuat sikel a,
b, . (rosedur untuk memperoleh pohon adalah dengan menghapus sebuah
sisi di setiap sikelnya. 2engan menghapus b dari sikel a, b, e, d akan
diperoleh graph pada Gambar 4.13 *b+ yang tetap bukan pohon, karena masih
ada sikel , e, d. !ehingga dihapus lagi sebuah sisi pada sikel ini, misal e.
8/17/2019 Modul 4. Pohon (2x Pert)
13/52
Graph hasilnya terlihat pada Gambar 4.13 *+ dan sekarang merupakan
pohon. (ohon ini adalah pohon jumlah untuk graph aslinya.
Gambar 4.13
ika suatu graph terhubung memiliki n titik dan e sisi, dengan e = n,
maka harus dilakukan proses penghapus e - n $ 1 kali dengan tujuan
mendapatkan pohon. &arena dengan melakukan penghapusan ini, banyak sisi
yang semula e berubah menjadi n - 1, yang merupakan banyak sisi dalam
pohon dengan n titik.
%etode yang digambar di atas bukan satu-satunya ara untuk
mendapatkan pohon jumlah. Ada banyak ara lainnya, dan beberapa di
antaranya lebih mudah untuk diprogram pada komputer, karena tidak diperlukan adanya sikel. !alah satu metode ini adalah lgoritma !en"ari
!ertama #e$ar .
lgoritma !ohon %umlah !en"arian !ertama #e$ar
Algoritma ini akan mendapatkan pohon jumlah, jika ada, untuk graph G
yang bertitik n. 2i dalam algoritma ini, adalah himpunan titik berlabel dan
adalah himpunan sisi yang menghubungkan titik-titik di .
angkah-langkahnya sebagai berikut.
1. *mulai pada sebuah titik+. Ambil titik < dan berikan pada < label 0.
%isalkan 7 D
8/17/2019 Modul 4. Pohon (2x Pert)
14/52
letakkan di satu sisi yang menghubungkan titik itu ke titik berlabel k.
ika ada lebih dari satu sisi seperti itu, pilihlah satu sisi sembarang.
&embalilah ke langkah #.
Contoh 11
Akan diaplikasikan algoritma pohon jumlah penarian pertama lebar untuk
mendapatkan pohon jumlah bagi graph pada Gambar 4.14.
8/17/2019 Modul 4. Pohon (2x Pert)
15/52
semua titik graph. adalah pohon jumlah yang diilustrasikan pada Gambar
4.1. abel titik-titiknya diletakkan dalam kurung.
Gambar 4.1
(erlu diatat bah"a ketika menggunakan algoritma ini, ada tempat-
tempat yang sisinya dipilih sembarang. (ilihan berbeda menghasilkan pohon
jumlah yang berbeda.
Contoh 12
Graph G yang diberikan pada Gambar 4.1> tidak memiliki pohon jumlah,
karena tidak ada sisi-sisi yang menghubungkan semua titik G. !ehingga tidak ada path dari A ke :.
Gambar 4.1!
(ada ontoh-ontoh di atas, terlihat bah"a keberadaan pohon jumlah
berkaitan dengan keterhubungan graph itu. eorema berikut menyatakan
hubungan itu seara eksplisit.
Teorema 8
Graph G adalah terhubung jika dan hanya jika G memiliki pohon jumlah.
Bukti
%isalkan graph G memiliki pohon jumlah . &arena adalah graph
terhubung yang memuat semua titik G, maka untuk setiap titik < dan 9 di G
8/17/2019 Modul 4. Pohon (2x Pert)
16/52
ada path yang menggunakan sisi-sisi . etapi karena sisi-sisi adalah juga
sisi-sisi G, maka ada path antara < dan 9 yang menggunakan sisi-sisi G.
&arena itu G terhubung. !ebaliknya, andaikan G adalah terhubung. 2enganmengaplikasikan algoritma pohon jumlah penarian pertama lebar pada G
diperoleh himpunan yang memiliki elemen titik-titik berlabel dan
himpunan yang memiliki sisi-sisi yang menghubungkan titik-titik di .
ebih lagi, adalah pohon. &arena G terhubung, maka setiap titik G
berlabel. adi, memuat semua titik G dan merupakan pohon jumlah
untuk G.
Algoritma lain untuk memperoleh pohon jumlah adalah algoritma
pen"ari pertama dalam.
lgoritma !ohon %umlah !en"arian !ertama &alam
Algoritma ini akan memberikan label titik-titik dan memilih sisi-sisi
graph. (ada algoritma ini, adalah himpunan titik berlabel dan adalah
himpunan sisi yang dipilih.
angkah-langkahnya adalah sebagai berikut.
1. *mulai berdekatan+. Ambil titik < dan berikan pada < label 1. %isalkan
7 D
8/17/2019 Modul 4. Pohon (2x Pert)
17/52
&arena A ada di dan titik berdekatan ' serta : tidak di , langkah 3
segera dijalankan. !ekarang dipilih titik tidak berlabel yang berdekatan
dengan A, katakan :, dan beri : label #. itik : dimasukkan di dan sisinya p ada A serta : ditempatkan di . &arena ada titik di dengan titik
berdekatan tidak di , kita berjalan maju ke langkah 3.
&ali ini, : adalah titik berlabel terbesar yang memiliki titik berdekatan
yang tidak di , pilih satu dari titik berdekatan yang belum berlabel ini,
katakan B. 'erikan pada B label 3, tempatkan B di , dan masukkan sisi pada
: dan B di . angkah 3 perlu diulangi lagi. 2i sini B adalah titik berlabel
terbesar yang memiliki titik berdekatan yang tidak di , sehingga dipilih satu
dari titik berdekatan ini, katakan '. !ekarang ' diberi label 4, dan sisi pada 'dan B ditempatkan di . angkah 3 diulangi dengan melihat pada titik yang
berdekatan dengan ' yang belum berlabel. &arena titik yang seperti itu
hanya C, maka diberikan label pada C dan menempatkan sisi ' dan C di .
2emikian pula pada 2 ditempatkan di .
%asih ada titik-titik berlabel yang memiliki titik berdekatan tanpa label.
&ali ini bukan titik 2 yang berlabel terbesar > dan memiliki titik berdekatan
semaam itu. adi, kita kembali ke titik berlabel dan mendapatkan bah"a
titik itu juga tidak memiliki titik berdekatan tanpa label. (engujian titik berlabel 4 menunjukkan hal yang sama. itik B yang berlabel 3 memiliki
titik-titik berdekatan tidak berlabel dan dipilih satu, katakan H. &emudian
titik H diberi label dan sisi BH ditempatkan di . angkah 3 sekarang
diulangi, dengan G atau , salah satu mendapatkan label /. Andaikan dipilih ,
maka sisi pada H dan dimasukkan di , karena tidak memiliki titik
berdekatan tanpa label, kita kembali ke H, yang berdekatan dengan titik yang
tidak berlabel G. adi G diberi label , dan sisi pada G dan H ditempatkan
di . Gambar 4.1/ mengilustrasikan pelabelan dan penempatan sisi di ituseara lengkap.
Gambar 4.1#
8/17/2019 Modul 4. Pohon (2x Pert)
18/52
erdapat perbedaan mendasar antara penari pertama lebar dan penari
pertama dalam. 2engan penari pertama lebar, dari setiap titik kita berjalan
keluar ke semua titik berdekatannya, dan proses ini diulangi di setiap titik.&ita tidak perlu berjalan kembali untuk melanjutkan penarian. etapi dalam
penari pertama dalam, kita berjalan keluar dari sebuah titik sejauh yang kita
dapat, dan bila tidak dapat melanjutkan, kita kembali ke titik yang baru
dipilih dan memilih pilihan titik berikutnya, kemudian kita berjalan lagi
sejauh yang dimungkinkan.
!ilakan istirahat sejenak
1+ Gambar graph yang bukan pohon sedemikian hingga banyak titiknya
lebih satu dari banyak sisinya
#+ (erhatikan pohon berakar berikut.
3+ entukan pohon jumlah dari graph berikut dengan menggunakan
algoritma pohon jumlah penarian pertama lebar *mulai dengan A dan
gunakan urutan abjad bila ada pilihan untuk sebuah titik+
LATIHAN
8/17/2019 Modul 4. Pohon (2x Pert)
19/52
4+ entukan pohon jumlah dari graph berikut dengan menggunakanalgoritma pohon jumlah penarian pertama dalam
(eriksa dan teliti kembali ja"aban Anda, sekarang ookkan ja"aban
dengan kuni ja"aban berikut ini.
!etun'uk %aa$an #atihan
1+
#+ a. A
b. A, ', C, 2, H,
. , &, , :, B, G
d. C
e. 2, :, Bf. H, , , &,
g. A, ', 2
8/17/2019 Modul 4. Pohon (2x Pert)
20/52
3+
4+
(ohon ialah graph terhubung yang tidak memiliki sikel. Hutan
adalah graph tanpa sikel.
!ebuah pohon pada graph G yang memuat semua titik G disebut
pohon rentang dari G.
(ohon berakar adalah graph berarah *digraph+ yang memenuhi
dua syarat)
*1+ 'ila arah sisi-sisi pada diabaikan, hasil graph tidak berarahnya
merupakan sebuah pohon, dan
*#+ Ada titik tunggal @ sedemikian hingga derajat masuk @ adalah 0 dan
derajat masuk sembarang titik lainnya adalah 1.
(ohon jumlah graph G adalah pohon *yang dibentuk dengan
menggunakan sisi dan titik graph G+ yang memuat semua titik graph G
untuk menentukan pohon jumlah dari graph G dapat dilakukan dengan
RANGKUMAN
8/17/2019 Modul 4. Pohon (2x Pert)
21/52
menggunakan algoritma pohon jumlah penarian pertama lebar atau
algoritma pohon jumlah penarian pertama dalam.
1+ !ebuah pohon mempunyai dua titik berderajat #, sebuah titik
berderajat 3, dan tiga titik berderajat 4. 'anyaknya titik berderajat satu
adalah ....
A.
'. /C.
2. 10
#+ !uatu kompetisi sepak bola melibatkan 1> kesebelasan. Apabila
kompetisi tersebut dilakukan dengan ara sistem gugur *kesebelasan
yang kalah tidak bertanding lagi+, berapa banyak pertandingan untuk
menentukan juara pertama?
A. 1# kali
'. 1 kaliC. 1> kali
2. 1/ kali
3+ 'obot salah satu di antara delapan mata uang yang bentuknya identik
lebih ringan daripada mata uang lainnya. 2engan menggunakan alat
pengukur yang hanya dapat membedakan apakah dua benda sama
beratnya, berapa kali minimum pengukuran bobot harus dilakukan untuk
mengidentifikasi mata uang yang bobotnya teringan?
A. > kali'. kali
C. 4 kali
2. 3 kali
4+ 'anyaknya path *lintasan+ sederhana yang panjangnya bukan nol pada
pohon yang memiliki n titik dengan n = # adalah ....
A. *n*n-1++#
'. *n*n-1++3
C. n*n-1+2. #n*n-1+
TES !RMATI 1
(ilihlah satu ja"aban yang paling tepat
8/17/2019 Modul 4. Pohon (2x Pert)
22/52
+ (ernyataan berikut ini yang benar adalah ....
A. jika pohon, maka untuk setiap dua titik u dan 5 yang berbeda di
terdapat lebih dari satu lintasan * path+ yang menghubungkan keduatitik tersebut.
'. jika pohon, maka 89*+8 7 8:*+8 - 1
C. pohon adalah suatu graph yang tidak memiliki sikel
2. jika e sebuah sisi pada graph G maka τ*G+ 7 τ*G+ 7 τ*G-e+ $ τ*G.e+
>+ Graph lengkap dengan 4 titik mempunyai ....
A. / pohon rentang
'. 1> pohon rentang
C. #0 pohon rentang2. #4 pohon rentang
+ (erhatikan graph pada gambar di ba"ah ini.
Iang $ukan merupakan pohon adalah graph pada gambar ....
A. *i+
'. *ii+
C. *iii+
2. *i5+
/+ 'anyaknya sisi pada pohon dengan #1 titik adalah ....
A. #0 buah
'. #1 buah
C. ## buah
2. tidak tentu
+ !eorang petani ingin mengairi sa"ahnya yang tanamannya mulai
tumbuh. *'erikut ini adalah peta sa"ah itu. 2aerah yang dibatasi sisi
menunjukkan sa"ah dan sisi graph itu menunjukkan pematang sa"ah
yang memisahkan petak sa"ah yang satu dengan yang lain+. (engairan
dilakukan dengan melubangi pematang dan membiarkan air dari luar
menutupi semua sa"ah. 'erapa banyak lubang *sesedikit mungkin+ yang
harus dibuatnya?
8/17/2019 Modul 4. Pohon (2x Pert)
23/52
A. 1/
'. 1>
C. 142. 1#
10+ (erhatikan pohon berakar berikut ini
(ohon akar tersebut mempunyai)
*i+ akarnya A
*ii+ titik internalnya A, ', 2, H
*iii+ titik terminalnya :, B, C, G,
(ertanyaan yang benar adalah ....
A. hanya *i+ dan *ii+ benar
'. hanya *i+ dan *iii+ benar
C. hanya *ii+ dan *iii+ benar 2. *i+, *ii+, dan *iii+ benar
Cookkanlah ja"aban Anda dengan &uni a"aban es Bormatif 1 yang
terdapat di bagian akhir modul ini. Hitunglah ja"aban yang benar.
&emudian, gunakan rumus berikut untuk mengetahui tingkat penguasaan
Anda terhadap materi &egiatan 'elajar 1.
8/17/2019 Modul 4. Pohon (2x Pert)
24/52
"u#u$%
Arti tingkat penguasaan yang Anda apai)
0 - 100J 7 baik sekali
/0 - /J 7 baik
0 - J 7 ukup
K 0J 7 kurang
Apabila menapai tingkat penguasaan /0J atau lebih, Anda dapat
meneruskan dengan &egiatan 'elajar #. &a'u$ etapi bila tingkat
penguasaan Anda masih di ba"ah /0J, Anda harus mengulangi &egiatan
'elajar 1, terutama bagian yang belum Anda kuasai.
ingkat penguasaan 7umlah a"aban yang 'enar
100Jumlah !oal
×
8/17/2019 Modul 4. Pohon (2x Pert)
25/52
Kegiatan Belajar "
Pohon Jumlah Minimal danPohon Biner
A *+,+N ./0A, /INI/A0
&etika dibangun saluran yang menghubungkan tempat-tempat
penyimpanan minyak, biaya pembangunan setiap saluran itu tidak sama
besarnya. &arena kemiringan tanah, jarak, dan faktor-faktor lainnya maka biaya pembangunan salah satu saluran itu dapat lebih tinggi daripada saluran
lainnya.
%asalah ini dapat digambarkan sebagai graph berbobot, dengan bobot
setiap sisinya menunjukkan biaya pembangunan saluran itu *lihat
Gambar 4.1+. %asalahnya adalah bagaimana dapat membangun jaringan-
jaringan pipa yang biayanya serendah mungkin. 2engan kata lain, ingin
ditemukan pohon jumlah yang total biaya sisinya sekeil mungkin.
Gambar 4.1$
2i dalam graph berbobot, bobot sebuah pohon adalah jumlah bobot sisi-sisi pohon itu. !ohon 'umlah minimal di dalam sebuah graph berbobot adalah
pohon jumlah yang bobotnya sekeil mungkin. 2engan kata lain, pohon
jumlah minimal adalah pohon jumlah sedemikian hingga tidak ada pohon
jumlah lain yang memiliki bobot kurang darinya.
Contoh 1
Graph berbobot pada Gambar 4.1, sisi-sisi b, , e, g, dan h membentuk
pohon jumlah dengan bobot 3 $ 4 $ 3 $ 4 $ 3 7 1. !isi a, b, , d, dan emembentuk pohon jumlah yang lain dengan bobot # $ 3 $ 4 $ # $ 3 7 14.
!isi-sisi a, d, f, i, dan j membentuk pohon jumlah yang lain lagi, dengan
8/17/2019 Modul 4. Pohon (2x Pert)
26/52
bobot /. &arena pohon jumlah ini menggunakan kelima sisi dengan bobot
terkeil, maka tidak ada pohon jumlah lain dengan bobot yang lebih keil.
adi, sisi a, d, f, i, dan j membentuk pohon jumlah minimal untuk graph berbobot itu.
(ada ontoh 1 di atas, dapat ditemukan pohon jumlah minimal dengan
ara menoba-oba.
8/17/2019 Modul 4. Pohon (2x Pert)
27/52
%etode yang digunakan pada ontoh # akan selalu menghasilkan pohon
jumlah minimal. %etode ini ditemukan oleh (rim. Algoritma (rim menyusun
pohon dengan memilih sembarang titik dan kemudian suatu sisi dengan bobot terkeil pada titik itu. 'erikutnya, pohon itu dikembangkan dengan
memilih suatu sisi berbobot terkeil. (ohon itu masih dikembangkan lagi
dengan memilih suatu sisi berbobot terkeil yang membentuk pohon dengan
dua sisi terpilih sebelumnya. (roses ini dilanjutkan sampai diperoleh sebuah
pohon jumlah, yang juga merupakan pohon jumlah minimal. (rosedur ini
dapat diformalisasikan sebagai berikut.
1 Al'orit#a *ri# utu *oho u#lah /ii#al2engan algoritma ini akan ditemukan pohon jumlah minimal *jika ada+
untuk sebuah graph berbobot G dengan n titik. 2alam algoritma ini ! adalah
himpunan titik dan adalah himpunan sisi.
#angkah 1 *mulai+. (ilih titik
8/17/2019 Modul 4. Pohon (2x Pert)
28/52
Gambar 4.21
&arena ! tidak memuat semua titik G, diperhatikan sisi pada
8/17/2019 Modul 4. Pohon (2x Pert)
29/52
Gambar 4.22
(ada dua tempat berbeda pada ontoh di atas, dapat dipilih lebih dari
satu titik dengan bobot terkeil. Algoritma itu menunjukkan bah"a setiap
titik dengan bobot terkeil dapat saja dipilih. leh karena itu dapat disusun
pohon jumlah minimal yang berbeda, tergantung pada pilihan yang
dilakukan. %isal) jika pada ontoh 3 dipilih sisi d dan bukan b, diikuti
dengan dan h, maka pohon jumlah minimalnya adalah seperti pada
Gambar 4.#3. adi, pohon jumlah minimalnya tidak tunggal.
Gambar 4.23
(erhatikan kembali Gambar 4.#1. Andaikan sekarang bobot sisi-sisi itu
menunjukkan besarnya keuntungan yang dihasilkan bila minyak dipompakanmelalui saluran itu. %asalahnya sekarang adalah mendapatkan pohon jumlah
saluran yang menghasilkan keuntungan terbesar. adi, sekarang diinginkan
untuk mendapatkan pohon jumlah yang total bobot sisinya bukan paling
keil, melainkan paling besar.
(ohon jumlah maksimal di dalam graph berbobot adalah pohon jumlah
yang bobotnya sebesar mungkin. 2engan kata lain, bobot pohon jumlah itu
paling besar, tidak ada pohon jumlah lain yang bobotnya lebih besar.
8/17/2019 Modul 4. Pohon (2x Pert)
30/52
Contoh 4
8/17/2019 Modul 4. Pohon (2x Pert)
31/52
Algoritma ini akan mendapatkan pohon jumlah minimal, jika ada, untuk
graph berbobot G yang memiliki n titik, dengan n = #. 2alam algoritma ini, !
adalah himpunan titik dan adalah himpunan sisi. #angkah 1 *mulai+. ika tidak ada sisi, G tidak terhubung, dan karena itu
tidak memiliki pohon jumlah minimal. ika tidak demikian,
ambil sebuah sisi dengan bobot terkeil *rangkaian dapat
diputuskan seara sembarang+. empatkan sisi itu di dan
titiknya di !.
#angkah 2 *pemeriksaan untuk penyelesaian+. ika memuat n - 1 sisi,
maka berhentilah; sisi-sisi di dan titik-titik di ! membentuk
pohon jumlah minimal. ika tidak demikian lanjutkan kelangkah 3.
#angkah 3 *ambil sisi berikutnya+. entukan sisi-sisi berbobot terkeil yang
tidak membentuk sikel dengan sembarang sisi yang ada di .
ika tidak ada sisi seperti itu, G tidak terhubung dan tidak
memiliki pohon jumlah minimal. ika tidak demikian, pilih satu
sisi sejenis itu *rangkaian dapat diputus seara sembarang+, dan
tempatkan sisi itu di dan titiknya di !. &embalilah ke
langkah #.
Contoh 5
Gunakan algoritma &ruskal untuk menentukan pohon rentang dengan bobot
minimum dari graph berikut.
Gambar 4.2
%aa$
8/17/2019 Modul 4. Pohon (2x Pert)
32/52
Ambil sebuah sisi dengan bobot terkeil, sisi itu adalah f, sehingga 7 D E
dan ! 7 DA, BE. entukan sisi berbobot terkeil yang tidak membentuk sikel
dengan sembarang sisi yang ada di , sisi itu adalah g, sehingga 7 Df, gEdan ! 7 DA, ', BE. (ilih sisi berbobot terkeil yang tidak membentuk sikel
dengan sembarang sisi yang ada di , sisi itu adalah i, sehingga 7 Df, g, iE
dan ! 7 DA, ', B, GE. !isi dengan bobot terkeil yang tidak membentuk sikel
dengan sembarang sisi yang ada di adalah j dan k, misalkan seara
sembarang diambil k. adi 7 Df, g, i, kE dan ! 7 DA, ', 2, B, GE. Ambil sisi
bobot terkeil yang tidak membentuk sikel dengan sembarang sisi di , yaitu
. adi 7 D, f, g, i, kE dan ! 7 DA, ', C, 2, B, GE. (ilih sisi h, sehingga 7
D, f, g, h, i, kE dan ! 7 DA, ', 2, :, B, GE. &arena ! memuat semua titik dari graph tersebut, maka pohon jumlah minimum dari graph tersebut terlihat
pada Gambar 4.#> dengan bobot 1.
Gambar 4.2!
Contoh 6
Gunakan algoritma &ruskal untuk menentukan pohon rentang dengan bobot
minimum dari graf G berikut.
Gambar 4.2"
8/17/2019 Modul 4. Pohon (2x Pert)
33/52
(ertama-tama kita tentukan sisi dengan bobot terkeil. !isi dengan bobot 1
terpilih sebagai sisi pertama yang kita pilih.
8/17/2019 Modul 4. Pohon (2x Pert)
34/52
Gambar 4.31
erdapat # sisi dengan bobot 4. &ita pilih sebuah sisi dengan bobot 4,
sehingga kita peroleh gambar berikut.
Gambar 4.32
!ekarang hanya tinggal sebuah titik lagi yang belum terambil. 2ari 4 sisi
yang insiden dengan titik ini, yang mempunyai bobot terkeil adalah sisi
dengan bobot . &ita pilih sisi ini sehingga pohon optimalnya terlihat pada
gambar di ba"ah ini dengan sisi yang dietak lebih hitam.
Gambar 4.33
(ohon optimal ini total bobotnya adalah 1 $ 3 $ # $ 4 $ # $ 7 1.
& *+,+N &INE"
(ohon biner adalah pohon berakar yang setiap titiknya memiliki paling
banyak dua anak dan setiap anak ditunjuk sebagai anak kiri atau anak kanan.adi, pada pohon biner setiap titik mungkin memiliki 0, 1, atau # anak. Anak
8/17/2019 Modul 4. Pohon (2x Pert)
35/52
kiri digambarkan di sebelah kiri dan di ba"ah orang tuanya, serta anak kanan
di sebelah kanan di ba"ah orang tuanya.
Contoh 7
8/17/2019 Modul 4. Pohon (2x Pert)
36/52
Gambar 4.3!
Contoh 10
(ohon pernyataan untuk a $ d N *b - + diiptakan dengan barisan pohon
biner pada Gambar 4.3.
Gambar 4.3"
Contoh 11
(ernyataan *a $ b N + - *f - de+ disajikan dengan pohon pernyataan pada
Gambar 4.3/.
Gambar 4.3#
!ilakan Anda istirahat sejenak, kemudian kerjakanlah soal-soal latihan
berikut.
LATIHAN
8/17/2019 Modul 4. Pohon (2x Pert)
37/52
1+ entukan pohon jumlah minimal dan bobotnya dengan menggunakan
algoritma (rim, mulai dari titik A pada graph berikut
#+ entukan pohon jumlah minimal dan bobotnya dengan menggunakan
algoritma (rim, mulai dari titik C pada graph soal nomor 1
3+ entukan pohon jumlah minimal dan bobotnya dengan menggunakan
algoritma &ruskal pada graph berikut
4+ &onstruksikan pohon pernyataan untuk operasi **a - b++N *d $ ef+
(eriksa dan teliti kembali ja"aban Anda, sekarang ookkan ja"abannya
dengan kuni ja"aban berikut ini.
!etun'uk %aa$an #atihan
1+ %ulai dari titik A, sehingga 7 D E dan ! 7 DAE. (erhatikan sisi a, b, d,
ambil bobot terkeil yaitu a, sehingga 7 DaE dan ! 7 DA, 'E.
(erhatikan sisi-sisi yang memiliki satu titik di ! dan satu titik tidak di !,
8/17/2019 Modul 4. Pohon (2x Pert)
38/52
yaitu b, , d, e. (ilih sisi , karena bobot terkeil, sehingga 7 Da, E dan
! 7 DA, ', BE. Ambil sisi yang memiliki satu titik di ! dan satu titik
tidak di ! dengan bobot terkeil yaitu g, sehingga 7 Da, , gE dan! 7 DA, ', C, :E. (ilih sisi f, didapat 7 Da, , g, fE dan ! 7 DA, ', C,
2, :E. &arena ! memuat semua titik dari graph tersebut, maka pohon
jumlah minimal dari graph tersebut adalah seperti berikut dengan
bobot .
#+ %ulai dari titik C, sehingga 7 D E dan ! 7 DCE. (erhatikan sisi d, e, f,
g. Ambil bobot terbesar, yaitu e, sehingga 7 DeE dan ! 7 D', CE.
(erhatikan sisi-sisi yang memiliki satu titik di ! dan satu titik tidak di !.
(ilih sisi d, karena bobotnya terbesar sehingga 7 Dd, eE dan ! 7 DA, ',
CE. &emudian pilih sisi b sehingga 7 Db, d, eE dan ! 7 DA, ', C, 2E.
(erhatikan sisi , g, h. &arena bobot terbesar yaitu dan h, pilih searasembarang misalnya sisi h, sehingga 7 Db, d, e, hE dan ! 7 DA, ', C,
2, :E yang merupakan pohon jumlah maksimal dengan bobot 1/, seperti
pada gambar berikut.
3+ (ilih sebuah sisi dengan bobot terkeil, sisi itu adalah f dan i. %isalkan
diambil seara sembarang f, sehingga 7 DfE dan ! 7 D2, :E. entukan
sisi berbobot terkeil yang tidak membentuk sikel dengan sembarang sisi
yang ada di , sisi itu adalah i, sehingga 7 Df, iE dan ! 7 D2, :, GE.
(ilih sisi berbobot terkeil yaitu , sehingga 7 D, f, iE dan ! 7 DA, 2,
:, GE. (ilih sisi dengan bobot terkeil yaitu b atau j, misalkan diambil b.adi 7 Db, e, f, g, iE dan ! 7 A, C, 2, :, GE. Ambil sisi bobot terkeil
yang tidak membentuk sikel dengan sembarang sisi di , yaitu .
8/17/2019 Modul 4. Pohon (2x Pert)
39/52
!ehingga 7 Db, , f, i, jE dan ! 7 DA, C, 2, :, B, GE. (ilih sisi a,
sehingga 7 Da, b, , f, i, jE dan ! 7 DA, ', C, 2, :, B, GE yang
merupakan pohon jumlah minimal dengan bobot 14 seperti terlihat padagambar berikut.
4+
2i dalam graph berbobot, bobot sebuah pohon adalah jumlah bobot
sisi-sisi pohon itu. (ohon jumlah minimal di dalam sebuah graph adalah
pohon jumlah yang bobotnya paling keil. (ohon jumlah maksimal di
dalam graph berbobot adalah pohon jumlah yang bobotnya paling besar.
8/17/2019 Modul 4. Pohon (2x Pert)
40/52
anak kanan. adi, pada pohon biner setiap titik mungkin memiliki 0,1,
atau # anak.
1+ 2engan menggunakan algoritma &ruskal, pohon rentang dengan bobotminimum dari graph berikut adalah ....
A. 1/
'. 1
C. #0
2. #1
#+ ima komputer harus dipasang di sebuah kantor dan satu sama lain
saling terhubung *dapat seara langsung atau dengan melalui komputer
lain, salah satu+. (anjang kabel yang diperlukan untuk menghubungkan
unit-unit komputer yang berdekatan diberikan dalam meter. 'erapa panjang minimum kabel yang diperlukan? *%enggunakan algoritma
&ruskal+
TES !RMATI "
(ilihlah satu ja"aban yang paling tepat
8/17/2019 Modul 4. Pohon (2x Pert)
41/52
A. ,3 meter
'. ,1 meter C. >, meter
2. >,1 meter
3+ 2i sebuah kota terdapat enam tempat yaitu A, ', C, 2, :, dan B. Iang
perlu dipasang kabel telepon agar terhubung satu dengan yang lain.
'erapa panjang minimum kabel yang diperlukan? *jarak dalam
kilometer+. *%enggunakan algoritma &ruskal+
A. #1 kilometer
'. ## kilometer
C. #3 kilometer
2. #4 kilometer
4+ &antor pusat suatu perusahaan akan membangun jaringan pos elektronik
*menggunakan satelit+ dengan anak-anak perusahaannya yang terbesar di
tempat-tempat seperti pada gambar berikut. 'iaya membangun
hubungan itu tergantung pada jaraknya dan dinyatakan dalam jutaanrupiah. 'erapa biaya maksimum untuk membangun jaringan itu?
•
8/17/2019 Modul 4. Pohon (2x Pert)
42/52
A. 14, juta rupiah
'. 1> juta rupiah
C. 1, juta rupiah2. 1 juta rupiah
+ Gambar berikut memberikan informasi tentang panjang kabel yang
diperlukan untuk menghubungkan lima lampu taman *panjang dalam
meter+. 'erapa panjang minimum kabel yang diperlukan?
A. 3 meter
'. #4 meter
C. #3 meter
2. #1 meter
>+ empat-tempat "isata di suatu aman Oasional saling terhubung dengan
jalan-jalan yang jaraknya *dalam kilometer+ diperlihatkan pada gambar
berikut. !etiap tempat "isata perlu mendapatkan persediaan air. (ipa-
pipa air itu dipasang sepanjang sisi jalan-jalan yang telah dibangun.
'erapa panjang minimum pipa yang diperlukan?
A. 40 kilometer
'. 4# kilometer
C. 44 kilometer
2. 4> kilometer
+ 2engan menggunakan algoritma (rim, pohon rentang dengan bobot
maksimum dari graph berikut adalah ....
8/17/2019 Modul 4. Pohon (2x Pert)
43/52
A. 14
'. #0
C. #>2. #
/+ (ohon rentang minimum dari graph berikut mempunyai bobot ....
A. ##
'. #0
C. 1/
2. 1>
+ &onstruksi pohon pernyataan dari operasi a N b $ adalah ....
.
10+ 2iagram pohon berikut menunjukkan pohon pernyataan dari operasi P.
8/17/2019 Modul 4. Pohon (2x Pert)
44/52
A. # $ 3 N - 4
'. # $ *3 N + - *4+
C. *# $ 3 N + - *4+2. *# $ 3+ N * - 4+
Cookkanlah ja"aban Anda dengan &uni a"aban es Bormatif # yang
terdapat di bagian akhir modul ini. Hitunglah ja"aban yang benar.
&emudian, gunakan rumus berikut untuk mengetahui tingkat penguasaan
Anda terhadap materi &egiatan 'elajar #.
"u#u$%
Arti tingkat penguasaan yang Anda apai)
0 - 100J 7 baik sekali
/0 - /J 7 baik
0 - J 7 ukup
K 0J 7 kurang
Apabila menapai tingkat penguasaan /0J atau lebih, Anda dapat
meneruskan dengan modul berikutnya. &a'u$ etapi bila tingkat
penguasaan Anda masih di ba"ah /0J, Anda harus mengulangi &egiatan
'elajar #, terutama bagian yang belum Anda kuasai.
ingkat penguasaan 7umlah a"aban yang 'enar
100Jumlah !oal
×
8/17/2019 Modul 4. Pohon (2x Pert)
45/52
&un'i Ja(aban )e* +ormatif
)es *ormati+ 1
1+ C 'anyaknya titik berderajat satu adalah , seperti terlihat pada
gambar pohon berikut.
#+ ' 'agan pertandingannya adalah sebagai berikut.
uara
banyaknya pertandingan untuk menentukan juara pertama ada 1
kali pertandingan.
3+ 2 2iagram pohonnya adalah sebagai berikut.
8/17/2019 Modul 4. Pohon (2x Pert)
46/52
4+ A n 7 #, ada 1 path) lintasannya 91 - 9
#
n 7 3, ada 3 path) lintasannya 9# - 9
1, 9
3 - 9
1, dan 9
# - 9
1 - 9
3
n 7 4, ada > path) lintasannya 91 - 9
#, 9
1 - 9
3, 9
1 - 9
4, 9
# - 9
1 -
93,9# - 91 - 94, dan 93 - 91 - 94
+ C Graph pada gambar *iii+ bukan merupakan pohon, karena tidak
terhubung.
/+ A 89*+8 7 8:*+8 $ 1
#1 7 8:*+8 $ 1
8:*+8 7 #0
8/17/2019 Modul 4. Pohon (2x Pert)
47/52
+ 2
10+ 2 !emuanya *i+, *ii+, dan *iii+ benar.
)es *ormati+ 2
1+ '
#+ C
3+ A
8/17/2019 Modul 4. Pohon (2x Pert)
48/52
4+ 2
+ C
>+ '
+ C
/+ C
8/17/2019 Modul 4. Pohon (2x Pert)
49/52
+ A
10+ 2 *# $ 3+ N * - 4+
8/17/2019 Modul 4. Pohon (2x Pert)
50/52
Daftar Pu*taka
'udayasa, . &. *1+. ,atematika &iskrit - . !urabaya) +. .raph )heor/. California) Addison Fesley (bulishing
Company.
%ayeda, F. *1#+. .raph )heor/. Oe" Iork) ohn :iley and !ons, n.
!uryadi, 2. *11>+. ,ateri !okok ,atematika &iskrit . *%odul dan
%odul >+. akarta) +. ,ateri !okok !engantar )eori .raph. akarta)
8/17/2019 Modul 4. Pohon (2x Pert)
51/52
Glo*arium
Aa$e
2ua buah titik disebut a'asen, jika kedua titik tersebut merupakan titik-
titik ujung dari sisi yang sama.
Al'orit#a
Algoritma merupakan prosedur atau aturan. Contoh) algoritma &ruskal
dan algoritma Huffman.
&oot
'obot suatu Graph G yaitu ukuran sisi-sisi dari graph G. 2apat juga
merupakan bobot *jumlah+ keseluruhan dari sisi-sisi graph G.
Deraat titi
2erajat titik 9 yaitu jumlah atau banyaknya sisi yang insiden dengan
titik 9.
,uta
Hutan adalah graph tanpa sikel. Hutan merupakan gabungan dari
beberapa pohon.
I$i6e
ika sebuah titik 9 merupakan titik ujung dari sisi : maka 9 dan : saling
berinsidensi atau titik 9 insiden dengan sisi :.
0ita$a (3ath)
!uatu lintasan u-5 *u-5 path+ dalam graph G adalah lintasan yang tidak
mengulangi sebarang sisi *rusuk+ dan tidak mengulangi sebarang titik
*simpul+.
*oho
(ohon ialah graph terhubung yang tidak memiliki sikel.
*oho eraar
(ohon berakar adalah graph berarah *digraph+ yang memenuhi syarat)
*1+ bila arah sisi diabaikan maka graphnya merupakan pohon, dan *#+
ada titik tunggal @ sehingga derajat masuknya 0 dan derajat masuk titik
lainnya 1.
8/17/2019 Modul 4. Pohon (2x Pert)
52/52
*oho ier
(ohon biner adalah pohon berakar yang setiap titiknya memiliki paling
banyak dua anak, yaitu anak kiri dan anak kanan.
*oho u#lah
(ohon jumlah graph G adalah pohon yang dibentuk dengan
menggunakan sisi dan titik graph G yang memuat semua titik di G.
*oho u#lah #ii#al
(ohon jumlah minimal graph berbobot G adalah pohon jumlah yang
bobotnya paling keil.
*oho reta'
(ohon rentang graph G adalah pohon pada graph G yang memuat semua
titik di G.
iel
!ikel adalah suatu sirkuit yang tidak mengulang sebarang titik
internalnya *titik dalamnya+.
iruit
intasan u-5, dengan u 7 5 *titik a"al sama dengan titik akhir+ disebut
sirkuit.