In this tutorial, we’ll present two concepts from graph theory: minimum spanning tree and minimum bottleneck spanning tree. We’ll discuss the definitions with examples.
Finally, we’ll talk about the core differences between two tree structures.
2. Definition of Minimum Spanning Tree (MST)
Given an undirected, connected and weighted graph . A spanning tree on the graph is a tree that includes all the vertices of . Hence, . Additionally, all the edges in should also be present in . Therefore, .
The spanning tree for an input graph is not unique. Moreover, for a given graph , we can find various spanning trees. The cost of a spanning tree is the sum of all the edges present in the tree. Hence, based on the edge weights, the cost of the spanning trees for a given graph can be different.
Now we’re ready to discuss the definition of minimum spanning tree. A minimum spanning tree is a spanning tree that has minimum cost among all possible spanning trees for a given graph.
A diverse range of real-life applications uses the minimum spanning tree such as image segmentation, recognition of the handwritings, face tracking in real-time (in a video), analysis of clusters, network design.
Let’s see an example of how to find a minimum spanning tree from a graph :
In this example, the input graph is a complete graph with vertices. Next, let’s find all the possible spanning trees for the graph :
As the input graph, is fully connected, the total number of possible spanning trees is . Here, denotes the total number of vertices in the graph. Therefore, we generated spanning trees for the graph .
The cost of spanning trees are . Hence, we can see that among all the possible spanning trees of , has minimum cost. Therefore, is the minimum spanning tree for the graph .
3. Definition of Minimum Bottleneck Spanning Tree (MBST)
A bottleneck in a spanning tree is defined as the edge with maximum weight. Therefore, a minimum bottleneck spanning tree in an undirected, connected, and weighted graph is a tree whose maximum weighted edge is minimum among all the possible spanning trees of .
As we already discussed, for a given graph, there might be several spanning trees. Therefore, we select a spanning tree with minimum cost as a minimum spanning tree from the set of spanning trees. In the minimum spanning tree, the edge with the maximum cost is a bottleneck edge. Finally, spanning trees that contain this particular edge are minimum bottleneck spanning trees.
Let’s take an undirected, connected, and weighted graph :
Now let’s list out all the spanning trees with cost and bottleneck edge:
Here, the total number of spanning trees corresponding to the graph is . Finding all the possible spanning trees from the given graph is the first step of finding the minimum bottleneck spanning trees. The next step is to find the minimum spanning tree among all possible spanning trees.
Among all possible spanning trees of , has the minimum cost. Therefore, is a minimum spanning tree of . We need to find the bottleneck edge, the maximum weighted edge in the minimum spanning tree .
We can see the edge in is the bottleneck edge as its the highest weighted edge in . Hence, all the spanning trees that contain the edge are the minimum bottleneck spanning trees. Therefore, for graph , the minimum bottleneck spanning trees are .
3.2. Properties of MBST
A minimum bottleneck spanning tree has some interesting properties. A minimum bottleneck spanning tree may or may not be a minimum spanning tree. In the case of , we found minimum bottleneck spanning trees. Out of , is a minimum spanning tree. But and are not minimum spanning trees. Hence, not all the minimum bottleneck spanning trees are minimum spanning trees.
An MST is always an MBST. By the definition of an MBST, the bottleneck edge should belong to an MST. In fact, we select MBSTs from the spanning trees that contain the bottleneck edge.
The total weight of an MBST will always be greater than or equal to the total weight of an MST for a given graph. For example, the weight of the MST for the graph is . On the other hand, the weights of the MBSTs of are and .
4. Differences Between MBST and MST
Now we know how an MBST is different from an MST. Let’s talk about the core differences between them:
In this article, we discussed two very close yet different graph concepts in graph theory: minimum spanning tree, minimum bottleneck spanning tree. We presented the definition of both the trees with graph examples.
Finally, we discussed the core differences between them.