生成树

生成树是a的特殊子图吗图它有几个重要的性质。首先,如果T是一个生成树的图G, T必须跨G, T意义必须包含每个顶点在G .其次,T必须的子图G .换句话说,每条边的T也必须出现在G .第三,如果每条边在T也存在于G, G是相同的T。

生成树在寻径算法中非常重要，如Dijkstra最短路径算法和A *搜索算法．在这些算法中，生成树是作为子部分计算的。它也用于网络路由协议。的生成树协议就是一个例子。

图中有一个用蓝色突出显示的生成树^［1］

生成树有一些一般的性质。

1. 一个连通图可以有不止一棵生成树。他们可以有很多 $v v | | ^ {| | 2},$在哪里 $v | |$为图中顶点的数目。
2. 图G的所有可能的生成树都有相同数量的边和顶点。
3. 生成树没有任何循环。
4. 生成树都是最小连接的。也就是说，如果任何一条边被移除，生成树将不再连接。
5. 向生成树添加任何边都会创建一个循环。生成树是最大无环的。
6. 生成树 $| | - 1$边, $n | |$为顶点的数目。

不同类型的图有不同数量的生成树。这里有几个例子。

1)完整的图

完全图是指每个顶点与其他顶点相连的图。图G的生成树数 $v | |$顶点的定义公式如下: $T (G_ \文本{完成})v = | | ^ {| v | 2}$．

完全图^［2］

2)连接图

对于连通图，生成树可以定义为连通边的最小集所有顶点或不包含循环的最大边集。

连通图就是这样一个图，它的边数必须小于或等于具有相同顶点数的完整图中的边数。因此，连通图的生成树数为 $T (G_ \文本{连接})\ leq v | | ^ {| v | 2}$．

连通图^［３］

3)树

如果一个图G本身是树，那么G的唯一生成树就是它自己。所以一棵树 $v | |$顶点定义为 $T (G_ \文本{树})v = | | ^ {| v | 2}$．

树图^［4］

4)完全二部图

二部图是这样一种图，其中每个节点可以与两个集合中的一个相关联， $米$或 $n$．这些集合中的顶点只连接到另一个集合中的顶点。没有集合内的边。完全二部图是集合中每个顶点的二部图 $米$连接到集合中的每个顶点 $n$，反之亦然。

定义了二部图的生成树数 $T (G_ \文本{complete-bipartite}) = m ^ {n} \ cdot n ^ {m - 1}$．

完成两偶图^［5］

5)一般图

为了计算一般图的生成树的数目，一个流行的定理是基尔霍夫定理．

为了实现这个定理，必须构造一个二维矩阵，它可以通过图的顶点通过行和列建立索引。的细胞 $我^ \文本{th}$行和 $j ^ \文本{th}$列的值由三个因素决定。如果 $我=我$，则单元格中的值将等于的度数 $我$．如果 $我$和 $j$是相邻的，那么值是 $－１$．否则，值为 $0$．

从这里，选择一个任意顶点，并从矩阵中删除其相应的行和列。这个新矩阵的行列式就是一个生成树 $T (G)$．

生成树可以是线性的 $O (V + E)$通过简单的表演来获得时间广度优先搜索或深度优先搜索．这些图搜索算法只依赖于图中顶点的数量，所以它们非常快。

广度优先搜索将使用队列为了保存顶点以供以后探索，深度优先搜索将使用堆栈．在任何一种情况下，都可以通过连接每个顶点来构造生成树 $v$用发现它的顶点。

不幸的是，这些搜索算法并不适用于并行或分布式计算，而这正是生成树流行的领域。然而，有一些算法是设计来在并行设置中找到生成树的。

对于完全图，有精确数量的边必须被删除以创建生成树。对于一个完全图G，可以通过删除来计算生成树 $|e| - |v| + 1$边缘。在这个方程, $| e |$是边数，和 $v | |$为顶点的数目。

最小生成树是生成树的一种变体。
无加权图G的最小生成树是使边数或边权数最小化的生成树。
加权图G的最小生成树是使树中边的权值最小的生成树。

这两幅图展示了生成树和最小生成树的区别。被灰色化的边缘在它们各自的树中被保留了下来，但是它们被保留在图像中以显示它们的权重。

加权生成树

加权最小生成树

最小生成树在许多应用和算法中都非常有用。它们通常用于水网、电网和计算机网络。它们也被用在图的问题中，比如旅行推销员问题，它们被用于重要的算法，如min-cut最大流算法。

有很多方法可以找到最小生成树，但是克鲁斯卡算法可能是最快最简单的手工操作。

1.找出下面图的最小生成树。它的总重量是多少?

示例图

显示答案

最小生成树如下图所示。总重量是31。

最小生成树

1. o艾普斯坦,D。生成树．2016年4月10日，从https://en.wikipedia.org/wiki/Spanning_tree
2. Benbennick D。维基百科的完全图．2016年5月21日，从https://en.wikipedia.org/wiki/Complete_graph
3. L。维基百科的连通图．2016年5月21日，从https://en.wikipedia.org/wiki/Connectivity_ (graph_theory)
4. L。维基百科的树．2016年5月21日，从https://en.wikipedia.org/wiki/Tree_ (graph_theory)
5. K。完全二部图．2016年5月21日，从https://en.wikipedia.org/wiki/Complete_bipartite_graph