图论与网络
图论与网络方法建模
目 录
一、引言 . .......................................................................................................................................... 1
二、基本概念和性质 .............................................................................................................. 2
三、算法介绍 ............................................................................................................................... 3 3.1 最短轨道问题 . ...................................................................................................................... 3 3.2 求最小生成树 . ...................................................................................................................... 4 3.3 Steiner生成树 . ....................................................................................................................... 5 3.4 Euler回路 ............................................................................................................................... 7 3.5 网络中的最大流 .................................................................................................................. 8 3.6 工序问题 .............................................................................................................................. 10
四、网络规划的应用 ............................................................................................................ 10 参考文献 . ........................................................................................................................................ 13
一、引言
我们知道,数学建模竞赛中有问题A 和问题B 。一般而言,问题A 是连续系统中的问题,问题B 是离散系统中的问题。由于我们在大学数学教育内容中,连续系统方面的知识的比例较大,而离散数学比例较小。因此很多人有这样的感觉,A 题入手快,而B 题不好下手。
另外,在有限元素的离散系统中,相应的数学模型又可以划分为两类,一类是存在有效算法的所谓P 类问题,即多项式时间内可以解决的问题。但是这类问题在MCM 中非常少见,事实上,由于竞赛是开卷的,参考相关文献,使用现成的算法解决一个P 类问题,不能显示参赛者的建模及解决实际问题能力之大小;还有一类所谓的NP 问题,这种问题每一个都尚未建立有效的算法,也许真的就不可能有有效算法来解决。命题往往以这种NPC 问题为数学背景,找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说,由于问题是具体的实例,我们可以找到特殊的解法,或者可以给出一个近似解。
图论作为离散数学的一个重要分支,在工程技术、自然科学和经济管理中的许多
方面都能提供有力的数学模型来解决实际问题,所以吸引了很多研究人员去研究图论中的方法和算法。应该说,我们对图论中的经典例子或多或少还是有一些了解的,比如,哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且,从历年的数学建模竞赛看,出现图论模型的频率极大,比如:
AMCM90B -扫雪问题;
AMCM91B -寻找最优Steiner 树; AMCM92B -紧急修复系统的研制(最小生成树) AMCM94B -计算机传输数据的最小时间(边染色问题) CMCM93B -足球队排名(特征向量法) CMCM94B -锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B -灾情巡视路线(最优回路)
等等。这里面都直接或是间接用到图论方面的知识。要说明的是,这里图论只是解决问题的一种方法,而不是唯一的方法。
本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型,着重介绍图论中的典型算法。这里只是一些基础、简单的介绍,目的在于了解这方面的知识和应用,拓宽大家的思路,希望起到抛砖引玉的作用,要掌握更多还需要我们进一步的学习和实践。
二、基本概念和性质
这门课程的特点是不像其它数学课程有大量复杂的公式和繁琐的计算,它描述性的东西比较多。首先给出图论中的一些基本概念。
1.一个图G 由一个顶点集V 和一个边的集E 组成。E 中每个元素e 是连接顶点集 V 中两个顶点u 和v 的边,称e 与u ,v 关联。我们规定连接两个顶点u 、v 至多有一条边,且一条边的两个顶点不重合,这种图称为简单图。
2.顶点集为V ,边集为E 的图G 通常记为G=(V ,E )。图G 1=(V 1,E 1)称为G 的子图,如果 V 1V , E 1E 。
3.顶点v 的度(或“次”) 是指与v 相关联的边的个数。图G 的度数之和为边数的两倍。
4.若图G 中任意两个顶点u 、v 之间都存在连接它们的路,称G 为连通图。
5.W=v0e1v1e2……ekvk ,其中ei ∈E ,vj ∈V ,ei 与vi-1,vi 关联,称W 是图G 的一条道路。v0是起点,vk 是终点;各边相异的道路叫做行迹,各顶点相异的道路叫做轨道;起点和终点重合的道路为回路;起点和终点重合的轨道为圈;包含图中每条边的回路称为Euler 回路;含Euler 回路的图称为Euler 图。
6.一个无圈的连通图称为树。树是最简单而最重要的一类图。树有下列重要性质: 性质:
1) 在树中去掉任意一条边,所得的图是不连通的。
2) 在树中任意两个不相邻的顶点u 、v 之间添加一条新的边,所得的图恰有一个圈。 下述定理是树的判断定理:
定理:若图G 具有下列性质中的两条,则它是树,且也具有第三条性质。
(1).G 是连通图;
(2).G 没有圈;
(3).G 的顶点数=G的边数+1。
7.如果图G=(V ,E )的子图G t =(V t ,E t )是一个树,且V t =V,称G t 是G 的生成树。G 连通的充要条件是G 有生成树。生成树一般而言数量很大。
8.设对图G=(V ,E )的每一条边e 赋予一个实数W (e ),称为e 的权,G 称为赋权图(加权图) 。若G 是连通的赋权图,要找G 的连通子图 G *=(V ,E*),使得W (G*)=∑W (e ) 为最小。显然G*应为G 的一个生成树。G 的权最小的生成树称为 G
e ∈E
的最小生成树。
三、算法介绍
3.1 最短轨道问题
背景:给定连接若干城市的铁路网,寻求从指定城市到各城去的最短道路。 数学模型:图G 为一赋权图,对任给的v ∈V(G),寻求轨道P(v0,v),使得
W(P(v0,v))=min{W(P),P取自所有v0到v 的轨道集合}
其中W(P)是轨道P 上各边权之和。
这一问题可用迪克斯特拉(Dijkstra)算法解决。
基本思想:从起点v0开始,逐步寻找到达各点的最短路,在每一步都对顶点记录一个
数,称之为该点的标号,它表示v0到该点的最短距离的上界,或就是v0到该点的最短距离。实际上每一步都通过把至少一个具有T 标号的点变成P 标号(即把一个不是最短距离标号的顶点变成是最短距离标号的顶点) ,这样最多经过|V(G)|-1步就可完成。 步骤:记l(v)为v0到v 的距离。
(1) l(v0)=0,l(v) = ∞,(v≠v0) ;S0={v0},i=0。
(2) 对v ∉Si ,min{l(v),l(vi)+w(viv)}代替l(v);这样找到点vi +1使得l(v)取最小值,vi +1∈(Si的余集) 。令Si +1=Si +{vi+1}。
(3) i=|V(G)|-1时停止,否则,i+1,转到(2)。
实例:CMCM94A -公路选址问题中可以利用该思想。
3.2 求最小生成树
1.克罗斯克尔(Kruskal)算法(1956年) ,俗称“避圈法”
背景:筑路选线问题 欲修筑连接n 个城市的铁路,已知i 城与j 城之间的铁路造价为Cij 。设计一个线路图,使总造价最低。
分析:选线问题的数学模型是在连通加权图上求权最小的连通生成子图。显然,权最小的连通生成子图是一个生成树,即求取连通加权图上的权最小的生成树,这就归结为最小生成树问题。这个问题可由克罗斯克尔(Kruskal)算法解决。
思路:从“边”着手选最小生成树。
步骤:设G 为由m 个节点组成的连通赋权图。
(1) 先把G 中所有的边按权值大小由小到大重新排列,并取权最小的一条边为树T 中的边。即选e1∈E ,使得w(e1)=min 。
(2) 从剩下的边中按(1)中的排列取下一条边。若该边与前面已取进T 中的边构成一个回路,则舍弃该边,否则也把它取进T 中。若e1,e2,„,ei 已经选好,则从E -{e1,e2,„,ei}中选取ei +1,使得G[{e1,e2,„,ei ,ei+1}]中无圈,且w(ei+1)=min。
(3) 重复步骤(2),直到T 中有m -1条边为止。则T 为G 的最小生成树。
2.普莱姆(Prim)算法
思路:从点入手来选边
步骤:(1) 在图G 中任取一个节点vi1,并放入T 中。 该算法的复杂度为O(e log e ) ,其中e 是图G 中的边数。
(2) 令S =V(G)/V(T),V(G)、V(T)分别是G 、T 的节点集。
(3) 在所有连接V(T)节点与S 节点的边中,选出权值最小的边(u0,v0),即
w(u0,v0)=min{w(u,v)|u∈V(T), v∈S}。
(4) 将边(u0,v0)放入T 中。
(5) 重复步骤(2)-(4),直到G 中节点全部取完。
3.1975年管梅谷提出的“破圈法”
(略)
3.3 Steiner生成树
实际背景:在已有网络上选择连通几个城市的最廉价交通或通讯网。
数学模型:从已知的加权连通图上求取最小的树状子图,使此树包含指定的顶点子集。
第一个的边长为3,第二个的边长为1,总费用第二个更少。 该算法的复杂度为O(n^2),其中n 为图G 的节点数。
分析:与传统的最小生成树相比,这里可以引入若干“虚拟站”并构造一个新的Steiner 树,这样可以降低由一组站生成的传统的最小生成树所需的费用(降低的费用大概为13.4%)。而且为构造一个有n 个顶点的网络的费用,最低的Steiner 树决不需要多于(n-2) 个虚设站。当然,有时最小Steiner 生成树与最小生成树相同。寻求最小Steiner 生成树的算法有Melzak 算法(1961年) ,但是这是一个指数时间的算法,现在没有多项式时间的算法,换句话说它是一个NP 问题。而且,这里的要求是用直折线代替欧氏直线距离,因而不能利用直接的算法。所以在解决这样的问题的时候,为减少运算的时间,理论上的分析是必要的:比如树的长度的下界,Steiner 树的存在性,虚设站的位置等等。常用的算法还包括穷举法、模拟退火法等。
Melzak 算法:其基础是3点steiner 树,即3点Fermat 问题的几何作图法。参考[2],Page375。
模拟退火法原理:模拟退火法(Simulated annealing, SA)
是模拟热力学中经典粒子系统
的降温过程,来求解规划问题的极值。当孤立粒子系统的温度以足够慢的速度下降时,系统近似处于热力学平衡状态,最后系统将达到本身的最低能量状态,即基态,这相当于能量函数的全局极小点。其步骤如下(也称为Metropolis 过程) :
(1) 给定初始温度T 0,及初始点,计算该点的函数值f(x)。
(2) 随机产生扰动Δx,得到新点x′=x+Δx,计算新点函数值f(x′),及函数值差Δf=f(x′)-f(x)。
(3) 若Δf≤0,则接受新点,作为下一次模拟的初始点;
(4) 若Δf>0,则计算新点接受概率:,产生 [0,1]区间上均匀分布的伪随机数r,r ∈[0,1],如果p(Δf)≥r,则接受新点作为下一次模拟的初始点;否则放弃新点,仍取原来的点作为下一次模拟的初始点。
实例:
1.MCM91B(通讯网络中的极小生成树) 是一个求STEINER 生成树问题,参见《工科数学专辑》Page :70-78。
2、CMCM 97A题
97年全国大学生数模竞赛A 题“零件的参数设计”,可以归结为非线性规划模型,由于目标函数很复杂,且又是一个多维函数,因此求解比较困难,为应用模拟退火法进行求解,将7个自变量的取值范围进行离散化,取步长为0.0001,这样,所有7个变量取值就组成了一个极为庞大的离散空间, 而这个问题变成组合优化模型。
这个问题算法的状态调整规则是:每次从7个自变量中随机选取1-4个,让选取的自变量随机移动,考虑选取的自变量在两个方向移动组合,从中选取最佳的作为候选者,自变量移动的距离随着温度的降低而减少,为避免陷入局部极小,可以从多个随机选取的初始值开始计算,算法的其它步骤同上。
3、CMCM 98B题
98年全国大学生数学建模竞赛B 题“水灾巡视问题”,是一个推销员问题,本题有53个点,所有可能性大约为exp(53),目前没有好方法求出精确解,既然求不出精确解,我们使用模拟退火法求出一个较优解,将所有结点编号为1到53,1到53的排列就是系统的结构,结构的变化规则是:从1到53的排列中随机选取一个子排列,将其反转
或将其移至另一处,能量E 自然是路径总长度。具体算法描述如下:
步1: 设定初始温度T ,给定一个初始的巡视路线。
步2:步3 --8循环K 次
步3:步 4--7循环M 次
步4:随机选择路线的一段
步5:随机确定将选定的路线反转或移动,即两种调整方式:反转、移动。 步6:计算代价D ,即调整前后的总路程的长度之差
步7:按照如下规则确定是否做调整:
如果D
如果D>0,则按照EXP(-D/T)的概率进行调整
步8:T*0.9-->T,降温
3.4 Euler回路
设G 是一个图,若存在这样一条回路,使它经过图中的每条边且只经过一次又回到起始节点,就称这样的回路为Euler 回路。
背景:哥尼斯堡七桥问题
定理:对连通图G ,下列条件是相互等价的:
(1) G是Euler 图;
(2) G的每个节点的度数都是偶数;
(3) G的边集可以分解为若干个回路的并。
对有向图,出度=入度。
算法:弗罗莱(Fleury)算法(1921)
(1) 任给v0 V(G),R ={v0}
(2) 设路R =v0e1v1e2v2……eivi 已选定,则从E(G)\{e1,e2,……ei}中选边ei+1,且满足:
ei+1与vi 相连;除非已无选择,ei+1不要选E(Gi)=E(G)-{ e1,e2,……ei }中的桥(注:桥,去掉之后图不连通)
(3) 重复(2),直到不能再选为止
实例:MCM90B 铲雪问题中单车道单车扫雪-地图是Euler 图的情形。
说明:如果图G 不是Euler 图,也就是说不存在Euler 回路,这时候求解就比较困难。求解前需要做一些处理,添加一个边子集E1,E1+G =G1构成一个Euler 图,然后再寻找Euler 回路。注意图G 不是Euler 图时,必有偶数个奇数度的节点,可以给这些节点两两配对,求两点间的最短路,将这些最短路画在一起构成附加边子集E1。这里的困难在于:奇数度的节点较多时,配对方案也多。
3.5 网络中的最大流
背景:把商品从生产地运往市场,交通网上每个路段能力给定的条件下,设计一个运输方案,使得运输最快。
网络:规定起点s 、中间点和终点t 的赋权图。
数学模型:有向图G ,每边加权c(e),称c(e)为边e 之容量,设G 为严格的有向图,则称这个有向的加权图为一个网络。映射f :E(G)→R 满足
(c1) 任给e ∈E(G),0≤f(e)≤c(e);
(c2) 任给v ∈V(G)-{s,t},∑f (e ) -∑f (e ) =0;其中a(v)是以v 为头的边集(流
e ∈α(v ) e ∈β(v )
进) ,b(v)是以v 为尾的边集(流出) ,即除起点和终点外,各节点流入量总和等于流出量总和。称f(e)为流函数,称
F =
为流量。
我们的目标是寻找一个流函数f ,使其流量最大。1956年,福特(Ford)和福尔克逊∑e ∈α(t ) f (e ) -∑e ∈β(t ) f (e ) (Fulkerson)提出了求最大流的算法。
最大流最小割定理:流过网络的最大流量等于最小割集的容量。
2F 算法:
(1) 对每边e ,选f(e)=0;
(2) 标志顶s ,其它顶未标志;
(3) 选可“向前标志”或可“向后标志”的顶v 。若无此种顶可选时,停止,现流函数即为最大流;若有此种顶可选时,则得到新的标志顶v 及标志边e 。若v =t ,则转(4);否则转(3)。
(4) 设已得标志之轨为(此轨为无向的) s e1v1e2v2……et t ,从t 开始沿此轨逆行,令
∇=min ∇(e i ) , 1≤i ≤l
若ei 是前进边,即在有向图中ei =vi -1vi(s=v0,t =v l ) ,则f(ei)=f(ei)+∇; 若ei 是后退边,即在有向图中ei =vivi -1,则f(ei)=f(ei)-∇;
(5) 转(2)。
向前和向后标志的含义如下:若e =uv ,u 已有标志,v 没有标志,且c(e)>f(e),则称通过边e 可以向前标志顶点v ,且规定∇(e)=c(e)-f(e),得到标志边e 。若e =vu ,u 已有标志,v 没有标志,且f(e)>0,则称通过边e 可以向后标志顶v ,规定∇(e)=f(e),且得到标志边e 。∇(e)的含义是边e 上可以增载的上界。
说明:
1.如果每边之容量c(e)都是有理数,则2F 算法在有限步之内可以求得最大流。
2.容量有上下界的网络,需要构造附加网络。
最小费用—— 最大流问题
这是在上述讨论的基础上增加关于使费用最小的目标。解决的办法是采用“对偶法原理”:
1.先用上面讨论的方法求出网络的最大流量;
2.然后在原始的网络中福德算法找出从起点 vs 到终点 vt 的最短路线——最短
增广链;
3.在该增广链上找出最大调整量,并调整流量得到一个可行流,则此可行流的费用最小。如果此时流量等于最大流量,那么它就是最小费用最大流;否则应继续调整。
应用:运输问题,如CMCM2000B 钢管的采购和运输问题。
说明:
1.这里的介绍只是图论中的一部分,其余的需要我们进一步学习。
2.算法都是描述性的,有些可以找到现成的程序,但是最好是自己实现。
3.这里的例子只是解决问题的一种方法,不是唯一的方法。
4.注意实际应用中直接利用所给算法解决问题的情况很少,通常只是解决问题的一部分,而且需要建立模型,把实际问题用图论术语描述出来。所以要善于利用这里的工具。
其它方面的应用,如工序问题,最大独立集,最小覆盖集,邮递员问题,规划审核技术,关键轨道方法,可靠通信网络的构造问题等等。
3.6 工序问题
统筹方法是组织生产计划的方法,它用网络图表达生产和工程的进度,计算各项工序的有关时间参数。
一项工程总是由许多相互独立的工序组成的,各道工序之间有一定的先后次序。完成每道工序需要的时间(不妨设单位为小时)称为工序的长度。因此我们可以用一
个各条边有方向的图(称为有向图)表示各项工
序之间的互相依赖关系。以一条有向变来表示一
道工序,有向边的权即为此工序的长度,有向边
的起点和终点分别表示相应工序的开工和完工,
称为事项,前接工序和完工事项即为后续工序和
开工事项。
实例:上海MCM91B
四、网络规划的应用
1.最小生成树——网络规划例1
例1.求下图的一个最小生成树。
解:首先取 G 1=(V 1,E 1),V 1={v0},E 1=
其次,一端属于V 1,一端不属于V 1的最短边是v 0v 1,所以有
G 2=(V 2,E 2),V 2={v0,v 1},E 2={v0v 1}。
现在,一端属于V 2,一端不属于V 2的最短边是v 1v 3,所以有
G 3=(V 3,E 3),V 3={v0,v 1,v 3},E 3={vo v 1,v 1v 3}。
类似做下去,最后得最小生成树的边为:
v 0v 1,v 1v 3,v 2v 3,v 2v 5,v 5v 6,v 4v 6。
2.存储粮食模型——网络规划例2
例2.某乡有七个村A1,A2,... ,A7,需储存粮食数量分别为 50,75,62,40,100,80,35吨。各村之间有公路连通,如图。现要选择某村建立仓库储存所有粮食,问应选择何处最好?
解:图上连结两村的边所注的数字表示该段公路的千米数。我们的目的是选择仓库的位置使运粮的吨千米数最小。首先比较 A1和A2两处。在比较这两个村庄时,因为仓库无论建在 A1或A2,其他各村的粮食都要先运到 A2,所以我们可认为除 A1外各村的粮食都集中在 A2,共357吨。现在事情很明显,仓库建在 A2时需把50吨粮食运3千米到 A2,建在 A1时需把357吨粮食运 3千米到A1,所以 A2较 A1好。以后我们不再考虑A1,因此可把 A1的粮食移到 A2以简化问题。同理 A5也不必考虑,它的粮食可集中到 A4。
考虑其他五个村。我们猜想现在粮食数量大的村庄可能是个好主意。假定选择 A4,我们考虑A6是否会更好:A2、 A7的粮食少运4千米,而A3、 A4的粮食多运4千米,可见A4较 A6好。同理可证A4比其他各村都好。因此仓库应建在 A4。
3.工作顺序模型——网络规划例3
例3.某工厂的改造工程由下列7
道工序组成:A :拆迁;B :工程设
计;C :土建工程设计,前接工序为
B ;D :采购设备,前接工序为B ;
E :厂房土建,前接工序为A 、C ; F :
设备安装,前接工序为D 、E ;G :
设备调试,前接工序为F 。那么我们可用图 3.4表示这个工程,其中S 表示整个工程的开工, t 表示完工。有时,为了表示工序之间的顺序关系,需要引入虚工序。注意,用来表示工程进度的有向图是不允许有回路的。现在我们研究网络图的各种时间参数。 考虑图3.5
表示的网络,我们把各事项(即图的顶点)编号,一般要求每一工序的
开工事项(即箭尾)的编号少于完工事项的编
号(即箭头)。每条有向边旁所标数字为相应工
序的长度。
某一工序A 的最早开工时间t E (A),表示该
工序最早可在整个工程开工后t E (A)小时开工,
这时间仅与该工序的开工事项有关,所以也可
以说某一事项的最早时间 t E (k),例如图3.5中,事项4的最早时间是9(即工序1->4和 2->4都完成的时间)。
因而有下列递推公式
[ik]表示起点为i ,终点为k 的有向边。整个工程完工事项的最早时间,就是全工程完工的最短时间,称为总工期,记为 T E 。
某一工序的最迟完工时间(或该工序完工事项的最迟时间) t E (k),是在不误总工期的条件下,该工序最迟应在整个工程开工后 t L (A)小时完成。因此
实际上,t E (k)就是由事项1到事项k 的最长路的长度。t L (k)就是T E 减去k 到n 的最长路的长度。因而(2)的第二式也可写成
工序[ij]的总时差定义为
即不误总工期的条件下该工序的开工时间的机动时间,即可延迟开工的时间;而工序 [ij]的自由时差定义为
即在不误下道工序最早开工时间的前提下,该工序开工时间的机动时间。
从事项1到事项n 的一条最长路称为网络图的一条关键路,显然在关键路上的每一事项 k 满足t L (k)=t E (k),关键路上每一工序的总时差为 0,反之亦然。显然,若关键路上工序能提前完成,整个工程才有可能提前完成;若关键路上工序未能按时完成,整个工程必然不能按期完成。
求总工期和关键路的方法如下:首先对所有t E (i)置初始值零,然后利用公式(1)
进行迭代,直到所有的 t E (i)不再改变,而自由时差为0的工序就是关键路上的工序。例如图 3.5中网络图的总工期为28天,关键路为1->3->5->6->8。
参考文献
1. 叶其孝编,大学生数学建模竞赛辅导教材(2),湖南教育出版社,1997。
2. 李尚志等,数学建模竞赛教程,江苏教育出版社,1996。
3. 叶其孝编,数学建模教育与国际数学建模竞赛,工科数学杂志社,1994。
4. 王树禾,图论及其算法,中国科学技术大学出版社,1990。