生成树

跨越树木是一个特殊的子图图形有几个重要的属性。首先，如果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. 跨越树有 $| N |- 1$边缘，在哪里 $| N |$是顶点的数量。

不同类型的图形具有不同数量的跨越树。以下是一些例子。

1）完成图表

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

完全图^[2]

2）连接的图形

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

连接的图形是简单的曲线图，该图必须具有小于或等于具有相同数量的顶点的完整图中的边缘的数量小于或等于边缘的数量。因此，连接图的生成树的数量是 $t（g_ \ text {connected}）\ leq | v | ^ {| v | -2}$．

连通图^[3]

3）树木

如果图形g本身是一棵树，则唯一的g唯一的生成树本身就是这样。所以一棵树 $| v |$顶点定义为 $T (G_ \文本{树})v = | | ^ {| v | 2}$．

树图^[4]

4)完全二部图

两分图是一个图形，其中每个节点都可以与两组之一相关联， $m$或 $N$．这些集合中的顶点仅连接到另一个顶点。没有设定的内部边缘。然后是一个完整的二分图是一个二分的图，其中设定的每个顶点 $m$连接到集合中的每个顶点 $N$，反之亦然。

二分钟图的生成树数由 $T (G_ \文本{complete-bipartite}) = m ^ {n} \ cdot n ^ {m - 1}$．

完整的二分图^[5]

5）一般图

为了计算一般图的跨越树的数量，是一个流行的定理是Kirchhoff的定理．

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

从这里，选择任意顶点，并从矩阵中删除其对应的行和列。这个新矩阵的决定因素是生成树 $T（g）$．

跨越树木可以在线性地找到 $o（v + e）$只是表演的时间广度优先搜索或深度首先搜索．这些图搜索算法只依赖于图中顶点的数量，所以它们非常快。

广度优先搜索将使用队列举起稍后探索顶点，深度首先搜索将使用a堆．在任何一种情况下，可以通过连接每个顶点来构建生成树 $V.$用发现它的顶点。

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

对于完整的图表，有一个确切数量的边缘必须删除以创建生成树。对于完整的图G，可以通过删除来计算生成树 $|e| - |v| + 1$边缘。在这个等式中， $| e |$是边缘的数量，还有 $| v |$是顶点的数量。

最小的生成树是生成树的变体。
用于未加权图G的最小生成树是一个生成树，最小化边缘或边缘权重的数量。
用于加权图G的最小生成树是生成树，其最小化树中边缘的权重。

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

加权生成树

加权最小生成树

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

有很多方法可以找到最小的生成树，但是Kruskal的算法可能是手工最快，最容易做的。

1.找到下图的最小生成树。它的总重量是多少？

示例图

显示答案

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

最小的生成树

1. 埃普斯坦，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. A，L.维基百科连接图形．2016年5月21日，从https://en.wikipedia.org/wiki/connectivity_（graph_theory）
4. A，L.维基百科的树．2016年5月21日，从https://en.wikipedia.org/wiki/tree_(graph_theory）
5. A，K。完全二部图．2016年5月21日，从https://en.wikipedia.org/wiki/complete_bipartite_graph.