Tree 2021 [PDF]

Citation preview

Bab 10 Pohon



Pada diskusi mengenai graf kita sadari bahwa graf yang paling penting baik secara teoritis maupun parktis adalah graf terhubung. Di antara graf-graf terhubung pohon merupakan graf terhubung yang paling sederhana, tetapi mempunyai aplikasi yang paling banyak. Pada bab ini kita diskusikan pohon mulai dari aspek eksistensi, aspek counting, maupun aspek optimisasi.



10.1 Sifat-sifat Pohon Kita mulai diskusi kita dengan memperkenalkan beberapa istilah dan sifat-sifat dasar dari sebuah pohon. Definisi 10.1.1 Sebuah pohon adalah sebuah graf terhubung yang tidak memuat cycle (asiklik). Sebuah daun pada sebuah pohon adalah sebuah titik yang mempunyai derajat 1. Gambar 10.1 berikut memberikan semua pohon berlabel dengan dua titik dan tiga titik. 3t



3t



t



t



t



t



t



@ @ @t



1



2



1



2



1



2



3t t



@ @ @t



1



2



Gambar 10.1 Pohon berlabel dengan 2 dan 3 titik



222



10.1 Sifat-sifat Pohon



223



Bila kita amati kembali pohon dengan 2 dan 3 titik pada Gambar 10.1, maka setiap pohon mempunyai dua daun. Lemma 9.2 berikut memberikan batas bawah bagi banyak daun pada sebuah pohon. Lemma 10.1.2 Sebuah pohon dengan n ≥ 2 titik mempunyai sedikitnya dua daun.



Bukti. Andaikan T adalah sebuah pohon dan misalkan lintasan sederhana w:v1 − v2 − · · · − vt adalah sebuah lintasan sederhana terpanjang yang berada di T . Karena T tidak memuat cycle, maka v1 6= vt . Hal ini berakibat deg(v1 ) = deg(vt ) = 1, sehingga T mempunyai sedikitnya dua daun. Berikut ini kita diskusikan beberapa karakterisasi dari sebuah pohon. Teorema 10.1.3 Sebuah graf T yang terdiri atas n titik dan m sisi adalah sebuah pohon jika dan hanya jika T adalah asiklik dan m = n − 1.



Bukti. Andaikan T adalah sebuah pohon atas n titik. Maka T adalah asiklik. Kita perlihatkan m = n − 1 dengan menggunakan induksi atas n, yakni banyak titik dari pohon T . Bila n = 1, maka sebuah pohon dengan satu titik mempunyai tepat 0 sisi. Asumsikan bahwa setiap pohon dengan n titik mempunyai n − 1 sisi. Andaikan T adalah sebuah pohon dengan n + 1 titik. Kita perlihatkan bahw T mempunyai n sisi. Misalkan v0 adalah sebuah daun di T . Andaikan T0 = T − v0 , yakni T0 adalah sebuah graf yang diperoleh dari T dengan membuang titik v0 dan sisi yang insiden dengan v0 . Karena v0 adalah sebuah daun, maka T0 adalah terhubung dan tidak mempunyai cycle. Jadi T0 adalah sebuah pohon dengan n titik. Oleh asumsi induksi T0 mempunyai n − 1 sisi. Akibatnya T mempunyai n sisi. Sebaliknya andaikan T adalah sebuah graf asiklik dengan n titik dan m sisi yang memenuhi m = n − 1. Kita perlihtkan bahwa T adalah sebuah pohon. Cukup diperlihatkan bahwa T adalah terhubung. Andaikan T mempunyai k buah komponen Ti, i = 1, 2, . . ., k



224



Bab 10: Pohon



adalah sebuah pohon, katakan masing-masing dengan ni titik dan mi sisi. Perhatikan bahwa n−1 = m=



k X i=1



mi =



k X



(ni − 1) = n − k.



i=1



