最后更新: 2025-01-21 16:26 查看: 40 次反馈刷题

最小生成树 MST

## 最小生成树 MST Minimum Spanning Tree
－考虑边有权重的连通无向图。其生成树可能不唯一。定义生成树的权重为其所含各边之和。一个带权连通图的最小生成树是其权重最小的生成树。
－注意，这里的最小（Minimum）并不意味着唯一。
－最小生成树有广泛的应用。

## Prim算法（求最小生成树）

1： $E =\{ e \}, e$ 是权最小的边
2：从E以外选择与 $E$ 里顶点关联，又不会与E中的边构成回路的权最小的边加入 $E$
3：重复第 2 步，直到 E 中包含 $n -1$条边
算法结束

## 例题
铺设一个连接各个城市的光纤通信网络（单位：万元）。
 ![图片](/uploads/2025-01/f6b466.jpg)
 
 
 ## Kruskal算法（求最小生成树）

1： $E =\{ \}$
2：从E以外选择不会与E中的边构成回路的权最小的边加 $\lambda E$

3：重复第2步，直到 E 中包含 n－1条边
算法结束
铺设一个连接各个城市的光纤通信网络（单位：万元）
 ![图片](/uploads/2025-01/598f32.jpg)
  ![图片](/uploads/2025-01/07b459.jpg)
  
  
 ## 引理（更换生成树的边）
－$T$ 与 $T^‘$ 均是图 $G$ 的生成树，若 $e \in E_T$ 且 $e \notin E_T$ ，则必有 $e^{\prime} \in E_T$ ， $e ^{\prime} \notin E _{ T }$ ，且T－\｛e\}U\{ $\left.e ^{\prime}\right\}$ 和 $T ^{\prime}-\left\{ e ^{\prime}\right\} \cup\{e\}$ 均是 $G$ 的生成树。
－设 $==u v, T-\{e\}$ 必含两个连通分支，设为 $T_1, T_2$ 。因 $T^{\prime}$ 是连通图， $T ^{\prime}$ 中有 uv －通路，其中必有一边满足其两个端点 $x , y$分别在 $T_1, T_2$ 中，设其为 $e^{\prime}$ ，显然 $T-\{e\} \cup\left\{e^{\prime}\right\}$ 是生成树。
而 $T^{\prime}-\left\{e^{\prime}\right\}$ 中 $x, y$ 分属两个不同的连通分支，但在 $T^*=T^{\prime}-$ $\left\{e^{\prime}\right\} \cup\{e\}$ 中，$x u-$ 通路 $+e+v y$ 通路是一条 $x y-$ 通路，因此 $T^{\prime}-$ $\left\{e^{\prime}\right\} \cup\{e\}$ 连通，从而 $T^{\prime}-\left\{e^{\prime}\right\} \cup\{e\}$ 是生成树。
 ![图片](/uploads/2025-01/9567ce.jpg)
 
 ## Kruskal算法的正确性
－显然 T 是生成树。
－按在算法中加边顺序，T中边是 $e _1, e _2, \ldots e _{ k -1}, e _{ k }, \ldots e _{ n -1}$ 。
－假设T不是最小生成树。对于任意给定的一棵最小生成树 $T^{\prime}$ ，存在唯一的 $k$ ，使得 $e _{ k } \notin E _{ T }$ ，且 $e _i \in E _{ T }$ ，使得 $(1 \leq i< k )$ 。设 $T ^{\prime}$是这样的一棵最小生成树，使得上述的k达到最大。
－根据前述引理， $T ^{\prime}$ 中存在边 $e ^{\prime}$ ， $e ^{\prime}$ 不属于 T ，使得 $T ^*= T ^{\prime}$－ $\left\{e^{\prime}\right\} \cup\left\{e_k\right\}$ 也是生成树。 $e^{\prime} \in T^{\prime}$ 与 $e_1, e_2, \ldots e_{k-1}$ 不会构成回路，因此 $w\left(e^{\prime}\right) \geq w\left(e_k\right)$ ．所以 $w\left(T^*\right) \leq w\left(T^{\prime}\right)$ ，即 $T^*$ 也是最小生成树。但 $T ^*$ 包含 $e _1, e _2, \ldots e _{ k -1}, e _{ k }$ ，矛盾。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：生成树

下一篇：没有了

本文对您是否有用？有用 (0) 无用 (0)