|
[[Pohon rentangan minimum]]
[[Minimum spanning tree]]
{{Short description|data structure, subgraph of a weighted graph}}
[[File:Minimum spanning tree.svg|thumb|300px|right|ASebuah [[graf planar graph]] anddan itspohon minimumrentangan spanning treeminimumnya. EachSetiap edgetepi isdiberi labeledlabel withdengan its weightbobot, which hereyang iskira roughly- proportionalkira tosebanding itsdengan lengthpanjangnya.]]
A '''minimumPohon spanningrentangan treeminimum''' (atau '''MSTpohon retangan bobot minimum''') oratau {{lang-en|'''minimum weight spanning tree''' is('''MST''')}} aadalah subset ofdari the edges of atepi [[connected graph terhubung|connectedterhubung]], edge-weightedgraf undirectedtidak graphberarah thattepi-berbobot connectsyang allmenghubungkan thesemua [[Vertex (graphteori theorygraf)|verticessimpul]] togetherbersamaan, withouttepi-berbobot anypada cyclesgraf andtidak withberarah themenghubungkan minimumsimpul bersama, tanpa siklus dan possibledengan total edgebobot weight.tepi Thatminimum is,yang itdimungkinkan. is aArtinya, [[spanningpohon treerentangan]] whoseyang sumjumlah ofbobot edgetepi weightssekecil ismungkin. asSecara smalllebih asumum, possible.setiap Moregraf generally,tidak anyberarah edge-weightedberbobot undirected graphtepi (nottidak necessarilyharus connectedterhubung) has amemiliki '''minimumhutan spanningrentangan forestminimum''', whichyang ismerupakan agabungan uniondari ofMST the minimum spanning trees for itsuntuk [[connectedkomponen componentterhubung (graphteori theorygraf)|connectedkomponen componentsterhubung]].
Ada beberapa kasus penggunaan MST, Salah satu contohnya adalah perusahaan telekomunikasi yang mencoba memasang kabel di lingkungan baru. Jika dibatasi untuk memasang kabel hanya di sepanjang jalur tertentu (mis. Jalan), maka akan ada grafik yang berisi titik (mis. Rumah) yang terhubung oleh jalur tersebut.
There are quite a few use cases for minimum spanning trees. One example would be a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the [[triangle inequality]]. A ''spanning tree'' for that graph would be a subset of those paths that has no cycles but still connects every house; there might be several spanning trees possible. A ''minimum spanning tree'' would be one with the lowest total cost, representing the least expensive path for laying the cable.
Beberapa jalur mungkin lebih mahal, karena lebih panjang, atau membutuhkan kabel untuk ditanam lebih dalam;jalur ini akan diwakili oleh tepi dengan bobot lebih besar. Mata uang adalah unit yang dapat diterima untuk berat tepi, tidak ada persyaratan panjang tepi untuk mematuhi aturan geometri normal seperti [[ketidaksetaraan segitiga]]. ''Pohon rentangan'' untuk graf tersebut akan menjadi bagian dari jalur yang tidak memiliki siklus tetapi masih menghubungkan setiap rumah; mungkin ada beberapa pohon merentang lainya. ''MST'' akan menjadi pohon dengan biaya total terendah, mewakili jalur paling murah untuk memasang kabel.
==Properties==
| 