Persamaan di atas berakibat bahwa k = 1, yakni T hanya mempunyai satu komponen terhubung. Jadi T adalah terhubung. Teorema 10.1.4 Sebuah graf T dengan n titik dan m sisi adalah sebuah pohon jika dan hanya jika G adalah terhubung dan n = m + 1. Bukti. Andaikan T adalah sebuah pohon dengan n titik dan m sisi. Oleh definisi pohon, T adalah terhubung. Oleh Teorema 10.1.3 kita peroleh n = m + 1. Andaikan T adalah sebuah graf terhubung dengan n = m + 1. Kita perlihatkan T adalah sebuah pohon, yakni T adalah asiklik. Jika T memuat sebuah cycle C dan e adalah sebuah sisi dari C, maka graf T −e adalah sebuah terhubung dengan n titik dan n−2 sisi. Hal ini tidak mungkin, karena graf terhubung dengan n titik memerlukan sedikitnya n − 1 sisi. Sehingga T tidak mempunyai cycle. Teorema 10.1.5 Sebuah graf T adalah sebuah pohon jika dan hanya jika setiap dua titik berbeda dihubungkan oleh tepat satu lintasan sederhana. Bukti. Andaikan T adalah sebuah tree, maka setiap dua titik berbeda dihubungkan oleh lintasan. Bila dua titk u dan v dihubungkan oleh lebih dari satu lintasan berbeda, maka kedua lintasan tersebut akan membnetuk sebuah cycle. Hal ini bertentangan dengan asumsi bahwa T adalah sebuah pohon. Jadi setiap dua titik berbeda di T dihubungkan oleh tepat satu lintasan sederhana. Sebaliknya andaikan T adalah sebuah graf dengan sifat bahwa setiap dua titik berbeda di T dihubungkan oleh tepat satu lintasan. Sifat ini mengakibatkan T adalah terhubung. Jika T memuat sebuah cycle C yang memuat titik u dan v, maka u dan v dihubungkan oleh sedikitnya dua lintasan sederhana berbeda. Hal ini bertentangan dengan hipotesis bahwa setiap dua titi berbeda dihubungkan oleh



10.2 Pohon Perentang



225



tepat satu lintasan sederhana. Jadi T tidak mempunyai cycle, karenanya T adalah sebuah pohon. . Teorema berikut memberi karakterisasi dari sebuah pohon. Bukti dari teorema berikut diserahkan kepada pembaca sebagai latihan. Teorema 10.1.6 Andaikan G adalah sebuah graph dengan n ≥ 2 titik, tanpa loop dan tanpa sisi paralel. Yang berikut adalah ekivalen (a) G adalah sebuah pohon. (b) G adalah terhubung, tetapi tidak terhubung bila satu sisi dari G dibuang. (c) G adalah asiklik (tidak mempunyai simple cycle), tetapi tidak asiklik bila satu sisi ditambahkan ke G.



10.2 Pohon Perentang Andaikan G adalah sebuah graf terhubung. Sebuah pohon perentang T dari graf G adalah sebuah subgraf perentang dari G yang merupakan sebuah pohon. Teorema 10.2.1 Setiap graf terhubung G mempunyai pohon perentang.



Bukti. Andaikan G0 adalah sebuah subgraph terhubung dari G dengan V (G0 ) = V (G) dan G0 mengandung sisi sesedikit mungkin. Kita perlihatkan bahwa G0 adalah sebuah pohon perentang. Andaikan sebaliknya G0 bukan pohon perentang dari G, yakni G0 memuat cycle C dengan sisi e berada di cycle C. Misalkan G00 adalah graf yang diperoleh dari G0 dengan membuang sisi e. Karena e berada di cycle C, dan setiap dua titik di cycle dihubungkan oleh dua lintasan sederhana yang berebda, maka G00 adalah suatu subgraph terhubung dari G. Tetapi G00 memiliki sisi yang lebih sedikit dari G0 . Kontradiksi dengan fakta bahwa G0 mengandung sisi sesedikit mungkin. Sehingga G0 adalah suatu pohon perentang dari G.



