最佳灾情巡视路线模型

最佳灾情巡视路线模型

【摘要】 “图论”是组合数学的分支，它与其他的数学分支，如群论、矩阵论、拓扑学，数值分析有着密切的联系。在其它科学领域，如计算机科学、运筹学、电网络分析、化学物理以及社会科学等方面图论也具有越来越重要的地位，并已取得丰硕的成果。而且，图论的理论和方法在数学建模中也有重要应用。本文概述了一些常用的图论方法和算法，并通过举例（灾情巡视路线）说明其在数学建模中的应用。

【关键词】图论 灾情巡视 Hamilton 回路 数学模型

预备知识

定义1 完全图：如果图G 中每一对不同的顶点恰有一条边连接，则称此图为完全图。 定义2 连通图：如果对图G=（V ，E ）的任何两个顶点u 与v ，G 中存在一条（u-v ）路。则称G 是连通图。

定义3 加权图：边上有数的图称为加权图。在加权图中，链（迹、路）的长度为链（迹、路）上的所有边的权植的和。

定义4 Hamilton回路：图G 中的一个回路C 称为一个Hamilton 回路如果C 含有G 的所有顶点。含有Hamilton 回路的图称为Hamilton 图。

定义5 欧拉回路：经过图G 的每条边的迹称为欧拉迹，如果这条迹是闭的，则称这条闭迹为G 的欧拉回路。

一 数学建模中常用的图论方法

1 迪克斯特拉算法（Dijkstra ）

1.1问题来源

在加权图中，我们经常需要找出两个指定点之间的最短路，通常称为最短路问题。解决最短路问题的方法之一就是迪克斯特拉算法。

1.2基本思路

假定P ：V 1→V 2→„V i →„→V j →„→V k 是从V 1到V k 的最短路，则它的子路V i →„→V j 一定是从V i 到V j 的最短路。否则从V 1出发沿路p 走到V i ，, 然后沿V i 到V j 的最短路走到V j 再沿路P 从V j 到V k ，这样得到一条新的从V 1出发到V k 的路，其长度小于P ，与P 是最短路的假设矛盾。

1.3算法

设G 为所有权都为正数的加权连通简单图。G 带有顶点a=V0, V1 , „V n =z,权W(Vi , Vj ) ,若(Vi , Vj ) 不是G 中的边，则W(Vi , Vj ) =∞

for i=1 to n

