Mencari Minimum Spanning Tree dengan Algoritma Solin

Apa itu Tree

Pohon (Tree) didefinisikan sebagai graph terhubung yang tidak mengandung sirkuit.

Penting!!

Suatu Graf  G adalah Pohon (Tree) jika dan hanya jika terdapat satu dan hanya satu jalur diantara setiap pasang simpul dari Graf G.

Contoh :

contoh tree

Apa itu Spanning Tree ?

adalah suatu subgraf dari graf G yang  mengandung semua simpul dari G dan merupakan suatu pohon.

Contoh:

Contoh Graf G

Spanning Tree dari Graf G :

Contoh spanning tree dari graff g diatas

Minimum Spanning Tree ?

Apabila G suatu Graf berbobot (Suatu  Network), maka pohon rentangan minimal (Minimum Spanning Tree) dari graf adalah pohon rentangan (Spanning Tree) dengan jumlah bobot terkecil.

Algoritma Solin ?

Algoritma Solin menentukan pohon merentang minimum (Minimum Spanning Tree) dengan cara melakukan penghapusan sisi-sisi (Ruas) yang tidak menyebabkan graf menjadi tidak terhubung atau membentuk sirkuit. Penghapusan tersebut dimulai dari sisi atau ruas yang memiliki bobot terbesar hingga terkecil.Penghapusan dilakukan setelah sebelumnya sisi-sisi(Ruas) pada graf diurutkan berdasarkan bobotnya dari besar ke kecil.

Algoritma Solin dapat dituliskan secara terurut sebagai berikut:

  1. Urutkan ruas dari Graf G menurut bobotnya, dari besar ke kecil.
  1. Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan, dengan  ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf menjadi  tidak terhubung atau membentuk sirkuit.

Contoh Kasus

Perusahan Listrik Negara ingin merentangkan jaringan kabel listrik, untuk menghubungkan lokasi tertentu, dengan ketentuan bahwa kabel listrik tersebut harus di pergunakan SEPENDEK-PENDEK NYA.

Kita asumsikan bahwa satuan bobot untuk jarak antar lokasi yang dipakai adalah KM (Kilo Meter), dan karena kabel listrik ini bahannya dengan kualitas yang sangat bagus, maka per meternya, seharga Rp. 1.000.000,- (Satu juta rupiah).

Lokasi tersebut di gambarkan dalam Graf G berbobot sebagai berikut :

Graf G

Penyelesaian :

Kita akan menggunakan Algoritma Solin untuk mencari Minimum Spanning Tree dari Graf G diatas,

  1. Urutkan ruas dari Graf G menurut bobotnya, dari besar ke kecil.
tabel bobot dan ruas

2. Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan, dengan ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf menjadi  tidak terhubung atau membentuk sirkuit.

  1. Bobot 17 >>>> AD dan BC

Ruas AD dihapus karena membentuk Sirkuit (ADB|ACD), dan Ruas BC juga dihapus karena membentuk sirkuit (BCD|BCA)

Penghapusan ruas yang membentuk sirkuit

Sehingga Graf G diatas menjadi sebagai berikut :

Gambar 1
2. Bobot 15 >>>> AB dan CD
Ruas AB dihapus karena membentuk sirkuit (ABDC)
Penghapusan ruas yang membentuk sirkuit

Sehingga Graf G tersebut menjadi sebagai berikut :

Gambar 3

Ruas CD tidak dihapus karena jika dihapus graf akan terputus.

3. Bobot 10 >>>> AC dan BD

Ruas AC dan ruas BD tidak dihapus, karena jika dihapus graf akan terputus.

Gambar 3 adalah Minimum Spanning Tree dari Graf G diatas

Maka, Gambar 3, adalah Minimum Spanning Tree untuk Graf G diatas, dengan bobot nilai :

10 + 10 + 15 = 35

Artinya :

35 Km = 35.000 M, sedangkan harga 1 meter kabel adalah Rp. 1.000.000,- maka :
35.000 x 1.000.000 = Rp. 35.000.000.000,- (Tiga puluh lima milyar rupiah).

Biaya diatas adalah biaya terkecil untuk membangun jaringan kabel listrik dari Graf G diatas. Dengan MST nya.

Tetapi bagaimana jika Gambar MST nya adalah sebagai berikut ?

Ruas Pertama dengan bobot terbesar tidak boleh dihapus ??

MST yang tidak menghapus bobot terbesar karena alasan ruas pertama tidak boleh dihapus

Berapa kira-kira biaya yang akan dikeluarkan ya ??

10 + 10 + 17 = 37

Artinya :

37Km = 37.000M, sedangkan harga 1 meter kabel adalah Rp. 1.000.000,- maka

37.000 x 1.000.000 = Rp. 37.000.000.000,- (Tiga puluh tujuh milyar rupiah)
Wah, selisih Rp. 2.000.000.000,- (Dua milyar rupiah) ???

Dengan uang 2 Milyar rupiah, daripada dibuang karena kesalahan fatal dalam memasang kabel listrik, akan lebih bermanfaat untuk biaya pendidikan.

Referensi :

1. Minimum Spanning Tree/ Pohon Rentangan Minimal, Abdus Syakur, disini, diakses pada hari Selasa 27 April 2010 pada Pukul 23.00 Wita
2. Pohon (Tree), Yuni Dwi Astuti ST, disini, diakses pada hari Rabu 28 April 2010 pada pukul 01.00 Wita
3. Pengertian Graf, Wikipedia Indonesia, disini, diakses pada hari Selasa 27 April 2010 pada pukul 23.30 Wita

2 thoughts on “Mencari Minimum Spanning Tree dengan Algoritma Solin”

  1. duuhh
    pusing bgd nih. mata kuliah algoritma…
    bpak, aku mw nanya doonk… manfaatny dari minimmum spaning tree..??

    Hendra :
    Jangan panggil bapak dong, kelihatan tua jadinya saya.. hahahah
    manfaatnya untuk mencari lintasan terpendek dari suatu graph tree. kalo di implementasikan ya sangat berguna sekali, contohnya adalah penarikan Kabel.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.