Ang minimum spanning tree o minimum weight spanning tree ay isang subset ng mga gilid ng isang konektado, edge-weighted undirected graph na nag-uugnay sa lahat ng vertices nang magkasama, nang walang anumang mga cycle at may pinakamababang posibleng kabuuang bigat ng gilid. Ibig sabihin, isa itong spanning tree na ang kabuuan ng mga bigat sa gilid ay kasing liit hangga't maaari.
Ano ang minimum spanning tree na may halimbawa?
Ang minimum spanning tree ay isang espesyal na uri ng puno na nagpapaliit sa mga haba (o “mga timbang”) ng mga gilid ng puno. Ang isang halimbawa ay isang kumpanya ng cable na gustong maglagay ng linya sa maraming kapitbahayan; sa pamamagitan ng pagliit ng halaga ng cable na inilatag, ang kumpanya ng cable ay makatipid ng pera. Ang isang puno ay may isang landas na nagdurugtong sa alinmang dalawang vertice.
Paano mo mahahanap ang minimum spanning tree?
Hanapin ang ang pinakamalapit na walang kulay na kapitbahay sa pulang subgraph (ibig sabihin, ang pinakamalapit na vertex sa anumang pulang vertex). Markahan ito at ang gilid na nagkokonekta sa vertex sa pulang subgraph na pula. Ulitin ang Hakbang 2 hanggang sa mamarkahan ng pula ang lahat ng vertices. Ang pulang subgraph ay isang minimum spanning tree.
Ano ang ibig mong sabihin sa spanning tree at minimum spanning tree?
Ang spanning tree ng isang graph ay isang koleksyon ng mga konektadong gilid na kinabibilangan ng bawat vertex sa graph, ngunit hindi iyon bumubuo ng isang cycle. … Ang Minimum Spanning Tree ay ang isa na ang pinagsama-samang mga timbang sa gilid ay may pinakamaliit na halaga, gayunpaman.
Ano ang pagkakaiba ng spanning tree at minimum spanning tree?
Kung ang graph ayedge-weighted, maaari nating tukuyin ang weight ng isang spanning tree bilang kabuuan ng mga timbang ng lahat ng mga gilid nito. Ang minimum spanning tree ay isang spanning tree na ang bigat ay pinakamaliit sa lahat ng posibleng spanning tree.
