Minimum spanning tree

[2] More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

A minimum spanning tree would be one with the lowest total cost, representing the least expensive path for laying the cable.

If each edge has a distinct weight then there will be only one, unique minimum spanning tree.

This is true in many realistic situations, such as the telecommunications company example above, where it's unlikely any two paths have exactly the same cost.

Proof: More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees.

[3] If the weights are positive, then a minimum spanning tree is, in fact, a minimum-cost subgraph connecting all vertices, since if a subgraph contains a cycle, removing any edge along that cycle will decrease its cost and preserve connectivity.

Deleting e' we get a spanning tree T∖{e' } ∪ {e} of strictly smaller weight than T. This contradicts the assumption that T was a MST.

Proof: if e was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding e to the MST, would yield a spanning tree of smaller weight.

In each stage, called Boruvka step, it identifies a forest F consisting of the minimum-weight edge incident to each vertex in the graph G, then forms the graph G1 = G \ F as the input to the next step.

Since the number of vertices is reduced by at least half in each step, Boruvka's algorithm takes O(m log n) time.

Since they run in polynomial time, the problem of finding such trees is in FP, and related decision problems such as determining whether a particular edge is in the MST or determining if the minimum total weight exceeds a certain value are in P. Several researchers have tried to find more computationally-efficient algorithms.

[5][6] The fastest non-randomized comparison-based algorithm with known complexity, by Bernard Chazelle, is based on the soft heap, an approximate priority queue.

The function α grows extremely slowly, so that for all practical purposes it may be considered a constant no greater than 4; thus Chazelle's algorithm takes very close to linear time.

Each phase executes Prim's algorithm many times, each for a limited number of steps.

Hence, at most log*n phases are needed, which gives a linear run-time for dense graphs.

[11] Whether the problem can be solved deterministically for a general graph in linear time by a comparison-based algorithm remains an open question.

Given graph G where the nodes and edges are fixed but the weights are unknown, it is possible to construct a binary decision tree (DT) for calculating the MST for any permutation of weights.

A DT for a graph G is called optimal if it has the smallest depth of all correct DTs for G. For every integer r, it is possible to find optimal decision trees for all graphs on r vertices by brute-force search.

Hence, the total time required for finding an optimal DT for all graphs with r vertices is:[4] which is less than Seth Pettie and Vijaya Ramachandran have found a provably optimal deterministic comparison-based minimum spanning tree algorithm.

Thus, this algorithm has the peculiar property that it is provably optimal although its runtime complexity is unknown.

Research has also considered parallel algorithms for the minimum spanning tree problem.

With a linear number of processors it is possible to solve the problem in O(log n) time.

Alan M. Frieze showed that given a complete graph on n vertices, with edge weights that are independent identically distributed random variables with distribution function

Svante Janson proved a central limit theorem for weight of the MST.

, the exact expected size of the minimum spanning tree has been computed for small complete graphs.

Formally, a fractional spanning set of a graph (V,E) is a nonnegative function f on E such that, for every non-trivial subset W of V (i.e., W is neither empty nor equal to V), the sum of f(e) over all edges connecting a node of W with a node of V\W is at least 1.

Intuitively, f(e) represents the fraction of e that is contained in the spanning set.

If the fractions f(e) are forced to be in {0,1}, then the set T of edges with f(e)=1 are a spanning set, as every node or subset of nodes is connected to the rest of the graph by at least one edge of T. Moreover, if f minimizes

The fractional MST problem can be solved in polynomial time using the ellipsoid method.

[32] Other practical applications based on minimal spanning trees include:

A planar graph and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to its length.
This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.
This figure shows the cut property of MSTs. T is the only MST of the given graph. If S = { A , B , D , E }, thus V – S = { C , F }, then there are 3 possibilities of the edge across the cut ( S , V – S ) , they are edges BC , EC , EF of the original graph. Then, e is one of the minimum-weight-edge for the cut, therefore S ∪ { e } is part of the MST T .
Minimum Steiner trees of vertices of regular polygons with N = 3 to 8 sides. The lowest network length L for N > 5 is the circumference less one side. Squares represent Steiner points.