Pohon rentang minimum

Pohon rentang minimum atau pohon rentang berbobot minimum (, 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:
 Misalkan kebalikannya, yaitu ada dua MST yang berbeda: A dan B.
 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.
 Karena B adalah MST, {e1}  B harus memiliki siklus C dengan e1.
 Sebagai pohon, A tidak memiliki siklus, maka C harus memiliki garis e2 yang tidak ada dalam A.
 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.
 Karena e1 dan e2 adalah bagian dari siklus C, penggantian e2 dengan e1 mengakibatkan pohon rentang dengan bobot yang lebih kecil.
 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 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.

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

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

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

 Referensi 

Kategori:Matematika diskret
Kategori:Pohon rentang