Context: Pohon minimum spanning (MST) atau minimum weight spanning tree adalah subset dari tepi dari sebuah graph yang terhubung, dengan berat tepi yang tidak terarah yang menghubungkan semua puncak bersama-sama, tanpa siklus dan dengan total berat tepi minimum yang mungkin. Artinya, itu adalah pohon spanning yang jumlah berat tepi adalah sekecil mungkin. Lebih umum, setiap graph tanpa arah yang tertimbang tepi (tidak harus terhubung) memiliki hutan minimum spanning, yang merupakan persatuan dari pohon minimum spanning untuk komponen yang terhubung. Ada banyak kasus penggunaan untuk pohon minimum spanning. Salah satu contohnya adalah sebuah perusahaan telekomunikasi yang mencoba untuk meletakkan kabel di lingkungan baru. Jika dibatasi untuk menguburkan total kabel hanya di sepanjang jalur tertentu (misalnya jalan), maka akan ada grafik yang berisi poin-poin (misalnya rumah) yang terhubung oleh jalur-jalur minimum tersebut. Beberapa dari jalur mungkin lebih mahal, karena mereka terkubur lebih dalam, atau untuk mewakili jalur-jalur kabel dengan berat yang lebih rendah; tetapi tidak ada persyaratan geometris yang dapat diterima untuk mewakili satu jalur spanning dengan tepi yang lebih panjang; karena tidak ada persyaratan untuk mewakili jalur-jalur yang lebih panjang dengan batas-batas yang paling rendah dari satu pohon, akan tetap diperlukan untuk mewakili jalur-jalur yang memiliki ukuran yang paling tinggi.

Berdasarkan teks yang diberikan, apa yang optimal dari minimum spanning tree?

Sebuah minimum spanning tree mengoptimalkan grafik dengan cara yang meminimalkan jumlah semua bobot tepi