19个村庄铺设天然气管道

19个村庄铺设天然气管道

摘 要

本文是关于图论的问题，对19个村庄建立模型，来分别求管道铺设问题和各个最短路程问题。我们把19个村庄看成19个顶点，各村庄之间的公路看成图的边，公路的长度看成图的权重，则村庄公路图即为一无向赋权图。

问题一：根据题目要求，每个村庄铺设管道，使铺设费用最少，即图论最小生成树树的问题。经过比较和实验，最终求得的解为问题的精确解。

问题二：每条路至少走一遍，最终回到出发点，典型的中国邮路问题。建立模型求解，并且通过数据验证了我们所建的模型的正确性与稳定性。

问题三：检修员从村庄1出发，到每个村庄检查天然气状况，最后返回村庄1，怎样走才能使检修员走的总路程最短。这是典型的旅行推销商问， 是至今为解决的难题之一。我们对题设稍做改善，使其转化为求最短H回路的问题。

一、问题重述

某地区共有19个村庄, 各村庄之间的距离(单位为km) 如图所示, 图中每条连线表示有公路相连. 现要沿公路铺设天然气管道. 铺设管道的人工和其他动力费用为1万元/km, 材料费用为2万元/km.

(1): 如果每个村庄均通天燃气, 应如何铺设管道, 才使总的铺设费用最少? (2): 天然气公司决定在铺设管道前, 派人先查看所有公路的状况, 以便决定该公路是否可用. 他们从村庄1出发, 最后又回到村庄1. 问他们应如何走, 才使走的总路程最少?

(3): 某检修员从村庄1出发, 到每个村庄检查天然气状况, 最后又回到村庄1. 他应如何走, 才使走的总路程最少?

19个村庄铺设天然气管道

二、模型假设

1、假设村庄A与村庄B之间没有公路相连，则村庄A与村庄B无法直接行走，必须绕过其他村庄。

2、假设所给数据均为准确数据，无任何偏差。

3、对于问题二假设铺设管道之前，公司只派一队人去视察公路状况。

4、假设村庄A与村庄B之间没有公路相连，则在赋权图中两顶点之间的权重为无穷大。

三、符号说明

v1，v2，…，v19 19个村庄的标记，看成顶点 S，S1 ，S2，… 分别表示集合

G(V，E) 村庄公路图组成的一赋权图

G′(V,E) 村庄公路图的等价完全赋权图 W 各城市之间最短距离形成的矩阵

Fi Wi中第i行中除0以外的最小值 Fj Wi中第j列除0以外的最小值 Fij 罚函数 Fij=Fi+Fj

d（Si，SiC） 表示集合Si 到其补集的最短距离 d（v，u） 表示两顶点之间的距离

Pij 表示顶点两顶点vi，vj之间的最短路径 w（vi，vj） 表示顶点vi，vj之间的权重

四、问题分析与模型的建立

19个村庄公路图看成赋权图后，我们就来研究这个问题。 第一问：

此问要求每个村庄均通天然气，使得铺设管道费用最少。不难看出，

要使铺设费

19个村庄铺设天然气管道

用最少，即使得要铺设管道的总长度最短，而题干说明管道要沿着公路铺设，那么就要设计一个总路程最小的线路网把这些村庄都连通起来，这就是所谓的连通问题，这就可以归结为在赋权图G=（V，E）中寻求生成树T，即找出权的最小的连通子图——最小生成树。

设已给出无向赋权图G(V,E)，其中V={v1，v2，…，vn}，E={e1，e2，…，em}。令

w(T)=∑w e 其中e∈T

为G的生成树T的加权和，其中w e 为图中边e的权重。若T*为G的生成树且满足：

w(T*)=min{w(T)|T为G的生成树}

则称T*为G的最小生成树。我们不妨选用Prim算法。

Prim算法思想如下：先从E中任选一点构成E*，然后在E-E*中任选一条到E*中某点（比如v）权最小的边uv进入解，并令E*=E*∪{u}，直至E*=E，即得最小生成树。 第二问：

