数学建模中的图论方法

数学建模中的图论方法一、引言我们知道，数学建模竞赛中有问题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）。图G1=（V1，E1）称为G的子图，如果V1V，E1E。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）的子图Gt=（Vt，Et）是一个树，且Vt=V，称Gt是G的生成树。G连通的充要条件是G有生成树。生成树一般而言数量很大。8．设对图G=（V，E）的每一条边e赋予一个实数W（e），称为e的权，G称为赋权图(加权图)。假设G是连通的赋权图，要找G的连通子图G*=（V，E*），使得W（G*）=EeeW)(为最小。显然G*应为G的一个生成树。G的权最小的生成树称为G的最小生成树。三、算法介绍3．1最短轨道问题背景：给定连接若干城市的铁路网，寻求从指定城市v0到各城v去的最短道路。数学模型：图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)取最小值，v(i＋1)(Si的余集)。令S(i＋1)＝Si＋{v(i+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的最小生成树。该算法的复杂度为O(eloge)，其中e是图G中的边数。2．普莱姆(Prim)算法思路：从点入手来选边步骤：(1)在图G中任取一个节点vi1，并放入T中。(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中节点全部取完。该算法的复杂度为O(n^2)，其中n为图G的节点数。3．1975年管梅谷提出的“破圈法”3．3Steiner生成树实际背景：在已有网络上选择连通几个城市的最廉价交通或通讯网。数学模型：从已知的加权连通图上求取最小的树状子图，使此树包含指定的顶点子集。第一个的边长为3，第二个的边长为1，总费用第二个更少。分析：与传统的最小生成树相比，这里可以引入若干“虚拟站”并构造一个新的Steiner树，这样可以降低由一组站生成的传统的最小生成树所需的费用(降低的费用大概为13.4%)。而且为构造一个有n个顶点的网络的费用，最低的Steiner树决不需要多于(n－2)个虚设站。当然，有时最小Steiner生成树与最小生成树相同。寻求最小Steiner生成树的算法有Melzak算法(1961年)，但是这是一个指数时间的算法，现在没有多项式时间的算法，换句话说它是一个NP问题。而且，这里的要求是用直折线代替欧氏直线距离，因而不能利用直接的算法。所以在解决这样的问题的时候，为减少运算的时间，理论上的分析是必要的：比如树的长度的下界，Steiner树的存在性，虚设站的位置等等。常用的算法还包括穷举法、模拟退火法等。Melzak算法：其基础是3点steiner树，即3点Fermat问题的几何作图法。参考[2]，Page375。模拟退火法原理：模拟退火法(Simulatedannealing,SA)是模拟热力学中经典粒子系统的降温过程，来求解极值问题。当孤立粒子系统的温度以足够慢的速度下降时，系统近似处于热力学平衡状态，最后系统将达到本身的最低能量状态，即基态，这相当于能量函数的全局极小点。其步骤如下(也称为Metropolis过程)：（1）给定初始温度T0，及初始点，计算该点的函数值f(x)。（2）随机产生扰动Δx，得到新点x′=x+Δx，计算新点函数值f(x′),及函数值差Δf=f(x′)-f(x)。（3）若Δf≤0，则接受新点，作为下一次模拟的初始点；（4）若Δf0，则计算新点接受概率：，产生［0，1］区间上均匀分布的伪随机数r,r∈［0,1］，如果p(Δf)≥r，则接受新点作为下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点。模拟退火法实例：1．MCM91B(通讯网络中的极小生成树)是一个求STEINER生成树问题，参见《工科数学专辑》Page：70－78。2、CMCM97A题97年全国大学生数模竞赛A题“零件的参数设计”，可以归结为非线性规划模型，由于目标函数很复杂，且又是一个多维函数，因此求解比较困难，为应用模拟退火法进行求解，将7个自变量的取值范围进行离散化，取步长为0.0001，这样，所有7个变量取值就组成了一个极为庞大的离散空间,而这个问题变成组合优化模型。这个问题算法的状态调整规则是：每次从7个自变量中随机选取1-4个，让选取的自变量随机移动，考虑选取的自变量在两个方向移动组合，从中选取最佳的作为候选者，自变量移动的距离随着温度的降低而减少，为避免陷入局部极小，可以从多个随机选取的初始值开始计算，算法的其它步骤同上。3、CMCM98B题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：按照如下规则确定是否做调整：如果D0，则调整如果D0，则按照EXP(-D/T)的概率进行调整步8：T*0.9--T，降温3．4Euler回路设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铲雪问题中单车道单车扫雪－地