Pohon rentang minimum

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.

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 masalah ini adalah biaya (cost). Dalam konteks ini, pohon rentang minimum adalah jalur yang menggunakan kabel sependek mungkin atau dengan biaya serendah mungkin.

Sifat

Peluang ketergandaan (multiplicity)

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

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 e₁ adalah garis dengan bobot terendah; pilihan ini unik karena bobot-bobot garis berbeda satu sama lain. Misalkan e₁ berada dalam A.
3. Karena B adalah MST, {e₁} ∪ {\displaystyle \cup } B harus memiliki siklus C dengan e₁.
4. Sebagai pohon, A tidak memiliki siklus, maka C harus memiliki garis e₂ yang tidak ada dalam A.
5. Karena e₁ dipilih sebagai garis unik berbobot minimum di antara garis-garis yang dimiliki oleh tepat salah satu dari A dan B, bobot e₂ harus lebih besar daripada bobot e₁.
6. Karena e₁ dan e₂ adalah bagian dari siklus C, penggantian e₂ dengan e₁ 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

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

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 T₁, maka penghapusan e akan membagi T₁ 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 T₂ dengan bobot yang lebih kecil daripada T₁ karena bobot f lebih kecil daripada bobot e.

Algoritma

Algoritma 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. Algoritma ini bekerja dalam deretan tahapan yang disebut langkah Boruvka. Kompleksitas algoritmanya adalah O(m log n).^[2]

Algoritma kedua adalah algoritme Prim. Algoritma 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, algoritma 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 algoritmanya adalah math|O(m log n) atau O(m + n log n) tergantung struktur data yang dipakai.

Algoritma ketiga yang sering dipakai adalah algoritme Kruskal. Kompleksitas algoritmanya adalah O(m log n).

Algoritma keempat yang jarang dipakai adalah algoritme hapus mundur yang merupakan kebalikan dari algoritma Kruskal. Kompleksitas algoritmanya adalah O(m log n (log log n)³).

Keempat algoritma tersebut termasuk algoritme rakus (greedy).

Penerapan

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