图与网络方法建模4天然气管道铺设方案.doc

§4 天然气管道铺设方案 连通的无圈图称为树。树是最简单但又是十分重要的一类图，它在许多学科领域中有广泛的应用，例如分子结构，电网络分析等。最短连接问题与树有关，学科分类和一些决策过程也往往可以用树的形式表示。 若是连通图的子图，它们有相同的顶点，称是连通图的生成子图。 若是连通图的生成子图，且本身是树，则称为的生成树。 对连通图的每一条边赋以相应的实数权，得到一个网络，记为。设是的一个生成树，令，则称为的权，中权最小的生成树称为的最小生成树。 下面介绍在给定网络内求最小生成树的两种算法。设网络点数为，此时最小生成树的边数为。 算法1 （克鲁斯凯尔，Kruskal） 算法I的中心思想是每次添加权尽可能小的边，使新的图无圈，直到生成最小生成树为止。也形象地简称“最小边的加入法”。其步骤如下： （1）把内的所有边按照权的非减次序排列。 （2）按（1）排列的次序检查中的每一条边，如果这条边与已得到的边不产生圈，则取这一条边为解的一部分。 （3）若已取到条边，算法终止。此时以为顶点集，以取到的条边为边集的图即为最小生成树。 例1 求图1所示网络的最小生成树。 解 按各边的权的非减次序将网络中的8条边排列为 首先取和为所求最小生成树的两条边，然后检查边。由于边、和构成圈，故不取边，考虑。由于、和不构成圈，故可取。然后检查。由于、、和不构成圈，故可取。此时由、、和构成的生成树即为网络的最小生成树（如图2）。 1 1 2 2 3 4 4 4 2 1 3 2 2 图1 图2 算法II　（普赖姆，Prim） 这是一种迭代算法，每进行一次迭代将产生组成网络最小生成树的一条边。其作法基于下面的事实：如果我们已经知道中的一些边，它们的端点集为，则是的顶点的一个子集。以记一个端点在中、另一端点在中的所有边组成的集合，由于最小生成树是的连通生成子图，中权最小的一条边，应该也是的最小生成树中的一条边。下面通过对图1所示的网络求最优树的过程介绍这一算法。 算法开始时，，。由于，取，并把不在中的一个端点加入中。于是，，中权最小的边为和。任取一条边，例如加入中，把不在中的另一端点加进中。此时，，从而，其中权最小的边为。不在中的一个端点为，取新的，，从而，其中权最小的边为。不在中的一个端点为，从而取， 。此时以为顶点集，为边集的树即为的最小生成树。 我们将上述过程一般化。设，，为边的权。如果和之间无边相连，则取。为叙述方便，我们以顶点的下标来表示中的顶点。普赖姆迭代过程如下： （1），此处。 （2）设，记。以代替，代替，代替。 （3）若，算法终止，此时即为所求；否则，对每个,以代替，返回上一步骤（2）。 应用该算法求得例1（图1）中的网络的最优树（如图2）。 克鲁斯凯尔方法用于手工计算小型网络的最小生成树是比较好，而且直观易懂，但应用较大型网络时效率不高，基于这种算法的计算机软件也较难实现。普赖姆方法克服了这些缺点，但遗憾的是普赖姆方法应用于小型问题时却过分的繁复。 许多实际问题，如在若干个城市之间建造铁路网、输电网或通信网等，都可归纳为寻求连通赋权图（网络）的最小生成树问题。例如已知城市和间的直通线路的造价为 要求一个总造价为最小的设计方案。又如一个城市中，对若干新建居民点供应自来水和煤气，已测知连接各点间的直通管道的造价，要求给出一个总造价最小的铺设方案等等。 例2 我国西部某地区共有1个市(标记为1)和9个县(标记为2—10)组成，该地区打算使用天然气，其中城市1含有井源。现在要设计一个供气系统，使得从城市1到每个县城都有一条管道相连，并且铺设管道的总长度尽可能少。下图给出了该地区的地理位置图。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ 下表给出了各县市之间的距离（单位：公里）。 2 3 4 5 6 7 8 9 10 1 8 5 9 12 14 12 16 17 22 2