Carilah permasalahan yang berkaitan tentang Minimum spanning tree

Academia.edu no longer supports Internet Explorer.

Table of Contents Show

2.8 Aplikasi Minimum Spanning Tree
2.9 Algoritma Kruskal
2.10 Algoritma Prim
Video yang berhubungan

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser.

minimum mempunyai terapan yang luas dalam praktek. Misalkan Pemerintah akan membangun jalur kereta api yang menghubungkan sejumlah kota, membangun jalur rel kereta api biaya nya mahal, karena itu pembangunan jalur ini tidak perlu menghubungkan langsung dua buah kota, tetapi cukup membangun jalur kereta seperti pohon merentang. Karena di dalam graf mungkin saja terdapat lebih dari satu pohon merentang, harus dicari pohon merentang yang mempunyai jumlah jarak terpendek, dengan kata lain harus dicari pohon merentang minimum. d

2.8 Aplikasi Minimum Spanning Tree

Aplikasi yang sering dipakai dalam graf berlabel adalah mencari pohon rentang dengan total bobot seminimum mungkin atau disebut pohon merentang minimum. Jika semua jaringan listrik dibuat terlalu banyak maka biaya akan boros. Beberapa 15 20 30 55 5 35 10 50 5 40 20 10 15 b e f g h c c h e f g 25 25 30 a 45 Gambar 2.2 a Graf yang menyatakan jaringan jalur rel kereta api. Bobot pada tiap sisi menyatakan panjang rel kereta api x 100 km b Pohon merentang yang mempunyai jumlah jarak minimum Universitas Sumatera Utara jalur yang menghubungkan 2 kota secara langsung tidak perlu dibuat karena kota- kota tersebut tetap dapat teraliri listrik secara tidak langsung, yaitu dengan melalui kota lain sedemikian hingga total biaya pemasangan jaringan listrik seminimum mungkin. Atau dengan kata lain, mencari pohon rentang dengan total bobot seminimum mungkin. Cara yang paling sederhana adalah dengan mendaftarkan semua pohon rentang yang mungkin dibuat dan menghitung total bobot tiap-tiap pohon rentang. Selanjutnya dipilih pohon rentang dengan total bobot yang paling kecil. Metode itu tidak efisien, terutama pada graf yang cukup besar karena terdapat banyak sekali pohon rentang yang dapat dibuat.

2.9 Algoritma Kruskal

Algoritma Kruskal adalah algoritma dalam teori graph yang menemukan suatu pohon rentang minimum untuk terhubung dalam graf berbobot . Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan.. Jika grafik tidak terhubung, maka menemukan hutan rentang minimum pohon rentang minimum untuk setiap komponen terhubung . Algoritma Kruskal adalah contoh dari algoritma rakus . Algoritma ini pertama kali muncul dalam Prosiding American Mathematical Society , hal 1956. Algoritma lain untuk masalah ini termasuk Algoritma Prim , Reverse- Hapus algoritma , dan algoritma Borůvkas. Pada Algoritma Kruskal, sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan Universitas Sumatera Utara T adalah sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi- sisi sudah diurut berdasarkan bobot membentuk hutanforest, masing-masing pohon di hutan hanya berupa satu buah simpul. Hutan tersebut dinamakan hutan merentang spanning forest. Sisi dari graf G ditambahkan ke T jika ia tidak membentuk siklus di T. Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit. Sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya, yaitu : 1. T masih kosong 2. Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T. Masukkan e ke dalam T. 3. Ulangi langkah 2 sebanyak n-1 kali. Contoh 2.1 Carilah pohon merentang minimumnya dengan algoritma Kruskal. Penyelesaian: Sisi-sisi graf diurut menaik berdasarkan bobotnya: Langkah-langkah pembentukan pohon merentang minimum diperlihatkan pada Tabel 2.1. Bobot pohon merentang minimum ini adalah 10 + 25 + 15 + 20 + 25 = 105 Sisi 1,2 3,6 4,6 2,6 1,4 3,5 2,5 1,5 2,3 5,6 Bobot 10 15 20 25 30 35 40 45 50 55 Universitas Sumatera Utara Langkah Sisi Bobot Pohon Merentang 1 1,2 10 2 3,6 15 3 4,6 20 4 2,6 25 5 1,4 30 6 3,5 35 Tabel 2.1 Pembentukan pohon merentang minimum dengan algoritma Kruskal 1 2 3 4 5 6 1 2 1 2 3 4 5 6 1 2 3 4 5 6 1 3 2 5 4 6 1 2 3 5 4 6 ditolak Universitas Sumatera Utara Ada satu lagi algoritma yang membangun pohon merentang minimum yang hampir mirip dengan algoritma Kruskal yaitu algoritma Prim. Dibawah ini akan dijelaskan tentang algoritma Prim.

2.10 Algoritma Prim