铺设管道之前，派人查看所有公路状况，先从村庄1出发，最后又回到村庄1。由于公司只派一队人查看所有村庄的状况，即问题转化为由我国的管梅谷教授于1962年提出的中国邮递员问题（邮递员从邮局取走信件，需走遍他所管理的所有街道把信件发出去，然后返回邮局退回未送走的信件），就是要在赋权图G(V，E)中找一条最优环游。用图论的术语，即在一个连通的赋权图G(V，E)中，要寻找一个回路，使包含G中每条边至少一次，且该回路的权重最小。该题G(V，E)不是欧拉图，即存在奇度数的节点。我们用奇偶点图上作业法来求最优环游。

奇偶点图上作业法（求最优环游算法）：

(1)把 G 中度为奇数的顶点两两配对，记为 x1,x2, ,xk,y1,y2, ,yk。对每个 i(i 1,2, ,k)， G中取一条

xi yi 路P ，将 P 上的每

ii

一条边都添加一条边，从而得到 G 的一个赋权Euler生成母图 G*。

(2)去掉G* 中关于 G的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。

(3)检查G的每一个回路，如果某个回路C上多重边e的权和超过此回路权和的一半，则将C进行调整：删除 e ， C e 的边重数增加 1。 (4)用Fleury算法求G*的Euler环游。

Fleury算法给出了寻找Euler回路的一个简单算法：任选G中一顶点为初始点v0，如果通路u=v0，e1，v1，…，ei，vi已选出，那么则在

E-{e1，e2，…，ei}

中选出与vi关联的边ei+1，且不是Gi=G-{ e1，e2，…，ei }的断边，即Gi-{ei+1}仍连通，从而得通路u=v0，e1，v1，…，ei+1，vi+1。如此反复，直至G的所有边被选出，即得G的Euler回路。

第三问：

某检修员从村庄1出发，到每个村庄检查天然气状况，最后又回到村庄1，即对于图G(V,E)求从顶点v1开始，寻找一回路H，使其经过图G(V,E)的每一个顶点至少一次，最终又回到v1。这是典型的旅行推销商问题。我们对题设做些改变，使其转化为求H回路的问题。由于有些村庄之间并没有公路直接相通，无法直接行走，即赋权图G(V,E)有的两顶点之间并没有边相连。 我们先求出所有顶点之

19个村庄铺设天然气管道

中任意两顶点vi，vj之间的最短路径Pij，其权重为w（Pij）。即：

w(Pij)=min{w(P)|P为G（V，E）中vi到vj的所有路径}

求任何两点之间的最短路径，最好的方法是Dijkstra算法，其算法基本思想如下：

设S是V的真子集，u0∈S， 。如果P=u0…是从u 0到的最短路，则∈S，并且P的（u0，）段是最短的（u0，

d（u0，）= d（u0，+w（，）

并且 d（u0，=min{ d（u0，u）+w（u，v）} 其中u∈S，v∈（1） （1）式是Dijkstra算法的基础。从集S0={u0}出发，计算

d（u0，0）=min{w(u0，v)} 其中v∈0，

并选取u1∈0，使d(u0，u1)= d（u0，0）；令S1={ u0，u1}，P= u0u1。一般地，若Sk={u0，u1，…，uk}及相应的最短路P1，P2，…，Pk已经确定，由公式（1）算出d（u0，k）并选取顶点uk+1∈k,使得d(u0，uk+11)= d（u0，k），此时

d(u0，uk+11)= d(u0，uj)+w（uj，uk+1）对某个j≤k成立，将边ujuk+1连接到路Pj上，可得（u0，uk+11）的最短路。如果v0= uk+11,则结束，否则重复上述过程。 算法具体步骤

（1）初始时，S只包含源点，即S=v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或 U中顶点u距离小于边上的权（若u不是v的出边邻接点）。

