生成树和最小生成树

提示

1. 生成树定义：生成树是无向连通图的子图，包含所有顶点并尽量少使用边。完全图上带有 n 个顶点的生成树数量等于 n^(n-2)。
2. 最小生成树概念：最小生成树是生成树的一种，它特指边的权重和最小的生成树。
3. 应用领域：生成树在计算机网络路由协议和土木网络规划中有应用，而最小生成树用于地图路径寻找和设计电信网络、供水网络和电网。

在学习生成树之前，我们需要了解两种图：无向图和连通图。

无向图是指边不指向任何方向（即边是双向的）的图。

连通图是指总能从一个顶点到达另一个顶点的图。

生成树

生成树是无向连通图的一个子图，它包含图中的所有顶点，并尽可能少地使用边。如果漏掉了一个顶点，那么它就不是生成树。

边可能有或没有分配权重。

从完全图创建的带有 n 个顶点的生成树的总数等于 n(n-2)。

如果我们有 n = 4，那么可能的最大生成树数量等于 4^4-2 = 16。因此，可以从具有 4 个顶点的完全图形成 16 个生成树。

生成树的示例

让我们通过以下示例来理解生成树：

原始图为：

从上图创建的一些可能的生成树是：

最小生成树

最小生成树是一种生成树，其边的权重之和尽可能小。

最小生成树的示例

让我们通过以下示例来理解上述定义。

初始图为：

从上图创建的可能的生成树是：

从上述生成树中找到的最小生成树是：

从图中找到最小生成树的算法有：

1. 普里姆算法 (Prim's Algorithm)
2. 克鲁斯卡尔算法 (Kruskal's Algorithm)

生成树的应用

• 计算机网络路由协议
• 聚类分析
• 土木网络规划

最小生成树的应用

• 在地图上寻找路径
• 设计网络，如电信网络、供水网络和电网。