最佳灾情巡视路线模型

《最佳灾情巡视路线模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最佳灾情巡视路线模型【摘要】“图论”是组合数学的分支，它与其他的数学分支，如群论、矩阵论、拓扑学，数值分析有着密切的联系。在其它科学领域，如计算机科学、运筹学、电网络分析、化学物理以及社会科学等方面图论也具有越来越重要的地位，并已取得丰硕的成果。而且，图论的理论和方法在数学建模中也有重要应用。本文概述了一些常用的图论方法和算法，并通过举例（灾情巡视路线）说明其在数学建模中的应用。【关键词】图论灾情巡视Hamilton回路数学模型预备知识定义1完全图：如果图G中每一对不同的顶点恰有一条边连接，则称此图为完全图。定义2连通图：如果对图G=（V，E）的任何两个顶点u与v，G中存在一条（u-

2、v）路。则称G是连通图。定义3加权图：边上有数的图称为加权图。在加权图中，链（迹、路）的长度为链（迹、路）上的所有边的权植的和。定义4Hamilton回路：图G中的一个回路C称为一个Hamilton回路如果C含有G的所有顶点。含有Hamilton回路的图称为Hamilton图。定义5欧拉回路：经过图G的每条边的迹称为欧拉迹，如果这条迹是闭的，则称这条闭迹为G的欧拉回路。一数学建模中常用的图论方法1迪克斯特拉算法（Dijkstra）1.1问题来源在加权图中，我们经常需要找出两个指定点之间的最短路，通常称为最短路问题。解决最短路问题的方法之一就是迪克斯特拉算法。1.2基本思路假定P：V→

3、V→…V→…→V→…→V是从V到V的最短路，则它的子路V→…→V一定是从V到V的最短路。否则从V出发沿路p走到V，,然后沿V到V的最短路走到V再沿路P从V到V，这样得到一条新的从V出发到V的路，其长度小于P，与P是最短路的假设矛盾。91.3算法设G为所有权都为正数的加权连通简单图。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)+

4、W(u,v)

5、出发的城市。2.2算法设G=（V，E）是一个赋权完全图，根据实际问题作如下规定：对V（G）中的任何三个顶点U，V和X，满足W（UV）+W（VX）≥W（UX）（1）任选一个顶点V作起点，找一条与V关联其权最小的一条边e,e9的另一个端点记为V，得一条路VV；（1）设已选出路VV…V,在V（G）-{V，V…V}中取一个与V最近的相邻顶点V,得VV…VV；（2）若i+1

6、（VV）+W(VV)

7、点表示两条街道间的交叉点，每边的权表示街长。要找一条从邮局出发的回路，使之包含G的每一边至少一次，且该回路的权达到最小。3.2算法（1）任意取一个顶点V，令W=V；（2）假定迹W=VeV…eV已经选出，那么用下列方法从E（G）-{e,e,…,e}中选取e:①e与V相连；②除非没有别的边可选择，e不是G={e,e,…,e}的割边；（3）当（2）不能执行时，停止。否则让i+1→i.,转（2）。9二图论方法的应用举例灾情巡视路线模型1问题重述已知某县的乡村公路网