DAA- Spanning Trees

Spanning Trees

In this article, we will be learning about the Spanning tree with an example, its properties, and applications.

What is a Spanning tree?

Suppose that we have a graph G that contains vertices V and edges E, then the graph can be represented as follows:

G(V, E)

While creating a spanning tree from the above graph we see that it will contain the same number of vertices as the graph, but the vertices are not equal. The edges in the spanning tree would be one less than the number of edges in the graph.

Suppose the spanning tree is represented as:

G`(V`, E`)
where,
V=V`
E`ϵ E -1
E`=|V| - 1

Example:

Suppose that we want to create a spanning tree from the graph below:

As we know, the spanning tree would contain the same number of vertices as the graph. Here, the total number of vertices in the graph is 5; therefore, the spanning tree will also contain 5 vertices. Also, the number of edges in the spanning tree must be equal to the number of vertices in the graph minus 1; therefore, the number of edges is 4. From the above graph, three spanning trees can be created, these are shown below:

Properties of Spanning tree

• The first property of a spanning tree is that a connected graph can have more than one spanning tree. Out of all the spanning the tree which is minimally connected or having a minimum total edge weight would be considered as the minimum spanning tree.
• The spanning trees that are created from the given graph G would contain the same number of vertices as Graph G. But the number of edges in the spanning tree would be one less than the number of vertices in the given graph G.
• The spanning tree should never contain a cycle. Consider the following example to understand this more clearly. Suppose we have the following graph:
  

• The spanning trees that we get from the above graph are shown below:
  
  From the above spanning trees, we can observe that one edge has been removed from each of them. If we do not do that then it would form a cyclic graph and a cyclic graph cannot be considered as a spanning tree.
• The spanning tree cannot be disconnected. From the above graphs, if we remove one more edge then the tree is no more considered to be a spanning tree because it is disconnected now.
• If there are two or three edges with the same edge weight, then in that case there would be more than two minimum spanning trees. On the other hand, if each edge has a distinct weight, then there will be only one minimum spanning tree.
• It is observed that a complete undirected graph can have nn-2 number of spanning trees. Where n resembles the number of vertices in the graph. 

For example, if we take 5 as the value of n then the number of spanning trees would be equal to 125.

• Every connected and undirected graph will contain at least one spanning tree.
• Also, the disconnected graph will not contain any spanning tree, which we have discussed already.
• We can construct a spanning tree by removing a maximum of (e-n+1) edges provided, if the given graph is a complete graph.

A where each pair of vertices are connected is called a complete graph. Consider the following complete graph which has 3 vertices:

• From the above graph, we can create three spanning trees as shown below:
  According to this property, the maximum number of edges that can be removed from the graph can be formulated as (e-n+1).

Here, e is the number of edges, and n is the number of vertices. When we substitute the value of e and n in the formula, then we get the value 1. This means that a maximum of 1 edge can be removed from the graph to make a spanning tree. In all the above spanning trees, one edge has been removed.

Applications of Spanning trees

• Building a network: Consider, there is a network where there are many routers connected to each other. In such a case, there might be a possibility that it forms a loop. In order to avoid the formation of such loops, we can make use of the tree data structure to connect the routers. Therefore, a minimum spanning tree is used to minimally connect them.
• Clustering: Clustering is simply the grouping of a set of objects such that similar objects belong to the same group and not to a different group. Ultimately, our goal is to maximize the distance between the different groups. This can be done by dividing the n objects into k groups.