Pengguna:Chinamoonroll/bak pasir: Perbedaan antara revisi

[[Pohon rentangan minimum]]

[[Minimum spanning tree]]

[[File:Minimum spanning tree.svg|thumb|300px|right|Sebuah [[graf planar]] dan pohon rentangan minimumnya. Setiap tepi diberi label dengan bobot, yang kira - kira sebanding dengan panjangnya.]]

'''Pohon rentangan minimum''' atau '''pohon retangan bobot minimum''' atau {{lang-en|'''minimum spanning tree''' ('''MST''')}} adalah subset dari tepi [[graph terhubung|terhubung]], graf tidak berarah tepi-berbobot yang menghubungkan semua [[Vertex (teori graf)|simpul]] bersamaan, tepi-berbobot pada graf tidak berarah menghubungkan simpul bersama, tanpa siklus dan dengan total bobot tepi minimum yang dimungkinkan. Artinya, [[pohon rentangan]] yang jumlah bobot tepi sekecil mungkin. Secara lebih umum, setiap graf tidak berarah berbobot tepi (tidak harus terhubung) memiliki '''hutan rentangan minimum''', yang merupakan gabungan dari MST untuk [[komponen terhubung (teori graf)|komponen terhubung]].