（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中。 用上述方法求的任何两顶点之间的最短路后，由这些最短路我们可以绘制一完全Euler图G′，其权重我们可以组成一19阶的矩阵。我们对G′来求H回路，则求得的解我们可以转化成在原赋权图G(V,E)上的行走路线，此时每个村庄至少行走一次。对于求H回路，我们采用分枝定界法。基本思想：

分枝限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

在分枝限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

19个村庄铺设天然气管道

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 以例题来说明其方法是：

设有矩阵

W

它表示四个城市之间的距离，以此求最短回路。

1) 简化并确定W的下界。各行减去最小元素，然后各列减去最小元素，得W1，显然最短H回路的解的方案不受影响，若W1中零元素对应的边构成H回路，则该H回路最短。因此，W行列简化后的总量构成原问题的一个下界L.B(各行各列最小值的总和,L.B=3+3+5+4+1=16。继续求解得的H回路之权不会优于该下界。

W1

3

3

569 7

2) 分枝并确定分枝的下界。W1中零元素对应的边不构成H回路，但仍可选择一些零

元素对应边构成回路，为了在多个零元素中择优选择一个，引入罚函数Fij（假设中提到过），以零元素对应的最大罚函数max =0{ }确定的v2v1（或v4v3，v3v1，）作为分枝条件，其含义是：若回路中不包含v2v1，则引起的损失最大，此时在W1中置w2 1=∞，化简后的W3，且L.B.（W3=16+1=17）；若回路中包含v2v1，则可使最终H回路的增值量减少最多，此时回路不能包含v14v13，否则会形成子回路v2v1v2，且以后不再考虑v2v1，故在W1中删去v2v1坐在的行列的元素，并置w12=∞，化简后的W5，并且L.B.=16+3+1=20

00

015 3

W3

3)继续分枝定界。由于L.B.(W3)<L.B.(W5),故从W3分枝，分枝变为v3v1，

若回路中不包含v3v1，则置w31=∞，，有W3得W7，且L.B..（W7）=17+5=22；若回路中包含v3v1,则在W3中删去v3v1所在的行列元素，并置w13=∞，得W8，且L.B.(W8)=17.

W7

由于L.B.(W8)<L.B.(W5)<L.B.(W7)，故对W8分枝，以v1v2为分枝边。若回路中不包含v1v2，则置w12=∞，由W8得W9，化简的W10，且L.B.（W10）=17+3+3=23；若回路中包含v1v2，则在W8中删去v1v2所在的行列元素，得W11，且L.B.(W11)=17。

W10

W11

0

0153

W5 0

2

0

010 3

W8

3

3

显然，W11中的零元素构成回路，故H回路为{v3v1，v1v2，v2v4，v4v2 }，

19个村庄铺设天然气管道

其权为L.B.（W11）=177.由于除根外的各分支点的下界皆劣于17，故其为最短H回路。

五、模型的求解

问题一

我们设村庄1到19为顶点v1，v2，…，v19 设S1={v1}，S1C={v2，v3，…，v19}求

d（S1，S1C）= min{d(v1,u)+w(u,v)}， 其中u∈S1，v∈S1C 容易看出，d（S1，S1C）=d（v1，v2）

即把v2加入到S1中，设S2={v1，v2}=S，S2C={ v3，…，v19},再求 d（S2，S2C）=min{ d(u,v)}， 其中u∈S2，v∈S2C

同样，再把v8加入到S2中，设S3={ v1，v2，v8}=S，S3C={ v3，…，v7，v9，…，v19}，再求

d（S3，S3C）=min{ d(u,v)}， 其中u∈S3，v∈S3C 以此类推，直到把所有的顶点都加入到S中，便可求出图G(V，E)的最小生成树，如下图所示：

19个村庄铺设天然气管道

上图即为铺设管道的图示，所铺设的管道长度为5250km又铺设管道的人工和其他动力费用为1万元/km, 材料费用为2万元/km.即得

铺设管道的所有费用=5250×（2+1）=15750万元

即如上图铺设天燃气管道所需费用最少，费用为15750万元

问题二

我们设村庄1到19为顶点v1，v2，…，v19，村庄公路图记为G，村庄之间的距离记为权重。