L((Vi )= ∞

L(a)=0

S=Ф(初始化标记，a 的标记为0，其它结点标记为∞，S 为空集)

当z 不属于S 时

begin

u=不属于S 的L （u ）最小的一个顶点

S=S∪{u}

对所有不属于S 的顶点V

if L(u)+W(u,v)

L(v)=L(u)+L(u,v) (这样就给S 中添加带最小标记的顶点并且更新不在S 中的顶点

的标记)

End (L(z)表示从a 到z 的最短路的长度)

这个算法经过n-1次循环后必定结束，计算量为1/2（n-1）(n-2)，因而是个有效算法。

2最邻近算法

2.1问题来源

最邻近算法起源于旅行推销员问题，该问题实际上是求加权完全无向图中的访问每个顶点恰好一次且返回出发点的总权数最小的闭路，又称为最优Hamilton 回路。如果我们将加权图中的结点看作城市，加权看作距离，旅行推销员问题就成为找出一条最短路线，使得旅行推销员从某个城市出发，沿着这条路线遍历每个城市一次最后再回到出发的城市。

2.2 算法

设G=（V ，E ）是一个赋权完全图，根据实际问题作如下规定：

对V （G ）中的任何三个顶点U ，V 和X ，满足W （UV ）+W（VX ）≥W （UX ）

（1） 任选一个顶点V 0作起点，找一条与V 0关联其权最小的一条边e 1, e1的另一个端点记为V 1，得一条路V 0 V 1；

（2） 设已选出路V 0 V 1„V i , 在V （G ）-{ V0，V 1„V i }中取一个与V i 最近的相邻顶点V i +1, 得V 0 V 1„V i V i +1；

（3） 若i+1

2.3改进方法

设C= V1 V 2„V p V 1是G 的一个Hamilton 回路。若存在i,j 适合1

W （V i V j ）+W(Vi +1V j +1)

则Hamilton 回路为

C ij = V1V 2„V i V j V j -1„V i +1V j +1„V p V 1

（它是由C 删去边V i V i +1和V j V j +1添加边V i V j 和V i +1 V j +1而得到的）其权和

W （C ij ）=W(C)-W(Vi V i +1)-W(Vj V j +1)+W(Vi V j )+W(Vi +1V j +1)

因而Hamilton 回路C ij 将是一个改进。

3弗来里算法（Fleury ）

3.1问题来源

邮递员从邮局出发，沿着邮路的每条街道分送信件，最后回到邮局。在这一过程中，邮递员希望以尽可能少的行程完成投递任务。这类问题首先由我国的管梅谷先生于1962年提出，故国际上称为中国邮递员问题。用图论语言来描述：一个连通加权图G （V ，E ，W ），每一条边代表邮路中的每一条街道，每个顶点表示两条街道间的交叉点，每边的权表示街长。要找一条从邮局出发的回路，使之包含G 的每一边至少一次，且该回路的权达到最小。

3.2算法

（1） 任意取一个顶点V 0，令W 0=V0；

（2） 假定迹W i = V0 e 1 V 1„e i V i 已经选出，那么用下列方法从E （G ）

-{ e1,e 2 , „, ei }中选取e i +1:

① e i +1与V i 相连；

② 除非没有别的边可选择，e i +1不是G i ={ e1, e2, „, ei }的割边；

（3）当（2）不能执行时，停止。否则让i+1→ i., 转（2）。

二 图论方法的应用举例

灾情巡视路线模型

1 问题重述

已知某县的乡村公路网示意图。今年夏天该县遭受水灾，为考察灾情，组织自救，县领导决定带领有关部门负责人到全县各乡村巡视。现要求建立数学模型解决以下问题：

（1）若分三路巡视，试设计各路的巡视路线，使其总路线最短且尽可能均衡；

（2）假定巡视人员在各乡停留时间为T=2小时，在各村停留时间为t=1小时，汽车行使速度V=35千米/小时。要在24小时内完成巡视，至少应分几组？给出分组下你认为最佳的巡视路线。

2 模型假设

（1）所有乡、村和县政府所在地均为图中节点；

（2）各乡、村最多被经过两次，并且只被一组巡视人员巡视一次；

（3）交通工具只有汽车，巡视人员不采用步行或其他方式；

（4）汽车行使速度不受天气，路况等客观因素影响，速度恒定；

（5）巡视人员除在乡、村停留外，不做其他休息。

3 模型的建立和求解

3.1先求一路巡视时最短的巡视路线

3.1.1理论模型

这是一个典型的旅行推销员问题, 即推销员从驻地出发经所要去的城市至少一次返回原地，应如何安排旅行路线，使总的旅行距离最短。由于原图是加权连通图，图G 的顶点Vi 表示本县的各个乡（A ，B ，„，R ）和村（1，2，„，35）。每两个顶点V i , Vj 间都生成一条边（V i , Vj ）, 边的权植为这两个顶点间的最短路径长度D ij 。若原图两顶点之间并无直接边相连，则取这两点间按Dijkstra 算法生成的最短路径。巡视人员在原图中巡视的顶点顺序按这条Hamilton 回路，即为最短的巡视路线。由于图G 是一完全图，图中必然存在（N-1）/2条Hamilton 回路（N 为图G 的顶点数），其中最短的那条就是路程最短的巡视路线。

3.1.2 最邻近算法

① 任选一个顶点V 0作起点，找一条与V 0关联其权最小的一条边e 1, e1的另一个端点记为V 1得一条路C= V0 V 1；

② 设已选出路V 0 V 1 „V i , 在V （G ）-{ V0，V 1，„V i }中取一个与V i 最近的相邻顶点V i +1得V 0 V 1„V i V i +1；

③若i+1

运用本算法及其改进，即可得最短的Hamilton 回路为：

C={O.1,B,C,3,2,5,M,6,7,D,4,8,E,9,F,10,12,H,14,13,G,11,J,19,20,25,21,K,18,I,15,16,17,22,23,24,N,26,27,28,Q,30,32,35,34,A,33,31,R,29,P,O},其总长度S=508.6千米。 （计算过程及图见附录）

3.2求分三路巡视时总路程最短的巡视路线

对于分三路巡视，我们可以将其等价地看成一路巡视人员在巡视过程中三次从县政府出发和返回。于是我们将县政府顶点O 连同其相连的边一起复制两次，得到两个虚拟的顶点O 1、O 2。将O 1、O 2加入到图G 中，形成新图G 1，再运用上述求最短Hamilton 回路的算法在G 1中找到最短Hamilton 回路。于是这三条Hamilton 回路分别为C 1=C，C 2={ O1,1, O1},C3={ O2,2, O2}(其中1，2为与顶点O 相连的边) 。总路线为540.8千米。显然这样得到的C 1、C 2、C 3虽然满足总路程最短, 却极不均衡，下面给出改进方案。

3.3求分三路巡视且保证三路尽可能均衡的条件下总路程最短的巡视路线

3.3.1 划分子图

要使三路尽可能均衡, 应使每条巡视路线经过的顶点数目基本相同。由于地图中的乡村分布密度较均匀, 因此可以将地图去掉某些边后分为面积基本相同的三个子图G 1、G 2、G 3, 且这三个子图都应包含县政府O 。由于要满足总路程最短, 因此三个子图应尽量不互相覆盖。这样的G 1、 G 2、 G 3应成花瓣形。

3.3.2 分别求解

对G 1、 G 2、 G 3分别用3.1中算法求得最短巡视路线D 1、D 2、D 3, 其长度分别为S(D1) 、S(D2) 、S(D3) 。

3.3.3 调整

比较S(D1),S(D2),S(D3). 的大小, 将长度较大的子图中某些顶点适当调整至长度较小的子图中，若路径基本相同则结束。 这样就可以得到满足一定均衡性的三条Hamilton 回路, 其总巡视路程S=S(D1)+S(D2)+S(D3) 。由于D 1、 D 2、 D 3分别是子图G 1、 G 2、 G 3中的最优解, 故D 1、D 2、D 3是这种子图划分下的最优解。 D 1={ O，2，5，6，7，E ，11，G ，13，14，H ，12，F ，10，F ，9，8，4，D ，3，

2，O}(其中F 被经过两次, 但只巡视一次);

D 2={O，P ，26，N ，24，23，21，K ，22，17，16，I ，15，I ，18，J ，19，L ，20，

25，M ，O }(其中I 被经过两次, 但只巡视一次);

D 3={O，1，C ，B ，34，35，32，31，33，A ，R ，29，Q ，30，Q ，28，27，26，P ，

O }(其中Q 被经过两次, 但只巡视一次,26和P 只是被经过, 但不被巡视);

S(D1)=210.5千米 S(D2)=194.9千米 S(D3)=175.6千米

S= S(D1)+ S(D2)+ S(D3)=581.0千米（图见附录）

3.4假定巡视人员在各乡停留时间为T=2小时，在各村停留时间为t=1小时，汽车行使速度V=35千米/小时。要在24小时内完成巡视，至少应分几组？给出分组下你认为最佳的巡视路线

3.4.1 人员在各乡, 村的停留时间T,t 转化成完全图G 中边的权值的增长：

v i 为乡⎧2⎪t i =⎨1 v i 为村

⎪0v i 为县政府⎩

由图可知有17个乡,35个村, 因此停留时间为17⨯2+3⨯51=69小时, 将其转化为边的权值的增长Δd, 则

Δd=356⨯9=2415千米

于是巡视总路线为S=2415+540.8=2955.8千米

T=S/V=2955.8/35=84.5小时

要在24小时内完成巡视, 则至少需要 [84.5/24] =4组

3.4.2 分四组的情况下24小时内完成巡视的最佳巡视路线

①将G 划分为4个子图；的权值的增长Δd, 则

②按前面的算法逐步求解得下面一组解：（图见附录）

L 1={O，C ，3，D ，4，8，E ，9，F ，10，F ，9，E ，7，6，5，2，O }

(其中E ，9，F 经过两次，但只巡视一次)

S 1=158.8千米 T 1=21.54小时

L 2={O，2，5，6，7，E ，11，G ，12，H ，14，13，J ，19，L ，20，25，M ，O}（其中2，5，6，7，E 只被经过，不作巡视）

S 2=168.1千米 T 2=21.80小时

L 3={O，M ，25，21，K ，18，I ，15，，I ，16，17，22，23，24，N ，26，P ，O }（其

中I 被经过两次，但只巡视一次；M 、25只被经过，不作巡视）

S 3=167.2千米 T 3=20.78小时

L 4={O，1，B ，34，35，32，31，33，A ，R ，29，Q ，30，Q ，28，27，26，P ，O }

（其中Q 被经过两次，但只巡视一次；26、P 只被经过，不作巡视）

S 4=152.0千米 T 4=22.34小时

4 模型评价

本模型将求图中最短巡视路线问题转化为求一个最短Hamilton 回路的问题，这种方法有坚实的理论基础。在求多路巡视路线的最优解时, 使用了划分子图的方法, 在各子图实现最优, 总体上也保证了均衡, 方法简便, 易于操作。但本模型中所使用的求最短Hamilton 回路的算法本身是个近似算法, 因此结果只能是近似最优解。在经过多次尝试之后，结果中还是有多个顶点被重复经过。与前人的研究结果（见参考文献）对比如下：

（1）一路巡视本文所得总长度506.6千米比参考文献中的520.7千米稍短；

（2）三路巡视均衡性较好，但总长度有所增加。见下表（单位：千米）

（3）四路巡视（单位：小时）

【参考文献】：

【1】殷剑宏, 吴开亚. 图论及其算法, 中国科学技术大学出版社.

【2】卜月华. 图论及其应用, 东南大学出版社.

【3】王树禾. 图论, 科学出版社.

【4】袁震东, 洪渊林等. 数学建模, 华东师范大学出版社.

【5】薛毅. 数学建模基础, 北京工业大学出版社.

【6】赫孝良, 戴永红等. 数学建模竞赛赛题简析与论文点评, 西安交通大学出版社.

An Application Of Graph Theory In Mathematical Modeling

Kang xiaoxue

【Abstract 】 Graph theory is a branch of combination mathematics, which contact with other branches inseparably, such as group theory, matrix theory, topology and numerical analysis. In other science fields, like computer science, electronic network analysis, physical chemistry and society science etc, graph theory is used more and more frequently and got many harvests. Furthermore, graph theory and its approaches also have important applications in mathematical modeling. In this paper, we introduce some methods and algorithms of graph theory., and give an example to illustrate an application of the methods or algorithms.

【Key words】 Graph theory the tour of a disaster the shortest Hamilton loop mathematical model

附录：

1求一路巡视的运算过程

（1）取O 点为起点，比较与点O 相连的边（O ，1）、（O ，C ）、（O ，2）、（O ，M ）、（O ，

P ）、（O ，R ）的权值，显然（O ，1）最短，于是取C={O，1}；

（2）将1作为新起点，比较与1相连的边（1，A ）、（1，B ）、（1，C ）的权值，显然

（1，B ）最短，于是C={O，1，B}；

（3）依次类推可得C={O，1，B ，C ，3，2，5，6，7，E ，9，F ，10，12，G ，11，J ，

19，L ，20，25，21，K ，18，I ，15，I ，16，17，22，23，24，N ，26，27，28，Q ，29，R ，A ，1，O}

（4）但这样得到的路并没有包含所有顶点，遗漏了M ，D ，4，H ，14，13，8，30，

32，35，34，33，31，P ，因此还需要进行调整。

调整时可采用前文中提到的最邻近算法的改进方法。针对这个问题的实际况，笔者经过多次尝试，采用的是“推而求其次”的方法，即在没有经过的顶点附近，舍弃最短的边而取能够经过该点但权值稍大的边. 具体做法如下：

（5）在与M 点相连的点5处舍弃边（5，6）而取次短的（5，M ），再按照最邻近算

法，路径就变为{„5，M ，6，7„}；

（6）在7处舍弃边（7，E ）而取（7，D ），同样路径变为{„7，D ，4，8，E ，9，F ，10，

12„}；

（7）在12处舍弃（12，G ）而取（12，H ），路径变为{„12，H ，14，13，G ，11，J ，

19，L ，20，25，21，K ，18，I ，15，I ，16，17，22，23，24，N ，26，27，28，Q ，29，R ，A ，1，O}；

（8）在Q 处舍弃(Q,29)而取(Q,30),路径变为{„Q,30,32,31,33,A,1,O};

（9）在32处舍弃(32,31)而取(32,35),路径变为{„32,35,34,A,33,31,R,29,P,O};

（10）将所有调整后的路径连在一起, 便得到文中的最短Hamilton 回路。 2 三路巡视和四路巡视的方法同上，具体过程略。