Pohon rentang minimum

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

Pohon rentang minimum atau pohon rentang berbobot minimum (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 permasalahan 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

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 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₁} $\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.

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.

Algoritme

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).

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)³).

Keempat algoritme 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).