第一步：先找出奇节点：v2，v3，v6，v7，v8，v10，v11，v12，v16，v17，v18，v19，把节点进行配对，不妨把v2 与v8 ，v3 与v10 ，v6与v7 ，v11与v12 ，v16 与v18， v17与 v19配对，对每对配对的顶点，在G中取连接两顶点的边记为Pi（i=1，2…6）将 Pi上的每一条边都添加一条边，从而得到 G的一个赋权Euler生成母图G*。

*

第二步：若G 中关于G的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点，直到每一对相邻顶点至多由2条边连接。容易得出该题的生成母图G*不需此步骤。 第三步：检查G的每一个回路，如果某一个回路C上多重边的权重和超过此回路权和的一半，则将C上原来无重边的边各添加一条重边，而将C上的各多重边分别删去一条边，进行调整。重复这一过程，直至对G的所有回路，其多重边的权不超过此回路的权和的一半，得G**。容易看出我们只需对连接v11与v12的边进行调整即可。得出要求的结果如下图所示：

19个村庄铺设天然气管道

**

第四步：用Fleury算法求G的欧拉环游。则工作人员可按如下方法行走：

8 15 19 17 18 19 7 6 7 11 12 11 10 10 12 16 18 16 2 1

按以上方法走所走路程最短，最短路程为14650km

问题三

我们采用c++编程来求各顶点的最短路，编程内容如下：

#include<fstream> #include<cstring> using namespace std;

const int MaxNum=1000000; //边权最大值 int n; //节点数目

int dist[501]; //到节点1的最短路径值 bool state[501]; //节点被搜索过状态指示

19个村庄铺设天然气管道

int data[501][501]; //邻接矩阵

//查找权值最小的节点 int findmin() {

int minnode=0, min=MaxNum; for(int i=1; i<=n; i++)

if ((dist[i]<min) && (!state[i])) {

min=dist[i]; minnode=i; }

return minnode; }

int main() {

ifstream in("dijkstra.in"); ofstream out("dijkstra.out"); memset(state, 0, sizeof(state)); in >> n;

for(int p=1; p<=n; p++)

for(int q=1; q<=n; q++) {

in >> data[p][q];

if (data[p][q]==0) data[p][q]=MaxNum; }

//初始化

for(int i=1; i<=n; i++) dist[i]=data[1][i]; state[1]=true; int done=1;

while (done<n) {

int node=findmin(); if (node!=0) {

done++; //找到的点的数目加1

state[node]=true; //标记已经找到了从节点1到节点node的最短路径

19个村庄铺设天然气管道

for(int i=1; i<=n; i++)//更新还没有找到的点的路径值

if ((dist[i]>dist[node]+data[node][i]) && (!state[i])) dist[i]=dist[node]+data[node][i]; }

else break; }

for(int k=1; k<=n; k++) {

if (dist[k]==MaxNum) out<<-1; else

out<<dist[k]; if (k==n) out<<endl; else

out<<" "; }

in.close(); out.close(); return 0; }

由上可求的各顶点之间的最短路如下：

结合题目可知，我们应把w矩阵的对角线上的元素改为∞。接下来利用分枝定界法：

1）简化并确定W的下界。各行减去最小元素，然后各列减去最小元素，得

W1，显然最短H回路的解的方案不受影响，若W1中零元素对应的边构成H回路，则该H回路最短。因此，W行列简化后的总量构成原问题的一个下界L.B(各行各列最小值的总和,L.B=5650。继续求解得的H回路之权不会优于该下界。

19个村庄铺设天然气管道

300600105085011001600500700W 1100

135013001250145016501300180016002200

02507505507501000200400

W1 800

1000100095011501350950150013001500

2) 分枝并确定分枝的下界。W1中零元素对应的边不构成H回路，但仍可选择一些零元素对应边构成回路，为了在多个零元素中择优选择一个，引入罚函数Fij（假设中提到过），以零元素对应的最大罚函数max =0{ }确定的v13v14（或v14v13，v14v54，v15v14）作为分枝条件，其含义是：若回路中不包含v13v14，则引起的损失最大，此时在W1中置w13 14=∞，化简后的W3，且L.B.（W3=5650+200=5850）；若回路中包含v13v14，则可使最终H回路的增值量减少最多，此时回路不能包含v14v13，否则会形成子回路v13v14v13，且以后不再考虑v13v14，故在W1中删去v13v14坐在的行列的元素，并置v14v13=∞，化简后的W5，并且L.B.=5650+200=5850.

