Sesi 2 Jenis-Jenis Graf Tertentu - 2 [PDF]

Citation preview

2. Jenis-jenis Graf Tertentu Ada beberapa graf khusus yang sering dijumpai. Beberapa diantaranya adalah sebagai berikut. a.



Graf Lengkap (Graf Komplit) Graf lengkap ialah graf sederhana yang setiap titiknya mempunyai



sisi ke semua titik lainnya atau semua titiknya bertetangga dengan semua titik lainnya. Graf lengkap dengan 𝑛 titik dilambangkan dengan 𝐾𝑛 .



𝐾1



𝐾2



𝐾3



𝐾4



Gambar 6. Graf lengkap 𝐾𝑛 b. Graf Bipartisi Graf bipartisi 𝐺 adalah graf yang himpunan titiknya dapat dikelompokkan menjadi dua himpunan bagian 𝑉1 dan 𝑉2 , sedemikian sehingga setiap sisi di dalam 𝐺 menghubungkan sebuah titik di 𝑉1 ke sebuah titik di 𝑉2 , dan dinyatakan sebagai 𝐺 (𝑉1 , 𝑉2 ). Dengan kata lain, setiap pasang titik 𝑉1 (demikian pula dengan titik-titik di 𝑉2 ) tidak bertetangga. Apabila setiap titik di 𝑉1 bertetangga dengan semua titik di 𝑉2 , maka 𝐺 (𝑉1, 𝑉2 ) disebut sebagai graf bipartisi lengkap. Jika 𝑉1 terdiri dari 𝑚 titik dan 𝑉2 terdiri dari 𝑛 titik, maka graf bipartisi lengkap dilambangkan dengan 𝐾𝑚,𝑛 . 𝑉1



𝑉2



𝑉1



𝑉2



(𝑎)



(𝑏)



Gambar 7. (a) graf bipartisi, (b) graf bipartisi lengkap 𝐾2,2



13



c.



Graf Teratur (Graf Reguler) Graf yang setiap titiknya mempunyai derajat yang sama disebut graf



teratur atau graf reguler. Apabila derajat setiap titik adalah 𝑟, maka graf tersebut disebut sebagai graf teratur atau graf reguler derajat 𝑟 atau dapat ditulis graf teratur-𝑟 (graf reguler-𝑟). Jumlah sisi pada graf teratur adalah



𝑛𝑟 2



.



Contoh graf teratur ditunjukkan di bawah ini.



Gambar 8. Graf teratur-3 d. Graf Sikel Graf sikel adalah graf sederhana yang setiap titiknya berderajat dua. Graf sikel dengan n titik dilambangkan dengan 𝐶𝑛 . Contoh graf sikel ditunjukkan di bawah ini.



C3 e.



C4



C5



Graf Planar dan Graf Bidang Graf G disebut graf planar (planar graph) jika G dapat digambar



pada bidang datar sedemikan hingga sisi-sisinya tidak ada yang berpotongan kecuali mungkin pada titik-titik ujung dari sisi-sisi tersebut. Sedangkan graf bidang (plane graph) adalah graf yang digambar pada bidang datar sedemikan hingga sisi-sisinya tidak ada yang berpotongan kecuali mungkin pada titik-titik ujung dari sisi-sisi tersebut. Dengan demikian, graf planar adalah graf yang dapat digambar sebagai graf bidang. Graf bidang pasti graf planar tetapi sebaliknya tidak berlaku.



14



Gambar 𝐺1 , 𝐺2 , dan 𝐺3 adalah graf planar, tetapi 𝐺1 bukan graf bidang.



Perhatikan graf bidang G berikut. a e b



d c



f



Graf bidang G di atas membagi bidang menjadi 6 daerah yang masingmasing disebut “muka” (face), yaitu: muka a, muka b, muka c, muka d, muka e, dan muka f. Himpunan muka dari graf bidang G dinotasikan dengan 𝐹(𝐺). Untuk graf G di atas himpunan mukanya adalah 𝐹 (𝐺 ) = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓 }. Banyaknya sisi di G yang membatasi suatu muka f adalah dari G disebut derajat muka f tersebut dan dinotasikan 𝑑(𝑓). Jembatan (sisi pemutus) graf G dihitung dua kali dalam menghitung derajat muka. Sebuah sisi e di graf G disebut jembatan (sisi pemutus) jika penghapusan sisi e tersebut mengakibatkan subgraf G-e mempunyai komponen lebih banyak daripada graf G. Untuk graf G di atas derajat masing-masing muka adalah 𝑑 (𝑎) = 7, 𝑑 (𝑏) = 4, 𝑑 (𝑐 ) = 3, 𝑑(𝑑 ) = 3, 𝑑(𝑒) = 3, dan 𝑑 (𝑓 ) = 4.



f.



Graf Euler dan Graf semi-Euler Sebuah sirkuit di graf G yang memuat semua sisi G disebut sirkuit



