图论建模课件.ppt

数学建模;主讲内容; 图论是数学的一个分支，以图为研究对象。图论中的图是由若干个给定顶点及若干条连接两个顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构，可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模，因此图;论研究越来越得到这些领域的专家和学者的重视。 图论最早的研究起源于瑞士数学家欧拉，他在1736年成功地解决了哥尼斯堡七桥问题，从而开创了图论的先河。; 在此后的200多年时间内, 图论的研究从萌芽阶段，逐渐发展成为数学的一个新分支。20世纪70年代以后，由于高性能计算机的出现，使大规模图论问题的求解成为可能。目前，图论理论已广泛应用于运筹学、计算机科学、电子学、信息论、控制论、网络理论、经济管理等领域。; 由于图论有着丰富的算法和广泛的应用，所以一直以来图论问题在信息类竞赛中占有较大比重。例如，在著名的ACM/ ICPC程序设计竞赛中, 图的遍历、最小生成树、最短路径、网络流、匹配问题、图的连通性、图着色等都是常见问题。 数学建模竞赛中的图论问题不及ICPC中的普遍，难度也不大。; 本讲主要介绍图的一些基本概念及存储方法、最短路问题、及其LINGO程序。 本讲要求学生理解图论的基本概念；掌握图的邻接矩阵表示方法；能较为熟练地根据实际问题正确地建立图论模型，并利用相应的Lingo程序求解；不要求理解算法，编写程序。;A;七桥问题模拟图:;问题2:哈密顿圈（环球旅行游戏） 十二面体的20个顶点代表世界上20个城市，能 否从某个城市出发在十二面体上依次经过每个 城市恰好一次最后回到出发点？;问题3:四色问题;问题4(关键路径问题): 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机, 都要包括许多工序.这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？ ;一、图的基本概念与图的存储; 例如，右图所示的图 可表示为G(V,E)。其中， V(G)={0,1,2,3,4,5}， E(G)={(0,1),(0,2),(1,2),(1,3), (1,4),(1,5),(2,3),(2,4),(3,4)}。 1.2 无向图与有向图 所有边都没有方向的图称为无向图，如1.1中的图；每条边都有方向的图称为有向图，通常用u,v表示从u到v的有向边。; 例如，对于右图所示 的有向图G(V,E)，V(G)= {0, 1, 2, 3, 4, 5, 6}, E(G)= {0,1,1,2,1,4,1,5, 2,4,3,2,4,1,4,3,5,6}。 1.3 完全图 任何一对顶点都有一条边的图称为完全图；任何一对顶点u,v都有u,v和v,u两条有向边的图称为完全有向图。; 例如，左图为完全图，右图为完全有向图。 1.4 顶点与顶点、顶点与边的关系 在图论中，顶点与顶点、顶点与边的;关系是通过“邻接(Adjacency)”这个概念来表示的。 在无向图G(V,E)中，若(u,v)是图中的一条边，则称u和v互为邻接顶点，边(u,v)依附于u,v，或称(u,v)与u,v相关联。 在有向图G(V,E)中, 若u,v是图中的一条边，则称u邻接到v，v邻接自u，(u,v) 与u,v相关联。;1.5 路径 路径是图论中一个很重要的概念。 在图G(V,E)中, 若从vi出发，沿着一些边经过顶点vp1,vp2,…,vpm，到达顶点vj，则称顶点序列(vi,vp1,vp2,…, vpm,vj)为从顶点vi 到vj的一条路径或通路。 路径中边的数量称为路径的长度。 若路径中各顶点vi,vp1,vp2,…,vpm,vj均互相不重复，则称之为简单路径。; 若路径中第一个顶点 vi 与最后一个顶点vj重合，则称此路径为回路。 除第一个和最后一个顶点外，没有顶点重复的路径称为简单回路。 例如，; 在G1中，(0,1,4,3)为0到3的一条路径，且为简单路径, 长度为3；在G2中, (2,4,1,5)为2到5的一条路径, 长度也为3, 而(4,3,2