最小生成树

在了解最小生成树之前，我们应该先了解生成树。

为了理解生成树的概念，请考虑以下图

上图可以表示为 G(V, E)，其中 'V' 是顶点的数量，'E' 是边的数量。上图的生成树将表示为 G`(V`, E`)。在这种情况下，V` = V 意味着生成树中的顶点数将与图中的顶点数相同，但边的数量将会不同。生成树中边的数量是原始图中边的数量的子集。因此，边的数量可以写成

E` € E

也可以写成

E` = |V| - 1

生成树中存在两个条件，如下所示

• 生成树中的顶点数应与原始图中的顶点数相同。
  V` = V
• 生成树中的边数应等于边数减 1。
  E` = |V| - 1
• 生成树不应包含任何循环。
• 生成树不应断开连接。

注意：一个图可以有多个生成树。

考虑下面的图

上图包含 5 个顶点。正如我们所知，生成树中的顶点将与图中的顶点相同；因此，V` 等于 5。生成树中的边数将等于 (5 - 1)，即 4。以下是可能的生成树

什么是最小生成树？

最小生成树是一个边的总和最小的生成树。考虑以下包含边权重的图

以下是我们可以从上图中制作的生成树。

• 第一个生成树是一棵树，其中我们移除了顶点 1 和 5 之间的边，如下所示
  上述树的边总和为 (1 + 4 + 5 + 2): 12
• 第二个生成树是一棵树，其中我们移除了顶点 1 和 2 之间的边，如下所示
  上述树的边总和为 (3 + 2 + 5 + 4) : 14
• 第三个生成树是一棵树，其中我们移除了顶点 2 和 3 之间的边，如下所示
  上述树的边总和为 (1 + 3 + 2 + 5) : 11
• 第四个生成树是一棵树，其中我们移除了顶点 3 和 4 之间的边，如下所示
  上述树的边总和为 (1 + 3 + 2 + 4) : 10。边成本 10 是最小的，因此它是一个最小生成树。

最小生成树的一般属性

• 如果我们从生成树中删除任何边，则它将断开连接。因此，我们不能从生成树中删除任何边。
• 如果我们在生成树中添加一条边，则会创建一个循环。因此，我们不能向生成树中添加任何边。
• 在一个图中，每条边都有一个独特的权重，那么只存在一个唯一的最小生成树。如果边权重不唯一，则可以有多个最小生成树。
• 一个完整的无向图可以有 n^n-2 个生成树。
• 每个连通的无向图至少包含一个生成树。
• 断开连接的图没有任何生成树。
• 在一个完全图中，我们可以删除最多 (e-n+1) 条边来构造一个生成树。

让我们通过一个例子来理解最后一个属性。

考虑下面给出的完全图

可以从上述完全图创建的生成树的数量等于 n^n-2 = 4^4-2 = 16。

因此，可以从上图中创建 16 个生成树。

可以删除的最大边数以构造生成树等于 e-n+1 = 6 - 4 + 1 = 3。