221k views
5 votes
What is minimum spanning tree

1 Answer

0 votes

Answer:

Given an unguided connected graph, an extension tree of this graph is a subgraph which is a tree that connects all vertices. A single graph may have different extension trees. We can mark a weight at each edge, which is a number that represents how unfavorable it is, and assign a weight to the extension tree calculated by the sum of the weights of the edges that compose it. A minimum spanning tree is then an extension tree with a weight less than or equal to each of the other possible spanning trees. Generalizing more, any non-directional graph (not necessarily connected) has a minimal forest of trees, which is a union of minimal extension trees of each of its related components.

User Jestro
by
7.7k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.