02507505507501000200400

W3 800

1000100075011501350950150013001500

300

600

300

300750550800130020040080010501000950115013501000150013001900

1050750450

4502505001000500500500750700125014501650950145012501850

200450950950900450700650170019002000900140012001800

850550250200

250750750700250500450150017001800700120010001600

1100160080013005001000450950250750 500500 100015009501450500100025075070012501750225019502450205023509501450145017501250175018501150500700200400500500950900750700100095015001450 200200 65045090070085065075095095011501150135080060013001100110090017001500110013501300125014501650130018008001050100095011501350100015005007507001250145016509501450450700650170019002000900140025050045015001700180070012005002507001750195020509501450100075012502250245023501450175065090085075095011508001300450700650950115013506001100 250200140016001550450950250 4501650185018007001200200450 160015501350250750140016501600 20040015001000160018501550200 2001300800155018001350400200 1100600450700250150013001100 50095012007501000800600500 750100055012001000800300200135016001150160014001200900600

16001300125012001000125017501100900750100055012001000800300200

600

1300110010000800100012509007005507503501000800600500

25050

5055035055080002006008008007509501150750130011001300

2000200250250250250450450100012001400650120010001200

750550200

0200450750700250450450150017001800650120010001200

55035000

02505505005025025013001500160045010008001000

10501000950115013509508508007509501150750500450100012001400650500450150017001800650300250130015001600450

04501500170018006500 2507501750195018509008001050 70065055075095055075010000 5004507509501150350300550450250 50012001400135020002506504500 2001400160015504005008506504500250 140013501150015501800550750120014501400 02001250175020007509501400165013500 010501850190095011501350160011502000 85070095055035020050012501050850 1250130011009007501000550800600400250105013009007005508003501000800600501250300110090075010005501000800600250

8006002505050

10508505005003000

20002507505507501000

4002002507005007009500

80060025025050250500450250

15001300120012001000120012501100900750950550800600400250

00

50

55035055080002006008008005509501150750130011001300

25050

200020025025025025045045080012001400650120010001200

750550200

0200450750700250450450130017001800650120010001200

55035000

02505505005025025011001500160045010008001000

10501000950115013509508508007509501150750500450100012001400650500450150017001800650300250130015001600450

04501500170018006500 2507501750195018509008001050 70065055075095055075010000 5004507509501150350300550450250 50012001400135020002506504500 2001400160015504005008506504500250 140013501150013501600350550100012501200 01050175020007509501400165013500 010501850190095011501350160011502000 85070095055035020050012501050850 1250130011009007501000550800600400250105013009007005508003501000800600501250300110090075010005501000800600250

8006002505050

10508505005003000

20002507505507501000

4002002507005007009500

80060025025050250500450250

15001300120012001000120012501100900750950550600600400250

00

130011001000080010001250900700550750350800800600500

19个村庄铺设天然气管道

0 25050 750550200 5503500075055020020010008002504502000250750400200250700

W5

80060025025010008004504501000800450450115095012001700115095012001600950750650650150013001200120013001100100010001500130012001200

3) 继续分枝定界。由于L.B.(W3)=L.B.(W5),所以可以以W5分枝，分枝边确定为v13v14。若回路中不包含v13v14，则置w13 14=∞，由W3并化简后得W7，且L.B.(W7)= 5850+600+400=6850；若回路中包含v13v14，则在W3中删除v13v14所在的行和列元素，并置w14 13=∞，得W9，且L.B.(W9)= 5850+550+200=6600，小于W7所在分枝的下界。

