Data Structures Algorithms 简明教程
Spanning Tree
What is Spanning Tree?
生成树是图 G 的一个子集，它以尽可能少数量的边覆盖所有顶点。因此，生成树没有回路并且不能断开连接。
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..
根据这个定义，我们可以得出结论：每个相连且无向的图 G 至少有一个生成树。断开连接的图没有任何生成树，因为它无法跨越到其所有顶点。
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.
我们从一个完全图中找到了三个生成树。一个完整的无向图可以有 nn-2 个生成树，其中 n 是节点数。在上述示例中， n is 3, 因此 33−2 = 3 生成树是可能的。
We found three spanning trees off one complete graph. A complete undirected graph can have maximum nn-2 number of spanning trees, where n is the number of nodes. In the above addressed example, n is 3, hence 33−2 = 3 spanning trees are possible.
General Properties of Spanning Tree
我们现在明白一个图可以有多个生成树。以下是与图 G 相连的生成树的一些性质 −
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 nn-2 number of spanning trees.
因此，我们可以得出结论：生成树是连通图 G 的一个子集，断开连接的图没有生成树。
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.