Pohon rentang minimum

struktur data, graf bagian dari suatu graf berbobot

Pohon rentang minimum atau pohon rentang berbobot minimum (bahasa Inggris: minimum spanning tree, MST) adalah himpunan bagian dari himpunan garis-garis (edge) suatu graf berbobot tak berarah yang menghubungkan semua titik tanpa membentuk siklus dan dengan total bobot minimum. Dengan kata lain, ini adalah pohon rentang yang total bobotnya minimum.

Suatu graf datar (planar) dan pohon rentang minimumnya. Tiap garis dilabeli dengan bobotnya yang kira-kira sebanding dengan jaraknya dalam gambar tersebut.

Ada beberapa kasus yang menggunakan pohon rentang minimum. Misalnya, perusahaan telepon mencoba untuk menghubungkan telepon-telepon rumah dengan kabel sehingga kabel yang dipakai sependek mungkin. Di beberapa tempat, mungkin dibutuhkan penggalian sehingga biayanya bertambah. Dengan kata lain, "bobot" garisnya bertambah. Satuan yang biasa dipakai dalam permasalahan ini adalah biaya (cost). Dalam konteks ini, pohon rentang minimum adalah jalur yang menggunakan kabel sependek mungkin atau dengan biaya serendah mungkin.

Peluang ketergandaan (multiplicity)

sunting

Jika ada n titik pada graf, tiap pohon rentang memiliki n − 1 garis.

Mungkin ada beberapa pohon rentang minimum dengan bobot yang sama. Untuk graf dengan bobot garis yang seragam, semua pohon rentang adalah minimum.

Keunikan

sunting
 
Gambar di atas menunjukkan bahwa mungkin ada lebih dari satu pohon rentang minimum dalam suatu graf. Pada gambar, dua pohon yang ada di bawah graf adalah dua kemungkinan pohon rentang minimum dari graf yang diberikan.

Jika tiap garis memiliki bobot yang berbeda, hanya ada satu pohon rentang minimum. Hal ini benar untuk banyak kasus di kehidupan nyata karena jarang ada dua bobot yang tepat sama. Hal ini juga berlaku untuk hutan rentang.

Bukti:

  1. Misalkan kebalikannya, yaitu ada dua MST yang berbeda: A dan B.
  2. Karena A dan B berbeda, meski memiliki nodus yang sama, setidaknya ada satu garis yang berada dalam salah satu pohon, tetapi tidak dalam pohon lainnya. Di antara garis-garisnya, misalkan e1 adalah garis dengan bobot terendah; pilihan ini unik karena bobot-bobot garis berbeda satu sama lain. Misalkan e1 berada dalam A.
  3. Karena B adalah MST, {e1}   B harus memiliki siklus C dengan e1.
  4. Sebagai pohon, A tidak memiliki siklus, maka C harus memiliki garis e2 yang tidak ada dalam A.
  5. Karena e1 dipilih sebagai garis unik berbobot minimum di antara garis-garis yang dimiliki oleh tepat salah satu dari A dan B, bobot e2 harus lebih besar daripada bobot e1.
  6. Karena e1 dan e2 adalah bagian dari siklus C, penggantian e2 dengan e1 mengakibatkan pohon rentang dengan bobot yang lebih kecil.
  7. Hal ini menjadi kontradiksi dari pernyataan bahwa B adalah MST.

Secara umum, jika ada garis-garis yang memiliki bobot yang sama, hanya sebagian garis pada pohon rentang minimum yang pasti unik.[1]

Graf bagian dengan bobot minimum

sunting

Jika semua bobot adalah positif, pohon rentang minimum adalah graf bagian (subgraf) berbobot minimum yang menghubungkan semua titik. Graf bagian yang memiliki siklus membutuhkan total bobot yang lebih banyak.

Sifat siklus

sunting

Untuk tiap siklus C dalam graf, jika bobot suatu garis e yang ada dalam C lebih besar daripada bobot tiap-tiap garis yang ada dalam C, garis ini tidak dapat dimasukkan ke dalam MST.

Bukti: Misalkan sebaliknya, yaitu e dimasukkan ke dalam MST T1, maka penghapusan e akan membagi T1 menjadi dua pohon bagian (subpohon) yang berbeda. Sisa C menghubungkan kedua pohon bagian, sehingga ada garis f yang berada dalam dua pohon bagian. Dengan kata lain, garis f menghubungkan dua pohon bagian menjadi pohon T2 dengan bobot yang lebih kecil daripada T1 karena bobot f lebih kecil daripada bobot e.

Algoritme

sunting

Algoritme pertama yang dipakai untuk mencari pohon rentang minimum dikembangkan oleh ilmuwan Ceko Otakar Borůvka pada tahun 1926 (lihat algoritme Borůvka). Kegunaan awalnya adalah membuat sistem kelistrikan yang efisien di daerah Moravia. Algoritme ini bekerja dalam deretan tahapan yang disebut langkah Boruvka. Kompleksitas algoritmenya adalah O(m log n).[2]

Algoritme kedua adalah algoritme Prim. Algoritme ini ditemukan oleh Vojtěch Jarník pada tahun 1930 dan ditemukan ulang oleh Prim pada tahun 1957 dan Dijkstra pada tahun 1959. Secara sederhana, algoritme ini mengembangkan MST (T) garis demi garis. Awalnya, T terdiri dari titik bebas. Pada tiap langkah, T ditambahkan garis berbobot minimum (x, y) dengan x ada dalam T dan y belum ada dalam T. Dengan sifat pemotongan, semua garis yang ditambahkan adalah MST. Kompleksitas algoritmenya adalah math|O(m log n) atau O(m + n log n) tergantung struktur data yang dipakai.

Algoritme ketiga yang sering dipakai adalah algoritme Kruskal. Kompleksitas algoritmenya adalah O(m log n).

Algoritme keempat yang jarang dipakai adalah algoritme hapus mundur yang merupakan kebalikan dari algoritme Kruskal. Kompleksitas algoritmenya adalah O(m log n (log log n)3).

Keempat algoritme tersebut termasuk algoritme rakus (greedy).

Penerapan

sunting

Pohon rentang minimum dipakai dalam desain jaringan, termasuk jaringan komputer, jaringan telekomunikasi, jaringan transportasi, jaringan penyediaan air, dan sistem kelistrikan (yang menjadi alasan penemuannya, sudah dijelaskan di atas).[3]

Referensi

sunting
  1. ^ "Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?". cs.stackexchange.com. Diakses tanggal 20 Juni 2020. 
  2. ^ Pettie, Seth; Ramachandran, Vijaya (2002), "An optimal minimum spanning tree algorithm" (PDF), Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431 .
  3. ^ Graham, R. L.; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/MAHC.1985.10011, MR 0783327 .