最佳灾情巡视路线模型.doc

最佳灾情巡视路线模型【摘要】“图论”是组合数学的分支,它与其他的数学分支,如群论、矩阵论、拓扑学,数值分析有着密切的联系。在其它科学领域,如计算机科学、运筹学、电网络分析、化学物理以及社会科学等方面图论也具有越来越重要的地位,并已取得丰硕的成果。而且,图论的理论和方法在数学建模中也有重要应用。本文概述了一些常用的图论方法和算法,并通过举例(灾情巡视路线)说明其在数学建模中的应用。【关键词】图论灾情巡视Hamilton回路数学模型 预备知识定义1完全图:如果图G中每一对不同的顶点恰有一条边连接,则称此图为完全图。定义2连通图:如果对图G=(V,E)的任何两个顶点u与v,G中存在一条(u-v)路。则称G是连通图。定义3加权图:边上有数的图称为加权图。在加权图中,链(迹、路)的长度为链(迹、路)上的所有边的权植的和。定义4Hamilton回路:图G中的一个回路C称为一个Hamilton回路如果C含有G的所有顶点。含有Hamilton回路的图称为Hamilton图。定义5欧拉回路:经过图G的每条边的迹称为欧拉迹,如果这条迹是闭的,则称这条闭迹为G的欧拉回路。一数学建模中常用的图论方法1迪克斯特拉算法(Dijkstra),我们经常需要找出两个指定点之间的最短路,通常称为最短路问题。解决最短路问题的方法之一就是迪克斯特拉算法。:V→V→…V→…→V→…→V是从V到V的最短路,则它的子路V→…→V一定是从V到V的最短路。否则从V出发沿路p走到V,,然后沿V到V的最短路走到V再沿路P从V到V,这样得到一条新的从V出发到V的路,其长度小于P,与P是最短路的假设矛盾。。G带有顶点a=V,V,…V=z,权W(V,V),若(V,V)不是G中的边,则W(V,V)=∞fori=1tonL((V)=∞L(a)=0S=Ф(初始化标记,a的标记为0,其它结点标记为∞,S为空集)当z不属于S时beginu=不属于S的L(u)最小的一个顶点S=S∪{u}对所有不属于S的顶点VifL(u)+W(u,v)<L(v)thenL(v)=L(u)+L(u,v)(这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记)End(L(z)表示从a到z的最短路的长度)这个算法经过n-1次循环后必定结束,计算量为1/2(n-1)(n-2),因而是个有效算法。,该问题实际上是求加权完全无向图中的访问每个顶点恰好一次且返回出发点的总权数最小的闭路,又称为最优Hamilton回路。如果我们将加权图中的结点看作城市,加权看作距离,旅行推销员问题就成为找出一条最短路线,使得旅行推销员从某个城市出发,沿着这条路线遍历每个城市一次最后再回到出发的城市。=(V,E)是一个赋权完全图,根据实际问题作如下规定:对V(G)中的任何三个顶点U,V和X,满足W(UV)+W(VX)≥W(UX)任选一个顶点V作起点,找一条与V关联其权最小的一条边e,e的另一个端点记为V,得一条路VV;设已选出路VV…V,在V(G)-{V,V…V}中取一个与V最近的相邻顶点V,得VV…VV;若i+1<P(G)-1,用i代i+1返回(2),否则记C=VV…。最后得到的C就是G的一条近