02507505507501000200400

W7

800100010004501150950150013001500

1050100095095095015001300

8508007507507501300110050 5004501000100065012001000550200 500450150014006501200035000 3002501300120045010008005502002000 045015001400650120010008002504502500 250750175014509001250125002507505508001050 700650550550550110090020025070050075010000 50045075075035090070060025025050300550450250 500120095020075055080045045025002506504500 200140011504009507508004504502505008506504500250 140075005503503506001100900115014001503508001050750 450020095012001600140016501700750950115014009500 6502004007506506504507009505503502005001250450 25050130012001200100012501300110090075010005508000250 0110010001000800105013009007005508003501000200500

13001200120010001250300110090075010005501000200250000

250

50

750550200

55035000

8006002505050

10508505005003000

20002507505507501000

4002002507005007009500

80060025025050250500450250

250

50

750550200

55035000

0250550500502502501500140045010008001000

1050100095013509508508007501150750500450100014006505004501500180065030025013001600450

0450150018006500 250750175018509008001050 70065055095055075010000 5004507501150350300550450250 5001200135020002506504500 200140015504005008506504500250 14001150017502000750950140016501350 0105016501700750950115014009500 6507009505503502005001250850 1250130011009007501000550800400250105013009007005508003501000600501250300110090075010005501000600250

8006002505050

10508505005003000

20002507505507501000

4002002507005007009500

80060025025050250500450250

15001300120012001000120012501100900750950550600200250

00

130011001000080010001250900700550750350800400500

2507505507501000200

W9 400

80010001000950950150013001500

4） 由于L.B.(W9)<L.B.(W7),所以以W9分枝求得下一个分枝矩阵，依此类推，求得矩阵W83，W85，其中W83下界变为7650+50+450=8150，W85下界不变为7650，所以L.B.(W83)>L.B.(W85)，以W85进行分枝，分枝边为v2v2，若回路中不包含v2v2，则置w2 2=∞，由W85并优化得W87，且L.B.(W87)= 7650+500=8150；若回路中不包含v2v2，则在W85

80010501000400950

60085080020075050 250500450450650550200 25050045095065035000 503002507504505502002000 25004509506508002504502500 500250750120090002507505508001050 450700650055020025070050075010000 25050045020035060025025050300550450250 50065020080045045025002506504500 2008504008004504502505008506504500250 8500750100014001200145015005507509501200750 450750650650450700950550350200500700 1300120012001000125013001100900750100055025025011001000100080010501300900700550800350450501300120012001000125030011009007501000550450250

25050

750550200

55035000

8006002505050

10508505005003000

20002507505507501000

4002002507005007009500

150013001200120010001200125011009007509505500250

00

130011001000080010001250900700550750350200500

19个村庄铺设天然气管道

中删去v2v2所在的行列的元素，得W89，且L.B.(89)=7650

W83

0

W87 250

250

5）显然，W89中的零元素构成回路，所以可得一条

H回路其权为L.B.（W89）=7600。

其中H回路为 {v1v2 ,v2v9,v9v8 ,v8v13,v13v14,v14v15,v15v17,v17v19,v19v18,v18v16,v16v12,v12v10,v10v11,v11v6,v6v7 ,v7v4,v4v5,v5v3,v3v1} 。最短回路图如下：箭头表示的方向为行走的方向，双箭头表示需要来回走的道路

0

02500

0250 50

0

W85 2500

250 50

0W89

25

则上图为所求的最短路径，路程为7400km

参考文献：

[1].蔡锁章 数学建模原理与方法 海军出版社 2000

[2].湖北省大学生数学建模竞赛专家组 数学建模（本科册） 华中科技大学出版社 2006

[3].薛秀谦 朱开永 运筹学 中国矿业大学出版社 2002 [4].卜月华 图论及其应用 东南大学出版社 2002 [5].孙惠泉 图论及其应用 科学出版社 2004

本文来源：https://www.bwwdw.com/article/1u81.html