最后更新: 2025-01-21 16:26 查看: 79 次纠错评论(0) 课件开VIP

最小生成树 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 }$ ，矛盾。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：生成树

下一篇：没有了

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