最小瓶颈生成树与最小生成树有何不同？

1. Overview

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 G(V, E) . A spanning tree $\mathbf{S (V_1, E_1)}$ on the graph $\mathbf{G}$ is a tree that includes all the vertices of $\mathbf{G}$ . Hence, V_1 = V . Additionally, all the edges in should also be present in . Therefore, $E_1 \subseteq E$ .

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.

2.1. Example

Let’s see an example of how to find a minimum spanning tree from a graph $\mathbf{G_1}$ :

gjhfjfg-3

In this example, the input graph G_1 is a complete graph with $\mathsf{3}$ vertices. Next, let’s find all the possible spanning trees for the graph G_1 :

gjhfjfg-2

As the input graph, G_1 is fully connected, the total number of possible spanning trees is $N^{N - 2}$ . Here, denotes the total number of vertices in the graph. Therefore, we generated $\mathsf{3^{3 - 2} = 3}$ spanning trees for the graph G_1 .

The cost of spanning trees S_1, S_2, S_3 are $\mathsf{3, 4, 5}$ . Hence, we can see that among all the possible spanning trees of , S_1 has minimum cost. Therefore, $\mathbf{S_1}$ is the minimum spanning tree for the graph $\mathbf{G_1}$ .

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 $\mathbf{G(V, E)}$ is a tree whose maximum weighted edge is minimum among all the possible spanning trees of $\mathbf{G}$ .

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.

3.1. Example

Let’s take an undirected, connected, and weighted graph $\mathbf{G_2}$ :

gjhfjfg-4

Now let’s list out all the spanning trees with cost and bottleneck edge:

gjhfjfg-6

Here, the total number of spanning trees corresponding to the graph G_2 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 G_2 , S_1 has the minimum cost. Therefore, S_1 is a minimum spanning tree of G_2 . We need to find the bottleneck edge, the maximum weighted edge in the minimum spanning tree S_1 .

We can see the edge (C, D) in S_1 is the bottleneck edge as its the highest weighted edge in S_1 . Hence, all the spanning trees that contain the edge (C, D) are the minimum bottleneck spanning trees. Therefore, for graph $\mathbf{G_2}$ , the minimum bottleneck spanning trees are $\mathbf{S_1, S_2, S_4}$ .

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 G_2 , we found $\mathsf{3}$ minimum bottleneck spanning trees. Out of $\mathsf{3}$ , S_1 is a minimum spanning tree. But S_2 and S_3 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 G_2 is . On the other hand, the weights of the MBSTs of G_2 are 6, 9, 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:

Minimum Spanning Tree

Minimum Bottleneck Spanning Tree

It’s a spanning tree with the minimum cost among all possible spanning trees.

It’s a tree whose maximum weighted edge is minimum among all the possible spanning trees.

An MST is always an MBST.

An MBST may or may not be an MST.

Total weight of an MST corrosping to a graph is unique.

For a given graph, there might be MBSTs with different weights.

An MST contains exactly (N – 1) edges.

An MBST may contains more than (N – 1) edges.

5. Conclusion

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.

Persistence

REST

Security