226



Bab 10: Pohon



Bukti yang kita diskusikan di atas dilakukan atas dasar bukti dengan kontradiksi. Berikut diberikan bukti yang bersifat konstruktif, yakni bukti ini memberikan cara untuk menemukan sebuah pohon perentang pada graf terhubung. Bukti. Andaikan G adalah sebuah graf terhubung. Bila G tidak mempunyai cycle, maka G adalah sebuah pohon perentang. Bila tidak demikian, maka G memuat sebuah cycle C. Pilih sebuah sisi e pada cycle C, dan kemudian hapus sisi e dari G sehingga diperoleh graf G − e. Kembali karena setiap dua titik di cycle dihubungkan oleh dua lintasan berbeda, maka graf G − e adalah sebuah graf terhubung. Jika G − e tidak memuat cycle, maka G − e adalah sebuah pohon perentang. Bila tidak lakukan proses ini berulang-ulang sehingga kita peroleh pohon perentang dari G. Perhatikan pada setiap pengulangan sisi dari graf G − e berkurang satu dari sisi graf G, sehingga prosedur ini akan berhenti dan menghasilkan sebuah pohon perentang.  t @ @ @t



t



t



t @ @ @t



t @ @ @t



t



t



t @ @ @t



t



t t t



t



t



Gambar 10.1 Sebuah Graf dan dua pohon perentang



Perhatikan bahwa pada bukti di atas, kita bebas memilih sisi yang akan dihapus dari cycle. Hal ini mengindikasikan bahwa sebuah graf terhubung mungkin saja memiliki lebih dari satu pohon perentang. Banyaknya pohon perentang dari sebuah graf G disebut sebagai bilangan pohon dari G dan dinotasikan dengan κ(G). Gambar 10.2 memberikan sebuah graf terhubung dan dua buah pohon perentang yang dimuat oleh graf tersebut. Teorema 10.2.2, yang disajikan tanpa bukti, memberikan formula bagi banyaknya pohon perentang berlabel yang termuat dalam sebuah graf. Bukti dari Teorema 10.2.2 melibatkan pengetahuan aljabar linier yang sangat intensif yang tentu saja di luar topik diskusi kita. Andaikan G adalah sebuah graf dan D adalah digraf orientasi



227



10.2 Pohon Perentang



dari G. Misalkan P adalah matriks insidensi dari digraf D dan J adalah sebuah matriks bujursangkar dengan semua entri 1. Teorema 10.2.2 Banyaknya pohon perentang berlabel dari sebuah graf G dengan n titik adalah κ(G) = det(J + P P t )/n2 .



Kita sadari bahwa digraf orientasi dari sebuah graf tidak tunggal. Hal ini berakibat bahwa matriks insidensi P dari digraf orientasi tidak tunggal. Tetapi Teorema 10.2.2 menjamin bahwa bilangan pohon κ(G) dari sebuah graf G tidak bergantung pada pemilihan digraf orientasinya. Sehingga dalam penentuan κ(G) kita bebas menggunakan digraf orientasi. Contoh 10.2.3 Perhatikan sebuah graf G beserta digraf D pada Gambar 10.2. 1t



2t



@ @ @6t t



5@



@ @t



t



4



G



3



1t



-2t



6 I @ @6t 6 t 5@ @ R t? t



4



D



3



Gambar 10.2 Sebuah graf dan digraf orientasi Bila busur-busur dari D diurutkan dalam urutan (1, 2), (2, 3), (3, 4), (4, 1), (6, 1), (2, 6), (4, 5), (5, 3), (5, 6), maka matriks insidensi dari digraf D adalah matriks  1 0 0 −1 −1 0 0 0 0  −1 1 0 0 0 1 0 0 0   0 −1 1 0 0 0 0 −1 0 P =  0 0 −1 1 0 0 1 0 0   0 0 0 0 0 0 −1 1 1 0 0 0 0 1 −1 0 0 −1







   .   



228



Bab 10: Pohon