Euler. Jika graf G memuat sirkuit Euler, maka graf G disebut graf Euler.



15



Sebuah jejak-buka yang memuat semua sisi graf disebut jejak Euler. Graf G disebut graf semi-Euler jika G memuat jejak Euler.



Teorema 5 Misalkan G graf terhubung. Graf G Euler jika dan hanya jika setiap titik G berderajat genap.



Teorema 6 Misalkan G graf terhubung. Graf G semi-Euler jika dan hanya jika G memuat tepat dua titik berderajat ganjil.



Untuk mencari sirkuit Euler pada graf Euler G, dimulai dari sembarang titik v di G dan akan berakhir di titik v tersebut juga. Jejak Euler pada graf semi-Euler, berawal di sebuah titik berderajat ganjil dan berakhir di sebuah titik berderajat ganjil lainnya. Berikut contoh graf Euler dan graf semi-Euler.



G2



G1



Gambar 9. 𝐺1 graf Euler dan 𝐺2 graf semi-Euler g.



Graf Hamilton dan Semi-Hamilton Misalkan G adalah sebuah graf. Sebuah sikel yang memuat semua



titik di G disebut sikel Hamilton. Jika G memuat sikel Hamilton, maka G disebut graf Hamilton. Sebuah lintasan yang memuat semua titik di G disebut lintasan Hamilton. Sebuah graf G disebut graf semi-Hamilton jika graf G bukan graf Hamilton dan graf tersebut memuat lintasan Hamilton. Perhatikan tiga graf di bawah ini.



16



Graf 𝐺1 tidak memuat lintasan Hamilton, 𝐺2 memuat lintasan Hamilton tetapi tidak memuat sikel Hamilton dan 𝐺3 memuat sikel Hamilton. Dengan demikian, 𝐺2 adalah graf semi-Hamilton dan 𝐺3 adalah graf Hamilton. h. Pohon Pohon (tree) adalah graf terhubung yang tidak memiliki sikel. Berikut adalah contoh-contoh pohon.



𝑇1



𝑇2



𝑇3



𝑇4



Sifat-sifat Pohon Misalkan G = (V, E) adalah graf sederhana dan banyak titiknya n buah. Pernyataan-pernyataan di bawah ini adalah ekivalen. 1) G adalah pohon. 2) Setiap pasang titik di G terdapat tepat satu lintasan. 3) G terhubung dan memiliki n – 1 buah sisi. 4) G tidak mengandung sikel dan memiliki n – 1 buah sisi. 5) G terhubung dan semua sisinya adalah jembatan.



Graf bobot (weighted graph) G adalah sebuah graf yang setiap sisinya dikaitkan dengan sebuah bilangan real. Bobot sisi e ditulis sebagai w(e). Bobot graf G, ditulis w(G), adalah jumlah bobot semua sisi di G. Graf bobot G pada Gambar 10 mempunyai bobot 𝑤(𝐺 ) = 2 + 3 + 2 + 1 = 8.



17



3



2



1 2



G Gambar 10. Graf bobot



Dari sebuah graf terhubung dapat diperoleh sebuah graf bagian yang memuat semua titik di G yang berupa pohon. Sebuah graf bagian yang memuat semua titik di G yang berupa pohon disebut pohon rentang (spanning tree). Graf pada Gambar 10 di atas kemungkinan pohon rentangnya adalah sebagai berikut.



3



2



1



3



2



1 2



T1



1 2



T2



T3



Masing-masing pohon rentang tersebut mempunyai bobot 𝑤(𝑇1 ) = 6, 𝑤 (𝑇2) = 5, dan 𝑤(𝑇3 ) = 6. Perhatikan bahwa pohon rentang 𝑇2 memiliki bobot minimal di antara pohon rentang-pohon rentang yang diperoleh dari G. Pohon rentang yang memiliki bobot minimal tersebut disebut pohon rentang minimal (minimum spanning tree). Untuk mendapatkan pohon rentang minimal dari sebuah graf bobot G di atas dengan cara: dicari semua pohon rentangnya, baru kemudian dihitung bobot masing-masing pohon rentang tersebut, dan yang punya bobot minimal itulah yang merupakan pohon rentang minimal. Cara mendapatkan pohon rentang minimal dengan cara seperti itu tentu tidak efektif dan efisen sebab membutuhkan pekerjaan dan waktu yang banyak. Untuk mencari sebuah pohon rentang minimal dari graf bobot G, pada bahasan ini akan digunakan dua algoritma, yaitu algoritma Kruskal dan algoritma Prim. Dengan menerapkan algoritma Kruskal atau algoritma Prim tersebut akan diperoleh sebuah pohon rentang minimal. Berikut penjelasan kedua algoritma itu. 18



