A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected..

By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices.

We found three spanning trees off one complete graph. A complete undirected graph can have maximum n n-2  number of spanning trees, where n is the number of nodes. In the above addressed example, n is 3, hence 3 3−2  = 3 spanning trees are possible.

General Properties of Spanning Tree

We now understand that one graph can have more than one spanning tree. Following are a few properties of the spanning tree connected to graph G −

• A connected graph G can have more than one spanning tree.

• All possible spanning trees of graph G, have the same number of edges and vertices.

• The spanning tree does not have any cycle (loops).

• Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning tree is minimally connected.

• Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is maximally acyclic.

Mathematical Properties of Spanning Tree

• Spanning tree has n-1 edges, where n is the number of nodes (vertices).

• From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.

• A complete graph can have maximum n n-2  number of spanning trees. Thus, we can conclude that spanning trees are a subset of connected Graph G and disconnected graphs do not have spanning tree.

Application of Spanning Tree

Spanning tree is basically used to find a minimum path to connect all nodes in a graph. Common application of spanning trees are −

• Civil Network Planning

• Computer Network Routing Protocol

• Cluster Analysis

Let us understand this through a small example. Consider, city network as a huge graph and now plans to deploy telephone lines in such a way that in minimum lines we can connect to all city nodes. This is where the spanning tree comes into picture.

Minimum Spanning Tree (MST)

In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph. In real-world situations, this weight can be measured as distance, congestion, traffic load or any arbitrary value denoted to the edges.

Minimum Spanning-Tree Algorithm

We shall learn about two most important spanning tree algorithms here −

• Kruska's Algorithm

• Prim's Algorithm

Both are greedy algorithms

.1. Image segmentation

There are two famous algorithms for finding the Minimum Spanning Tree:

Kruskal’s Algorithm

Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach. This algorithm treats the graph as a forest and every node it has as an individual tree. A tree connects to another only and only if, it has the least cost among all available options and does not violate MST properties.

Algorithm Steps:

• Sort the graph edges with respect to their weights.

• Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.

• Only add edges which doesn't form a cycle , edges which connect only disconnected components.

• To understand Kruskal's algorithm let us consider the following example

Step 1 - Remove all loops and Parallel Edges

Remove all loops and parallel edges from the given graph.

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Arrange all edges in their increasing order of weight The next step is to create a set of edges and weight, and arrange them in an ascending order of weightage (cost).

Step 3 - Add the edge which has the least weight age Now we start adding edges to the graph beginning from the one which has the least weight. Throughout, we shall keep checking that the spanning properties remain intact. In case, by adding one edge, the spanning tree property does not hold then we shall consider not including the edge in the graph.

The least cost is 2 and edges involved are B,D and D,T. We add them. Adding them does not violate spanning tree properties, so we continue to our next edge selection. Next cost is 3, and associated edges are A,C and C,D. We add them again −

Next cost in the table is 4, and we observe that adding it will create a circuit in the graph.

We ignore it. In the process we shall ignore/avoid all edges that create a circuit.

We observe that edges with cost 5 and 6 also create circuits. We ignore them and move on.

Now we are left with only one node to be added. Between the two least cost edges available 7 and 8, we shall add the edge with cost 7.

By adding edge S,A we have included all the nodes of the graph and we now have minimum cost spanning tree.

Cost solution= (S,A)+(C,A)+(D,C)+(D,B)+(D,T) =7+3+3+2+2 =17

Prim’s Algorithm

Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal's, we add vertex to the growing spanning tree in Prim's.

Algorithm Steps:

• Maintain two disjoint sets of vertices. One containing vertices that are in the growing spanning tree and other that are not in the growing spanning tree.

• Select the cheapest vertex that is connected to the growing spanning tree and is not in the growing spanning tree and add it into the growing spanning tree. This can be done using Priority Queues. Insert the vertices, that are connected to growing spanning tree, into the Priority Queue.

• Check for cycles. To do that, mark the nodes which have been already selected and insert only those nodes in the Priority Queue that are not marked.

Consider the example below:

Graph

Consider the following graph.

We will find MST for the above graph shown in the image.

Step 1: Remove all loops

Any edge that starts and ends at the same vertex is a loop.

Loops are marked in the image given below.

Step 2: Remove all parallel edges between two vertex except the one with least weight

In this graph, vertex A and C are connected by two parallel edges having weight 10 and 12 respectively. So, we will remove 12 and keep 10.

We are now ready to find the minimum spanning tree.

Step 3: Create table

As our graph has 4 vertices, so our table will have 4 rows and 4 columns.

Now, put 0 in cells having same row and column name.

Find the edges that directly connect two vertices and fill the table with the weight of the edge. If no direct edge exists then fill the cell with infinity.

Finding MST

Start from vertex A, find the smallest value in the A-row.

Note! We will not consider 0 as it will correspond to the same vertex.

5 is the smallest unmarked value in the A-row. So, we will mark the edge connecting vertex A and B and tick 5 in AB and BA cell.

As we connected vertex A and B in the previous step, so we will now find the smallest value in the A-row and B-row.

4 is the smallest unmarked value in the A-row and B-row. So, we will mark the edge connecting vertex B and C and tick 4 in BC and CB cell.

As vertex A-B and B-C were connected in the previous steps, so we will now find the smallest value in A-row, B-row and C-row.

5 is the smallest unmarked value in the A-row, B-row and C-row. So, we will mark the edge connecting vertex C and D and tick 5 in CD and DC cell.

Result

Following is the required Minimum Spanning Tree for the given graph.