Minimum spanning tree adalah suatu pohon yang dapat didefinisikan dengan sebuah graf. Graf berarah dan graf tidak berarah adalah subgraf yang setiap node/simpulnya terkoneksi satu sama lain. Sebuah graf, dapat memberikan pohon rentang yang berbeda. Pada setiap ruas/edge, kita dapat memberikan suatu bobot untuk menentukan suatu nilai. Setiap bobot tersebut akan dibandingkan dengan bobot yang lain yang mengarah pada simpul berikutnya, selanjutnya akan dipilih bobot yang terkecil. Hal ini akan terus dilakukan sampai menuju simpul tujuan.

Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum.

Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route), kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan merentangkan (menghubungkan) semua titik dalam jaringan tersebut pada total jarak (panjang) minimum.

Contoh Minimum Spanning Tree.

Salah satu contohnya adalah perusahaan TV kabel yang memasang kabel ke lingkungan baru. Jika dibatasi untuk mengubur kabel hanya di sepanjang jalan tertentu, maka ada graf yang mewakili suatu jalur. Beberapa jalur tersebut mungkin akan lebih lama, karena memerlukan kabel yang akan dikubur lebih dalam, sehingga membutuhkan biaya yang lebih mahal. Dengan adanya minimum spanning tree, maka akan didapatkan total biaya yang lebih rendah.

Sebagai contoh lain, ada sebuah gedung Istec Corporation yang baru memiliki beberapa ruangan dan tiap ruangan membutuhkan 1 lubang aliran listrik (atau biasa disebut sebagai steker). Teknisi listrik akan menyalurkan listrik dari ruang bagian depan sampai keseluruh ruangan dengan total panjang kabel yang seefisien mungkin. Adapun jarak antar ruangan dapat digambarkan dalam gambar jaringan berikut ini, sedangkan ruang bagian depan digambarkan sebagai node-1

Karena node-1 adalah ruangan terdepan yang menjadi sumber aliran listrik utama, maka node-1 akan dijadikan sebagai patokan dalam jaringan. Node yang paling dekat dengan node-1 adalah node dengan jarak 2 meter, sehingga kita hubungkan node 1 dengan node-3.

Kemudian kita lihat node-node terdekat yang belum terhubung dengan node 1 dan 3, yaitu node 7, 6 dan 2. Yang terdekat dengan node 3 adalah node 7 dengan jarak 3 meter. Kemudian node 3 dan node 7 dapat dihubungkan.

Node yang belum terhubung terdekat dengan node 1, 3 dan 7 adalah node 6 dengan panjang 2 meter.

Node yang belum terhubung dan dekat dengan node 1,3,7 dan 6 adalah 5 dan 2. Node 5 dapat terhubung dengan node 6 dengan jarak 3 meter, sedangkan node 3 dapat dihubungkan dengan node-1 dengan jarak 3 meter.

Karena seluruh node telah terhubung atau telah terkait dalam satu jaringan, maka solusi di atas telah optimum. Jadi teknisi listrik dapat memulai merentangkan kabelnya dengan menghubungkan node 1 – 2, 1 – 3, 3 – 7, 6 – 7, 5 – 6, 4 – 5, 6 – 8, 8 – 9

Panjang kabel yang dibutuhkan adalah : 21 meter.

Cara membuat minimum spanning tree pada jaringan diatas :

Langkah-langkah dalam membuat spanning tree adalah sebagai berikut:

a. Langkah pertama, cari nilai cost yang terkecil. Dengan cost yang kecil maka biaya yang dibutuhkan lebih murah. Karena cost diatas yang terkecil nilainya 2 maka harus didahulukan terlebih dahulu.

b. Langkah kedua, mencari nilai cost yang terkecil pula. Terdapat 3 nilai edge yang kecil yaitu antara CE, DE, dan AF. Kita boleh mempergunakan salah satu dari edge tersebut. Saya mengambil edge antara DE.

c. Langkah ketiga, sekarang edge yang costnya terkecil tinggal CE dan AF. Untuk mencari nilai spanning tree harus membentuk cabang/pohon maka saya mempergunakan edge yang AF, karena jika saya mengabil edge CE maka spanning tree akan membentuk sebuah loop. Secara teori jika spanning tree membentuk sebuah loop maka costnya menjadi lebih besar. Oleh karena itu saya mengambil edge AF agar costnya menjadi murah.

d. Langkah keempat, mencari nilai cost yang lebih murah. Karena nilai cosnya bernilai 4 sudah tidak ada, maka saya mencari alternative cost yang lebih murah. Terdapat edge BC, BE, FE. Maka saya mengambil edge BC, FE, atau BE secara sembarang. Saya mengambil edge BC.

e. Langkah kelima, hasil akhir dari spanning tree sudah terlihat yaitu tinggal menghubungkan edge FE. Karena nilai costnya yang paling murah dibandingkan dengan nilai cost yang lainnya.

f. Kesimpulan, jika kita ingin membuat route spanning tree kita yang kita harus lakukan adalah mecari nlai cost yang terkecil, lalu jangan membuat suatu loop karena akan terjadi pemborosan.

http://firstqien.blogspot.co.id/2012/02/spanning-tree.html