Algoritma Kruskal Dalam algoritma ini, pertama pilih sisi di G yang memiliki bobot terkecil di antara sisi-sisi G yang bukan loop. Untuk menghindari sikel, dipilih dari sisi yang tersisa yang memiliki bobot terkecil yang tidak membentuk sikel dengan sisi yang telah terpilih. Ulangi lagi proses pengambilan sisi dengan bobot terkecil di antara sisi-sisi yang belum dipilih, asalkan tidak membentuk sikel dengan sisi yang telah terpilih. Jika graf tersebut memiliki 𝑛 titik, proses tersebut dihentikan setelah memilih 𝑛 − 1 sisi. Sisi-sisi tersebut membentuk graf bagian T yang tidak memiliki sikel dari G dan T adalah pohon rentang minimal dari G. Langkah-langkah tersebut dapat dituliskan sebagai berikut.



Algoritma Kruskal Langkah 1. Pilih 𝑒1 , sebuah sisi di G sehingga 𝑤(𝑒1 ) sekecil mungkin dan 𝑒1 bukan loop. Langkah 2. Jika sisi-sisi 𝑒1 , 𝑒2 , … , 𝑒𝑖 telah dipilih, lalu pilih sebuah sisi 𝑒𝑖+1, yang belum terpilih sedemikian sehingga (i) graf bagian



dari G yang dikonstruksi oleh sisi-sisi



𝑒1 , 𝑒2 , … , 𝑒𝑖+1 tidak memiliki sikel dan (ii) 𝑤(𝑒𝑖+1 ) adalah terkecil. Langkah 3. Jika G memiliki 𝑛 titik, hentikan langkah tersebut setelah memilih 𝑛 − 1 sisi. Jika belum terpilih 𝑛 − 1, ulangi langkah 2.



Algoritma Prim Pada algoritma ini untuk menemukan pohon rentang minimal, pertama dipilih sebarang titik 𝑣1 pada graf bobot G. Kemudian pilih satu sisi dengan bobot terkecil dari G yang bukan loop dan yang terkait dengan 𝑣1 , misalnya 𝑒1 = 𝑣1 𝑣2 . Kemudian pilih sisi dengan bobot terkecil di G yang terkait dengan 𝑣1 atau 𝑣2 tetapi titik ujung lain dari sisi tersebut adalah selain titik 𝑣1 atau 𝑣2 . Misalkan pilih sisi 𝑒2 = 𝑣𝑖 𝑣3 dengan 𝑖 ∈ {1,2} tetapi 𝑣3 ≠ 19



𝑣1 , 𝑣2 . Ulangi proses pengambilan sisi dengan bobot terkecil yang berujung di titik yang telah terpilih sebelumnya dan ujung lainnya dari sisi tersebut adalah titik dari G yang bukan ujung dari sisi yang sudah terpilih. Jika graf G memiliki n titik, dipilih sampai 𝑛 − 1 sisi. Langkah-langkah algoritma Prim tersebut adalah sebagai berikut. Algoritma Prim Langkah 1. Pilih sebarang titik 𝑣1 di G. Langkah 2. Pilih sebuah sisi 𝑒1 = 𝑣1 𝑣2 di G sehingga 𝑣2 ≠ 𝑣1 dan 𝑒1 memiliki bobot terkecil di antara sisi-sisi G yang terkait dengan 𝑣1 . Langkah 3. Jika sisi 𝑒1 , 𝑒2 , … , 𝑒𝑖 telah dipilih dengan titik-titik ujung dari sisi-sisi tersebut adalah titik-titik 𝑣1 , 𝑣2 , … , 𝑣𝑖+1 , selanjutnya pilih sisi 𝑒𝑖+1 = 𝑣𝑗 𝑣𝑘 dengan 𝑣𝑗 ∈ {𝑣1 , 𝑣2 , … , 𝑣𝑖+1 } dan 𝑣𝑘 ∉ {𝑣1 , … , 𝑣𝑖+1 } sedemikian sehingga 𝑒𝑖+1 memiliki bobot terkecil di antara sisi-sisi G yang salah satu ujung sisi tersebut di {𝑣1 , … , 𝑣𝑖+1 }. Langkah 4. Hentikan langkah tersebut setelah 𝑛 − 1 sisi telah dipilih. Jika tidak, ulangi langkah 3.



Contoh. Carilah sebuah pohon rentang minimal pada graf bobot G di bawah ini.



Penyelesian: Dengan menerapkan algoritma Kruskal atau Prim diperoleh sebuah pohon 20



rentang minimal T sebagai berikut.



Pohon rentang minimal T Bobot pohon rentang minimal T di atas adalah 𝑤(𝑇) = 𝑤(𝑒1 ) + 𝑤(𝑒2 ) + 𝑤(𝑒3 ) + 𝑤 (𝑒4 ) + 𝑤(𝑒5 ) = 2 + 1 + 1 + 3 + 3 = 10. Pada graf bobot G tersebut memuat bentuk pohon rentang minimal yang tidak tunggal. Untuk melancarkan penggunaan algoritma Kruskal atau Prim, coba Anda cari bentuk lainnya tersebut.



21