Sehinggga κ(G) = det(J +P P t )/36 = 75. Jadi G mempuyai 75 buah pohon perentang berlabel.  Secara khusus teorema berikut memberikan banyaknya pohon perentang yang dimiliki oleh sebuah graf lengkap. Teorema 10.2.4 Graf lengkap Kn atas n ≥ 3 titik mempunyai sebanyak nn−2 pohon perentang berlabel.



Bukti. Teorema 10.2.4 ekivalen dengan pernyataan terdapat nn−2 buah pohon berlabel atas n ≥ 3 titik. Andaikan T (n; d1, d2 , . . . , dn) menyatakan banyaknya pohon berlabel atas n titik dengan barisan derajat d1 , d2, . . . , dn. Andaikan v adalah sebuah daun di T dengan derajat besesuaian dengan di untuk suatu i = 1, 2, . . . , n. Tanpa kehilangan keumuman pembuktian kita misalkan v bersesuaian dengan deraja dn . Titik v bertetangga dengan sebuah titik vj dengan derajat dj ≥ 2, dan titik yang lainnya merupakan kandidat bagi titik yang bertetangga dengan v. Hal ini berakibat bahwa T (n; d1 , . . . , dn) =



n−1 X



T (n − 1; d1, . . . , dj − 1, . . ., dn−1 ).



(10.1)



j=1



Sekarang kita perhatikan kembali sifat dari koefisien multinomial dalam ekspansi  X n n (x1 + x2 + · · · + xk ) = xr1 xr2 · · · xrkk (10.2) r 1 , r 2, . . . , rk 1 2



dimana jumlahan pada persamaan (10.2) dilakukan atas semua solusi bulat tak negatif dari persamaan r1 + r2 + · · · + rk = n. Karena (x1 + x2 + · · · + xk )n = (x1 + x2 + · · · + xk )n−1 (x1 + x1 + · · · + xk ), maka   X  k  n n−1 = . (10.3) r1 , r2 , . . ., rk r1 , r2 , · · · , ri − 1, · · · , rk i=1



Untuk n = 3 tidak sulit untuk memperlihatkan bahwwa   n−2 T (n; d1, . . . , dn ) = . d1 − 1, d2 − 1, . . . , dn − 1



(10.4)



10.3 Pohon Perentang Minimum



229



Perhatikan bahwa ekspresi pada sisi kiri dan sisi kanan dari persamaan (10.4) memenuhi relasi rekurensi yang sama (dalam hal ini rekurensi pada persamaan (10.1) dan (10.3)), maka dngan induksi persamaan (10.4) berlaku untuk semua n. Pada persamaan (10.2) gantikan n dengan n − 2, k dengan n, ri dengan di − 1 dan xi = 1, maka kita peroleh  X n−2 n−2 n = d1 − 1, d2 − 1, . . . , dn − 1 X = T (n; d1, d2 , . . . , dn).



Jadi banyaknya pohon atas n ≥ 3 titik adalah nn−2 . Sehingga banyaknya pohon perentang dari graf lengkap Kn adalah nn−2 . 



