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 :

Apa itu Spanning Tree ?

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

Contoh:

Spanning Tree dari Graf G :

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 :

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.

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)

Sehingga Graf G diatas menjadi sebagai berikut :

Sehingga Graf G tersebut menjadi sebagai berikut :

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.

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 ??

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 :