Menu
A minimum spanning tree gives the cheapest way an undirected graph. But what is a minimum spanning forest? Is it defined for connected graphs or unconnected graphs?
618
Definition of Minimum Spanning Tree. A spanning tree of a graph is a collection of connected edges that include every vertex in the graph, but that do not form a cycle. Many such spanning trees may exist for a graph. The Minimum Spanning Tree is the one whose cumulative edge weights have the smallest value, however.
A minimum spanning tree is a special kind of tree that minimizes the lengths (or “weights”) of the edges of the tree. An example is a cable company wanting to lay line to multiple neighborhoods; by minimizing the amount of cable laid, the cable company will save money. A tree has one path joins any two vertices.
Spanning forests For other authors, a spanning forest is a forest that spans all of the vertices, meaning only that each vertex of the graph is a vertex in the forest. For this definition, even a connected graph may have a disconnected spanning forest, such as the forest in which each vertex forms a single-vertex tree.
A Minimum Spanning Tree(MST) or minimum weight spanning tree for a weighted, connected, undirected graph is a spanning tree having a weight less than or equal to the weight of every other possible spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.
Minimum spanning forest is a generalization of minimum spanning tree for unconnected graphs. For every component of the graph, take its MST and the resulting collection is a minimum spanning forest.
72
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