10.3 Pohon Perentang Minimum Sekelompok mahasiswa sedang melaksanakan kuliah kerja nyata di sebuah daerah terpencil. Masalah yang dihadapi oleh masyarakat adalah ketiadaan prasarana listrik. Untuk itu mahasiswa bermaksud membuat proposal untuk membangun jaringan listrik yang menghubungkan beberapa desa terpencil. Persoalan yang mereka hadapi adalah pada ruas jalan mana kabel harus dibentangkan agar setiap desa mendapatkan aliran listrik dan biaya pengadaan kabel seminimal mungkin? Persoalan mahasiswa ini dapat dimodelkan dengan menggunakan graf. Masing-masing desa direpresentasikan sebagai sebuah titik dan ruas jalan yang menghubungkan dua desa direpresentasikan sebagai sebuah sisi, dimana setiap sisi mempunyai bobot yang berbanding lurus dengan panjang ruas jalan. Graf yang demikian disebut sebagai sebuah graf berbobot, yakni sebuah graf G(V, E) bersama dengan fungsi bernilai nyata w : E → R. Untuk setiap sisi {u, v} di E(G) nilai dari w({u, v} disebut sebagai bobot dari sisi {u, v}. Agar setiap desa mendapat aliran listrik, maka ruas jalan harus dipilih sehingga ruas-ruas jalan terpilih membentuk sebuah pohon perentang dengan total panjang ruas jalan seminimal mungkin. Jadi persoalan berubah menjadi persoalan menentukan pohon perentang dengan total bobot sisi yang minimum. Persoalan ini dikenal sebagai persoalan pohon perentang minimum. Pada gambar berikut diberikan sebuah graf terhubung berbobot beserta dengan sebuah pohon perentang minimum.



230



Bab 10: Pohon



6



v5



u @4 @



2



4



u



2 @u



3



v3



u



v1



v6



5



uv4 3 @ 4@ @u



v2



v5



u @4 @ 3 2 @u



v3



v6 u



2 uv4



3



u



u



v1



v2



Gambar 10.4 Graf berbobot dan pohon perentang minimum



Berikut ini kita diskusikan beberapa cara untuk menentukan sebuah pohon perentang minimum. Kita mulai dengan Algoritma Kruskal yang pada dasarnya membangun sebuah pohon perentang dengan cara pada setiap iterasi algoritma memilih sisi dengan bobot terkecil yang tidak membentuk cycle dengan sisi-sisi yang terpilih pada iterasi sebelumnya. Karena setiap pohon dengan n titik memiliki tepat n − 1 buah sisi, maka algoritma berhenti setelah terpilih n − 1 buah sisi. Algoritma Kruskal Input: Graf terhubung G dengan bobot w : E(G) → R Output : Sebuah pohon perentang minimum T . 1. Urutkan sisi-sisi sehingga w(e1 ) ≤ w(e2 ) ≤ · · · ≤ w(em ). 2. Definisikan T := (V (G), ∅). 3. For i := 1 to m If T + ei tidak memuat cycle T := T + ei



Berikut ini kita diskusikan aplikasi dari Algoritma Kruskal dalam menentukan pohon perentang minimum dari graf terhubung berbobot pada Gambar 10.4 Contoh Kita perhatikan graf terhubung berbobot G pada Gambar 10.4. Bila sisi-sisi dari G diurutkan dalam urutan v1 v5 , v4 v6 , v2 v6 , v3 v4 , v2 v4 , v3 v5 , v1 v3 , v1 v2 , v5 v6 maka dalam setiap iterasi diperoleh subgraf seperti pada Gambar 10.5.



231



10.3 Pohon Perentang Minimum



vt5



vt6 t



v3 t



v3 t



vt5



vt5



v3



i=3



@ @ @t



v3



t



v1



v2



vt6 tv4 t



t



v2



i = 4, 5



t



vt5



tv4



t



tv4



t



v1



vt6



v2



vt6 t



v2



i=2



v3



i=1



vt5



t



t



t



tv4



t



tv4



t



v1



vt6 v3



v1



t



v2



t



vt6



tv4



v1



v1



vt5



i = 6, 7, 8, 9



v2



Gambar 10.5 Pembentukan pohon perentang minimum dengan Algoritma Kruskal



Bila sisi-sisi dari G diurutkan dalam urutan v1 v5 , v4 v6 , v2 v6 , v3 v4 , v2 v4 , v1 v3 , v3 v5 , v1 v2 , v5 v6 maka Algoritma Kruskal akan menemukan pohon perentang minimum seperti pada Gambar 10.5. vt5



vt6 t



v3 t



v1



tv4 t



v2



Gambar 10.6 Pohon perentang minimum berbeda



Dari contoh di atas kita ketahui bahwa mungkin saja terdapat lebih dari satu pohon perentang minimum dalam sebuah graf ter-



232



Bab 10: Pohon



hubung berbobot. Pohon perentang minimum yang dihasilkan oleh Algoritma Kruskal sangat bergantung pada pengurutan sisi-sisi dari graf terhubung. Teorema Algoritma Kruskal menghasilkan sebuah pohon perentang minimum dalam sebuah graf berbobot terhubung



Bukti. Andaikan G adalah sebuah graf berbobot terhubung atas n titik, dan misalkan T adalah sebuah subgraf yang dihasilkan oleh Algoritma Kruskal. Karena penggantian T := T + ei di langkah 3 pada algoritma dilakukan bila sisi ei tidak membentuk cycle dengan sisi-sisi sebelumnya, maka T adalah sebuah pohon perentang dari G, katakan dengan E(T ) = {e1 , e2 , . . . , en−1 }. Perhatikan dalam hal ini w(e1 ) ≤ w(e2 ) ≤ · · · ≤ w(en−1 ). Sehingga bobot dari pohon T adalah w(T ) =



n−1 X



w(ei).



i=1



Kita perlihatkan bahwa T adalah sebuah pohon perentang minimum dari G. Andaikan sebaliknya bahwa T bukan sebuah pohon perentang minimum. Maka di antara semua pohon perentang minimum dari G terdapat pohon perentang minimum, katakan H, yang mempunyai banyaknya sisi sekutu dengan T adalah maksimum. Sekarang pohon perentang T dan H tidak identik, maka T mempunyai sedikitnya satu sisi yang tidak berada di H. Misalkan ej , j = 1, 2, . . .n − 1 adalah sisi pertama dari T yang tidak berada di H. Definisikan H1 = H + ej , maka H1 mempunyai tepat satu cycle, katakan C. Karena T tidak mempunyai cycle, terdapat sisi e0 di C yang tidak berada di T . Karena e0 adalah sebuah sisi dari cycle C, T1 = H1 − e0 adalah sebuah pohon perentang dan w(T1 ) = w(H) + w(ej ) − w(e0 ). Karena H adalah sebuah pohon perentang minimum, w(H) ≤ w(T1). Akibatnya w(e0 ) ≤ w(ej ). Oleh Algoritma Kruskal, sisi ej adalah



10.3 Pohon Perentang Minimum



233



sebuah sisi dengan bobot minimum sehingga subdigraf h{e1 , e2 , . . . , ej−1 }i ∪ {ej } tidak memuat cycle. Tetapi subgraf h{e1 , e2 , . . . , ej−1 , e0 }i adalah subgraf dari H karenanya tidak memuat cycle, jadi w(ej ) ≤ w(e0 ). Jadi w(T1 ) = w(H), yang berarti bahwa T1 adalah sebuah pohon perentang minimum dari G. Tetapi T1 mempunyai sisi sekutu dengan H yang lebih banyak berbanding dengan sisi sekutu T dan H. Kontradiksi dengan asumsi bahwa Hadalah pohon perentang minimum dengan sisi sekutu dengan T adalah maksimum. Jadi T adalah sebuah pohon perentang minimum.  Untuk setiap ei ∈ E(G), bagaimana kita mendeteksi apakah T + ei pada Langkah 3 Algoritma Kruskal membentuk sebuah cycle atau tidak? Perhatikan proses pembentukan pohon perentang minimum pada Gambar 10.4. Pada awalnya (Langkah 2) subgraf terdiri dari m komponen terhubung. Pada setiap iterasi ketika T + ei tidak memuat cycle, maka komponen terhubung berkurang dengan satu. Perhatikan juga bahwa T + ei memuat cycle bila kedua titik ujung dari sisi ei berada di sebuah komponen dari T . Karena Akgritma Kruskal didasarkan pada informasi mengeai sisi, dalam implementasinya kita gunakan struktru data matriks sisi. Dalam hal ini matriks sisi terdiri dari tiga kolom dengan kolom pertama berisi titik ujung sebuah sisi, kolom kedua berisi titik ujung lainnya, dan kolom ketiga berisi bobot dari sisi. Untuk mendeteksi apakah T +ei memuat cycle perlu kita definisikan sebuah array ”komponen” dengan panjang n untuk mendeteksi sebuah titik berada di komponen terhubung tertentu. Pada awalnya komponen(i) = i Bila e = {u, v} adalah sebuah sisi dengan komponen(u) 6= komponen(v), maka u dan v tidak berada di komponen yang sama. Akibatnya T +e tidak memuat cycle. Sehingga sisi e terpilih oleh Algoritma Kruskal. Hal ini berakibat terjadi perubahan status komponen, yakni sekarang haruslah komponen(u) = komponen(v).



234



Bab 10: Pohon



Selanjutnya semua titik yang terletak dikomponen yang sama dengan titik u, dan semua titik yang terletak di komponen yang sama dengan titik v harus berada di sebuah komponen baru dengan titik-titik yang lebih banyak. Berikut diberikan sebuah code program dalam MATLAB untuk menentukan sebuah pohon perentang minimum dari graf terhubung berbobot. function [pohon,bobot]=kruskal(matriks_sisi,titik) [banyak_sisi,kolom_sisi]=size(matriks_sisi); %urutkan sisi berdasarkan bobotnya sisi_sort=sortrows(matriks_sisi,kolom_sisi); %inisiasi awalnya terdapat n buah komponen komponen=zeros(1,titik); for i=1:titik komponen(i)=i; end %inisiasi awalnya T adalah pohon kosong pohon_hasil=zeros(titik-1,2); total_bobot=0; sisi_terpilih=0; % seleksi sisi yang terpilih ke dalam pohon for sisi=1:banyak_sisi ujung_kiri=sisi_sort(sisi,1); ujung_kanan=sisi_sort(sisi,2); %cek sisi berada di komponen berbeda if komponen(ujung_kiri) ~= komponen(ujung_kanan) total_bobot=total_bobot+sisi_sort(sisi,3); sisi_terpilih=sisi_terpilih+1; pohon_hasil(sisi_terpilih,:)=sisi_sort(sisi,1:2); temp=komponen(ujung_kanan); % masukan titik ujung sisi terpilih ke %komponen yang sama komponen(ujung_kanan)=komponen(ujung_kiri); for i=1:titik if (komponen(i)==temp) komponen(i)=komponen(ujung_kiri); end end end



10.3 Pohon Perentang Minimum



235



end bobot=total_bobot; pohon=pohon_hasil;



Berikut ini kita diskusikan Algoritma Prim. Bila Kruskal membangun pohon perentang dengan memilih sisi yang tidak membentuk cycle, maka Prim membangun pohon sehingga pada setiap iterasi algoritma menambahkan titik baru ke pohon pada iterasi sesebelumnya. Algoritma Prim dapat dituliskan sebagai berikut



Algoritma Prim 1. Pilih titik v ∈ V (G). Set T := (V (G), ∅), dan V S := {v} 2. For i=1 to |V (G)| − 1 Pilih sisi bobot terkecil e = {u, w}, u ∈ V S, w ∈ V (G) − V (S) V S := V S ∪ {w} T := T + e



Contoh Kita perhatikan kembali graf terhubung berbobot pada Gambar 10.4. Kita aplikasikan Algorima Prim dalam membangun sebuah pohon perentang minimum. Algoritma kita mulai dengan V S = {v1 }. Subpohon yang diperoleh pada setiap iterasi adalah seperti pada Gambar 10.7.



236



Bab 10: Pohon



vt5



vt6 t



v3



tv4



t



vt6 v3



vt5



vt6 t



v3



vt5



i=4



i=3



vt5 tv4



t



t



v1



v2



vt6 v3



t



tv4 t



t



v2



v2



vt6



t



v1



tv4



t



v1



i=1



v3 t



i=2



t



t



v2



tv4



t



v1



tv4



t



v1



v3 v2



vt5



vt6 t



t



v1



t



vt5



i=5



v2



Gambar 10.7 Pembentukan pohon perentang minimum dengan Algoritma Prim



Teorema Algoritma Prim menghasilkan sebuah pohon perentang minimum dalam sebuah graf berbobot terhubung



Bukti. Andaikan G adalah sebuah graf terhubung berbobot. Karena pada setiap iterasi Algoritma Prima menambahkan sisi yang menghubungkan titik pada subpohon dengan titik yang tidak berada di subpohon, maka Algoritma berakhir dengan sebuah pohon perentang T . Kita perlihatkan bahwa T adalah sebuah pohon perentang minimum. Andaikan sebaliknya bahwa T bukanlah sebuah pohon perentang minimum. Misalkan H adalah sebuah pohon perentang minimum dari G yang mempunyai sisi sekutu dengan T maksimum. Misalkan pohon T yang dihasilkan oleh algoritma adalah T = h{e1 , e2 , . . . , en−1 }i



237



10.3 Pohon Perentang Minimum



dengan ej , j = 1, 2, . . ., n − 1 adalah sisi ke j yang terpilih oleh algoritma Prim. Jadi n−1 X w(T ) = w(ej ). j=1



Misalkan ei adalah sisi pertama dari T yang tidak berada di H. Untuk i = 1 kita definisikan U = {u} dan untuk i ≥ 2 misalkan U adalah himpunan titik dari subgraf yang disebabkan sisi e1 , e2 , . . . , ei−1 . Yakni U = V (h{e1 , e2 , . . . , ei−1 }i). Karena H dalah sebuah pohon, maka graf H + ei memuat sebuah cycle tunggal. Perhatikan bahwa ei menghubungkan titik di U dengan titik di V (T ) − U . Namun perhatikan bahwa C memuat sisi katakan e0 yang menghubungkan U dengan V (T ) − U . Akibatnya T1 = H + ei − e0 adalah sebuah pohon perentang. Karena T dikonstruksi dengan menggunakan Algoritma Prim, maka w(ei ) ≤ w(e0 ). Jadi w(T1) ≤ w(H). Karena H adalah sebuah pohon perentang minimum, demikian juga halnya dengan T1 . Sekarang kita peroleh pohon perentang minimum T1 yang mempunyai sisi sekutu dengan T yang lebih banyak dengan sisi sekutu antara H dengan T . Hal ini merupakan sebuah kontradiksi. Jadi mestilah T adalah sebuah pohon perentang minimum.  Berikut diberikan implementasi dari Algoritma Prim dalam MATLAB. Pada implementasi ini kita gunakan struktur data yang berupa matriks ketetanggaan. Karena kita mempunyai graf berbobot, maka pendefinisian matriks ketetanggaan A = (aij ) dari G adalah sebagai ( w({vi, vj }), bila {vi , vj } ∈ E(G) aij = 0, bila sebaliknya. Tetapi karena persoalan kita adalah persoalan minimisasi, maka sebaiknya matriks ketetanggan graf berbobot G didefinisikan dengan ( w({vi, vj }), bila {vi , vj } ∈ E(G) aij = ∞, bila sebaliknya.



238



Bab 10: Pohon



function [bobot,pohon]=prim(matriks_tetangga) [baris,kolom]=size(matriks_tetangga); %inisiasi titik 1 ada di pohon Set_ttk_pohon=zeros(1,baris); Set_ttk_pohon(1)=1; %semua titik ada di luar pohon kecuali titik 1 Set_ttk_luar=ones(1,baris); Set_ttk_luar(1)=0; bobot=0; %inisiasi pohon kosong pohon=zeros(baris-1,3); % pilih sisi dengan bobot tekecil ke pohon for k=1:baris-1 maks=inf; for i=1:baris for j=1:baris %pastikan satu ttk diluar satu di dlm pohon if Set_ttk_luar(i)~=0 & Set_ttk_pohon(j)~=0 temp=matriks_tetangga(i,j); if temp