Spanning Tree

The following are the types of graphs:

• Undirected graph: An undirected graph is a graph in which all the edges do not point to any particular direction, i.e., they are not unidirectional; they are bidirectional.
  It can also be defined as a graph in which set of V vertices and set of E edges, each edge connecting two different vertices.
• Connected graph: A connected graph is a graph in which a path always exists from a vertex to any other vertex.
  A graph is connected if we can reach any vertex from any other vertex by following edges in either direction.
• Directed graph: A directed graph is defined as a graph in which set of V vertices and set of Edges, each connecting two different vertices, but it is not mandatory that node points in the opposite direction also.

What is a Spanning tree?

If we have a graph containing V vertices and E edges, then the graph can be represented as:

G(V, E)

If we create the spanning tree from the above graph, then the spanning tree would have the same number of vertices as the graph, but the vertices are not equal. The edges in the spanning tree would be equal to the number of edges in the graph minus 1.

Suppose the spanning tree is represented as:

G`(V`, E`)

where,

V=V`

E`ϵ E -1

E`=|V| - 1

Let's understand through an example.

Suppose we want to create the spanning tree of the graph, which is shown below:

As we know, that spanning tree contains the same number of vertices as the graph, so the total number of vertices in the graph is 5; therefore, the spanning tree will also contain the 5 vertices. The edges in the spanning tree are equal to the number of vertices in the graph minus 1; therefore, the number of edges is 4. Three spanning trees can be created, which are shown below:

Minimum Spanning Trees

The minimum spanning tree is the tree whose sum of the edge weights is minimum. From the above spanning trees, the total edge weight of the spanning tree 1 is 12, the total edge weight of the spanning tree 2 is 14, and the total edge weight of the spanning tree 3 is 11; therefore, the total edge weight of the spanning tree 3 is minimum. From the above graph, we can also create one more spanning tree as shown below:

In the above tree, the total edge weight is 10 which is less than the above spanning trees; therefore, the minimum spanning tree is a tree which is having an edge weight, i.e., 10.

Properties of Spanning tree

• A connected graph can contain more than one spanning tree. The spanning trees which are minimally connected or we can say that the tree which is having a minimum total edge weight would be considered as the minimum spanning tree.
• All the possible spanning trees that can be created from the given graph G would have the same number of vertices, but the number of edges in the spanning tree would be equal to the number of vertices in the given graph minus 1.
• The spanning tree does not contain any cycle. Let's understand this property through an example.
  Suppose we have the graph which is given below:
  
  We can create the spanning trees of the above graph, which are shown below:
  
  As we can observe in the above spanning trees that one edge has been removed. If we do not remove one edge from the graph, then the tree will form a cycle, and that tree will not be considered as the spanning tree.
• The spanning tree cannot be disconnected. If we remove one more edge from any of the above spanning trees as shown below:
  The above tree is not a spanning tree because it is disconnected now.
• If two or three edges have the same edge weight, then there would be more than two minimum spanning trees. If each edge has a distinct weight, then there will be only one or unique minimum spanning tree.
• A complete undirected graph can have n^n-2 number of spanning trees where n is the number of vertices in the graph. For example, the value of n is 5 then the number of spanning trees would be equal to 125.
• Each connected and undirected graph contains at least one spanning tree.
• The disconnected graph does not contain any spanning tree, which we have already discussed.
• If the graph is a complete graph, then the spanning tree can be constructed by removing maximum (e-n+1) edges. Let's understand this property through an example.
  A complete graph is a graph in which each pair of vertices are connected. Consider the complete graph having 3 vertices, which is shown below:
  
  We can create three spanning trees from the above graph shown as below:
  
  According to this property, the maximum number of edges from the graph can be formulated as (e-n+1) where e is the number of edges, n is the number of vertices. When we substitute the value of e and n in the formula, then we get 1 value. It means that we can remove maximum 1 edge from the graph to make a spanning tree. In the above spanning trees, the one edge has been removed.

Applications of Spanning trees

The following are the applications of the spanning trees:

• Building a network: Suppose there are many routers in the network connected to each other, so there might be a possibility that it forms a loop. So, to avoid the formation of the loop, we use the tree data structure to connect the routers, and a minimum spanning tree is used to minimally connect them.
• Clustering: Here, clustering means that grouping the set of objects in such a way that similar objects belong to the same group than to the different group. Our goal is to divide the n objects into k groups such that the distance between the different groups gets maximized.

How can clustering be achieved?

First, we divide the n objects into k groups.

Secondly, we will combine these clusters iteratively by adding an edge between them.

Stop when we reach the k clusters.

Approach

One of the approaches that can be used to obtain clustering is to compute a minimum spanning tree. The minimum spanning tree can be simply calculated by dropping the k-1 most heavily weighted edge from the graph.