A spanning tree of a graph is any tree that includes every vertex in the graph. Little more formally, a spanning tree of a graph G is a subgraph of G that is a tree and contains all the vertices of G. An edge of a spanning tree is called a branch; an edge in the graph that is not in the spanning tree is called a chord. We construct spanning tree whenever we want to find a simple, cheap and yet efficient way to connect a set of terminals (computers, cites, factories, etc.). Spanning trees are important because of following reasons.
Greedy Spanning Tree Algorithm
One of the most elegant spanning tree algorithm that I know of is as
Note that each time a step of the algorithm is performed, one edge
is examined. If there is only a finite number of edges in the graph,
the algorithm must halt after a finite number of steps. Thus, the time
complexity of this algorithm is clearly O(n), where n is the number of
edges in the graph.
Some important facts about spanning trees are as follows:
- Any two vertices in a tree are connected by a unique path.
- Let T be a spanning tree of a graph G, and let e be an edge of G not in T. The T+e contains a unique cycle.
Lemma The number of spanning trees in the complete graph Kn is nn-2.
Greediness It is easy to see that this algorithm has the property that each
edge is examined at most once. Algorithms, like this one, which examine
each entity at most once and decide its fate once and for all during
that examination are called greedy algorithms. The obvious advantage of
greedy approach is that we do not have to spend time reexamining
Consider the problem of finding a spanning tree with the
possible weight or the largest possible weight, respectively called a
minimum spanning tree and a maximum spanning tree.
It is easy to see that if a graph possesses a spanning tree, it must have a
minimum spanning tree and also a maximum spanning tree. These spanning trees can
be constructed by performing the spanning tree algorithm (e.g., above mentioned
algorithm) with an appropriate ordering of the edges.
Minimum Spanning Tree Algorithm
Perform the spanning tree algorithm (above) by examining the edges is order of non decreasing weight (smallest first, largest last). If two or more edges have the same weight, order them arbitrarily.
Maximum Spanning Tree Algorithm
Perform the spanning tree algorithm (above) by examining the edges in order of non increasing weight (largest first, smallest last). If two or more edges have the same weight, order them arbitrarily.
Minimum Spanning Trees
A minimum spanning tree (MST) of a weighted graph G is a spanning tree of G whose edges sum is minimum weight. In other words, a MST is a tree formed from a subset of the edges in a given undirected graph, with two properties:
- it spans the graph, i.e., it includes every vertex of the graph.
- it is a minimum, i.e., the total weight of all the edges is as low as possible.
Let G=(V, E) be a connected, undirected graph where V is a set of vertices (nodes) and E is the set of edges. Each edge has a given non negative length.
Problem Find a subset T of the edges of G such that all the vertices remain connected when only the edges T are used, and the sum of the lengths of the edges in T is as small as possible.
Let G` = (V, T) be the partial graph formed by the vertices of G and the edges in T. [Note: A connected graph with n vertices must have at least n-1 edges AND more that n-1 edges implies at least one cycle]. So n-1 is the minimum number of edges in the T. Hence if G` is connected and T has more that n-1 edges, we can remove at least one of these edges without disconnecting (choose an edge that is part of cycle). This will decrease the total length of edges in T.
G` = (V, T) where T is a subset of E. Since connected graph of n nodes must have n-1 edges otherwise there exist at least one cycle. Hence if G` is connected and T has more that n-1 edges. Implies that it contains at least one cycle. Remove edge from T without disconnecting the G` (i.e., remove the edge that is part of the cycle). This will decrease the total length of the edges in T. Therefore, the new solution is preferable to the old one.
Thus, T with n vertices and more edges can be an optimal solution. It follow T must have n-1 edges and since G` is connected it must be a tree. The G` is called Minimum Spanning Tree (MST).