数学建模案例分析-- 图与网络方法建模4通讯网络的最小生成树

《数学建模案例分析-- 图与网络方法建模4通讯网络的最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§4通讯网络的最小生成树连通的无圈图称为树。树是最简单但又是十分重要的一类图，它在许多学科领域中有广泛的应用，例如分子结构，电网络分析等。最短连接问题与树有关，学科分类和一些决策过程也往往可以用树的形式表示。图，则下面关于树的命题是等价的。（1）是一个树。（2）无圈，且。（3）连通，且。（4）无圈，但加一新边即得唯一一个圈。（5）连通，但舍去一边就不连通。（6）中任意两点，有唯一链相连。上述性质中每一个命题均可作为树的定义，它们对判断和构造树将极为方便。若是连通图的生成子图，且本身是树，则称为的生

2、成树。对图的每一条边赋以相应的实数权，得到一个网络，记为。设是的一个生成树，令，则称为的权，中权最小的生成树称为的最小生成树。许多实际问题，如在若干个城市之间建造铁路网、输电网或通信网等，都可归纳为寻求连通赋权图（网络）的最小生成树问题。例如已知城市和间的直通线路的造价为要求一个总造价为最小的设计方案。又如一个城市中，对若干新建居民点供应自来水和煤气，已测知连接各点间的直通管道的造价，要求给出一个总造价最小的铺设方案等等。下面介绍在给定网络内求最小生成树的两种算法。设网络点数为，此时最小生成树的边

3、数为。算法1（克鲁斯凯尔，Kruskal）算法I的中心思想是每次添加权尽可能小的边，使新的图无圈，直到生成最小生成树为止。也形象地简称“最小边的加入法”。其步骤如下：（1）把内的所有边按照权的非减次序排列。（2）按（1）排列的次序检查中的每一条边，如果这条边与已得到的边不产生圈，则取这一条边为解的一部分。（3）若已取到条边，算法终止。此时以为顶点集，以取到的条边为边集的图即为最小生成树。例1求图1所示网络的最小生成树。解按各边的权的非减次序将网络中的8条边排列为首先取和为所求最小生成树的两条边，然

4、后检查边。由于边、和构成圈，故不取边，考虑。由于、和不构成圈，故可取。然后检查。由于、、和不构成圈，故可取。此时由、、和构成的生成树即为网络的最小生成树（如图2）。122344421322图1图2算法II　（普赖姆，Prim）这是一种迭代算法，每进行一次迭代将产生组成网络最小生成树的一条边。其作法基于下面的事实：如果我们已经知道中的一些边，它们的端点集为，则是的顶点的一个子集。以记一个端点在中、另一端点在中的所有边组成的集合，由于最小生成树是的连通生成子图，中权最小的一条边，应该也是的最小生成树中

5、的一条边。下面通过对图1所示的网络求最优树的过程介绍这一算法。算法开始时，，。由于，取，并把不在中的一个端点加入中。于是，，中权最小的边为和。任取一条边，例如加入中，把不在中的另一端点加进中。此时，，从而，其中权最小的边为。不在中的一个端点为，取新的，，从而，其中权最小的边为。不在中的一个端点为，从而取，。此时以为顶点集，为边集的树即为的最小生成树。我们将上述过程一般化。设，，为边的权。如果和之间无边相连，则取。为叙述方便，我们以顶点的下标来表示中的顶点。普赖姆迭代过程如下：（1），此处。（2）设

6、，记。以代替，代替，代替。（3）若，算法终止，此时即为所求；否则，对每个,以代替，返回上一步骤（2）。应用该算法求得例1（图1）中的网络的最优树（如图2）。克鲁斯凯尔用于手工计算小型网络的最小生成树是比较好，而且直观易懂，但应用较大型网络时效率不高，基于这种算法的计算机软件也较难实现。普赖姆方法克服了这些缺点，但遗憾的是普赖姆方法应用于小型问题时却过分的繁复。