Minimum and maximum spanning trees

Minimum and maximum spanning trees

A spanning tree of a connected undirected graph is a tree that includes all vertices of the graph.
A minimum spanning tree (MST) is a spanning tree with the smallest possible sum of edge weights.
Similarly, a maximum spanning tree is a spanning tree with the largest possible sum of edge weights.

Properties of a minimum spanning tree

• Uniqueness
  If all edges of the graph have distinct weights, the minimum spanning tree is unique.
  If some edges have equal weights, then it is possible for several different MSTs to exist.

• Minimization of the product of weights
  A minimum spanning tree minimizes not only the sum, but also the product of the weights of its edges.
  This can be understood by moving to logarithms of the weights: minimizing the sum of logarithms is equivalent to minimizing the logarithm of the product.

• Maximum spanning tree
  A maximum spanning tree can be found similarly to an MST. To do this, it is enough to change the sign of all edge weights and apply any minimum spanning tree algorithm (for example, Kruskal's algorithm).