生成树和最小生成树
提示
- 生成树定义:生成树是无向连通图的子图,包含所有顶点并尽量少使用边。完全图上带有 n 个顶点的生成树数量等于
n^(n-2)
。 - 最小生成树概念:最小生成树是生成树的一种,它特指边的权重和最小的生成树。
- 应用领域:生成树在计算机网络路由协议和土木网络规划中有应用,而最小生成树用于地图路径寻找和设计电信网络、供水网络和电网。
在学习生成树之前,我们需要了解两种图:无向图和连通图。
无向图是指边不指向任何方向(即边是双向的)的图。
连通图是指总能从一个顶点到达另一个顶点的图。
生成树
生成树是无向连通图的一个子图,它包含图中的所有顶点,并尽可能少地使用边。如果漏掉了一个顶点,那么它就不是生成树。
边可能有或没有分配权重。
从完全图创建的带有 n
个顶点的生成树的总数等于 n(n-2)
。
如果我们有 n = 4
,那么可能的最大生成树数量等于 4^4-2
= 16
。因此,可以从具有 4 个顶点的完全图形成 16 个生成树。
生成树的示例
让我们通过以下示例来理解生成树:
原始图为:
从上图创建的一些可能的生成树是:
最小生成树
最小生成树是一种生成树,其边的权重之和尽可能小。
最小生成树的示例
让我们通过以下示例来理解上述定义。
初始图为:
从上图创建的可能的生成树是:
从上述生成树中找到的最小生成树是:
从图中找到最小生成树的算法有:
生成树的应用
- 计算机网络路由协议
- 聚类分析
- 土木网络规划
最小生成树的应用
- 在地图上寻找路径
- 设计网络,如电信网络、供水网络和电网。