最后更新: 2025-01-22 09:44 查看: 86 次纠错评论(0) 课件开VIP

最小生成树

定义 10.10 （最小生成树）设 $G(V, E, \omega)$ 是带权连通简单图，$\omega$ 是从 $E$ 到正实数集的函数。又设 $T$ 是 $G$ 的一棵生成树，$T$ 中所有枝的权之和称为 $T$ 的权，记为 $W(T)=\sum_{\{i, j\} \in T} \omega(i, j)$ 。具有权 $\min _T W(T)$ 的生成树称为最小生成树。

如图 10.2 所示，图（a）给出带权连通简单图，图（b）为其最小生成树。

本节将给出在给定的一个带权连通图中求最小生成树的算法。这个问题是具有实际意义的。例如，$G$ 中的点表示城市，边表示城市间的道路，边的权表示对应道路的长度，现在我们沿着道路架设通信线路，将这些城市联系起来，要求架设的线路最短，这个问题就是求一棵最小生成树的问题。

下面我们介绍一种求最小生成树的克鲁斯科尔（Kruskal）算法。先看一个例子。
例10．1 求图 10.3 中带权连通图 $G(V, E, \omega)$ 的最小生成树。克鲁斯科尔算法的步骤，通俗地说，就是先将 $G$ 中的边按权从小到大顺序排列，再从小到大依次取出每一边作检查。—开始取权最小的边，由该边导出一个部分子图，然后依次每取一边加入已得的部分子图。若保持无回路，将该边与原有部分子图中的边导出一个新的部分子图；若得到回路，将该边放弃。上述过程继续进行，直到所有边均检查完，得到的生成子图就是所求的最小生成树，过程如图 10.3 所示。
 ![图片](/uploads/2025-01/904825.jpg)
 
 克鲁斯科尔算法：设 $G(V, E, \omega)$ 是有 $n$ 个顶点的带权连通简单图。
（1）在 $G$ 中选一边 $e_1$ ，使 $\omega\left(e_1\right)$ 最小，令 $E_1=\left\{e_1\right\}, 1 \rightarrow i$ 。
（2）若已选出 $E_i=\left\{e_1, e_2, \cdots, e_i\right\}$ ，那么从 $E-E_i$ 中选取一边 $e_{i+1}$ ，满足：
（1）$E_i \cup\left\{e_{i+1}\right\}$ 的导出子图中不含回路。同时
（2）$\omega\left(e_{i+1}\right)$ 为最小。
（3）若 $e_{i+1}$ 存在，则令 $E_{i+1}=E_i \cup\left\{e_{i+1}\right\}, i+1 \rightarrow i$ ，转（2）；若 $e_{i+1}$ 不存在，则停，此时 $E_i$ 导出的子图就是所求的最小生成树，记为 $T_{\text {。 }}$

现在来证明上述算法的正确性。
定理 10.8 克鲁斯科尔算法所得到的图 $T$ 是最小生成树。
证明：首先证明由定理10．1等价定义（4）便知 $T$ 是 $G$ 的一棵生成树。并由等价定义（2）可知边数为 $n-1$ 。

下面证明 $T$ 是最小生成树即可。用反证法证明，假设 $T$ 不是 $G$ 的最小生成树，而 $S$ 是 $G$ 的最小生成树，并且 $W(S)<W(T)$ 。在生成树 $T$ 中有 $n-1$ 条边，按权从小到大的顺序排列为 $e_1, e_2, \cdots$ ， $e_k, \cdots, e_{n-1}$ 。若 $e_k$ 是不在 $S$ 中的第一条边，也就是说 $e_1, e_2, \cdots, e_{k-1}$ 是 $S$ 和 $T$ 的公共边。现在对 $S$ 进行基本变换，在 $S$ 中加边 $e_k$ 得到一条基本回路，记为 $C$ ，在 $C$ 中必有一边 $e^{\prime} \in S$ ，但 $e^{\prime} \notin T$ ，否则 $T$ 中有回路，导致矛盾。再从 $S \cup e_k$ 中删去 $e^{\prime}$ ，得到生成树 $S^{\prime}$ ，由于 $w\left(e_k\right) \leqslant w\left(e^{\prime}\right)$ ，所以 $W\left(S^{\prime}\right) \leqslant W(S)$ ，
并且 $S^{\prime}$ 与 $T$ 的公共边比 $S$ 与 $T$ 的公共边多一条。重复上述过程，每一步作一次树的基本变换，使总权数减少，最后生成树 $S$ 变换到生成树 $T$ ，且 $W(T) \leqslant W(S)$ ，与假设 $W(S)<W(T)$ 相矛盾。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：生成树与割集

下一篇：数的计数

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