6图与网络模型.ppt

1、曲线图和网络模型，瑞士数学家欧拉在1736年发表了题为“几何下的解决方法”的论文，有效地解决了戈尼戈内斯堡的“七巧板问题”。这是历史上第一篇图表论文，欧拉被公认为图表理论的创始人。18世纪，戈涅斯堡城有一条河.河上游的七座桥连接着河的两岸和河中的两个岛。当时那里的人们热衷于游戏，一个旅行者如何一次只走这七条腿一次，回到原来的起点。(莎士比亚，哈姆雷特)没有人能想到这样的路，也不能说明行走的方法不存在。这就是著名的“七桥”难题。七桥问题：欧拉把这个问题归结为图论的问题。他用A，B，C，D 4点表示河流两岸和岛屿，用两点之间的连接表示桥梁。7腿的问题是在A，B，C，D的任何一点上，每个边只通过一次

2、就能回到原点吗？欧拉证明了这种行为不存在，并对这种问题做出了一般结论。1857年，英国数学家汉密尔顿发明了一种使用固体十二面体(象征地球)的游戏。正十二面体的20个部分分别代表世界20个城市，要求游戏玩家从任何城市出发。通过各个城市，寻找一次只能回到原来起点的路，这就是“全球旅行”问题。(阿尔伯特爱因斯坦，Northern Exposure(美国电视剧)，与七条腿的问题不同，他在图中找到只通过每个边一次的路，称为欧拉回路，后者在图中找到只通过每个点一次的路，可以成为汉密尔顿循环。大卫亚设、北境(美国电视剧)、北境(美国电视剧)在这个时候，米露问题、棋盘末的步行路线等很多游戏难题，吸引了很多学者

3、。(莎士比亚、米露、米露、米露、米露、米露、米露、米露、米露)这些看似微不足道的游戏带来了很多实用的新问题，从而开拓了新的学科。(莎士比亚，哈姆雷特)图论的第一部专着是匈牙利数学家奥科英写的有限度和无限度的理论，发表于1936年。从1736年欧拉的第一篇论文到这部前作已经过了200年，总的来说，这个时期导论的发展是缓慢的。到20世纪中期，电子计算机的发展和离散数学问题变得越来越重要，提供离散数学模型的导论迅速发展，成为运行研究中一个非常活跃的重要分支。目前导论已广泛应用于管理科学、计算机科学、信息论、控制论、物理学、化学、生物学、心理学等各个领域，取得了丰硕的成果。图片和网络是运营研究(Ope

4、rations Research)的经典和重要领域，涵盖经济管理、工业工程、运输、计算机科学和信息技术、通信和网络技术等多个领域。下面要讨论的最短路径问题、最大流问题、最小成本流问题、匹配问题等都是图和网络的基本问题。例1最短路径问题集装箱司机被命令在最短时间内将货物从甲地运到乙地。从甲地到乙地的道路网纵横交叉，所以有多种行车路线，这个司机应该选择哪种路线？假设集装箱卡车的运行速度恒定，这个问题就等于要找到从甲地到乙地的最短段落。例2道路连接问题一个地区有几个主要城市，目前正在建设高速公路，连接这些城市，允许任何城市通过高速公路直接或间接到其他城市。假设您已经知道在两个城市之间建设高速公路的费

5、用，如何决定在哪个城市之间建设高速公路，从而使总费用降至最低？示例3分配问题一名公司经理安排了一名员工(每个人一名)，准备完成此任务。由于每个员工的特点不同，徐璐其他员工完成同一任务时获得的收益是不同的。分配工作方案的方法可以最大限度地提高总收益。例如，4中国邮递员问题(CPPchinese postman problem)一名邮递员负责投递一个街区的邮件。如何为他(她)设计最短的递送路线？这个问题是我国官媒曲教授1960年首次提出的，因此国际上被称为中国邮递员问题。例5旅行上的问题(TSPtraveling salesman problem)，一名推销员准备去多个城市销售商品。如何为他(她)

6、设计最短的旅行路线？对这个问题的研究历史很悠久，常被称为旅行上的问题。问题。例6运输问题有些原材料有产地，现在需要将原料从产地运到使用这些原材料的工厂。假设一个产地的产量和加工场的需求已知，单位产品在哪个产地被称为某工厂的运费，如何安排运输方案，使总运输成本最小化？上述问题有两个共同的特征。第一，其目的是在几个可能的计划或方案(在数学上称为优化或优化问题)中，从某种意义上寻找最佳计划或方案。第二，可以用图形的形式轻松地说明和表达。在数学上，与此图相关的结构称为网络。与图和网络相关的优化问题是网络优化或“netwok optimization(网络优化)”问题。下面首先简要介绍了图和网络的一些基

7、本概念。第一盗窃和网络的基本知识，1，地图和网络的基本概念1。绘画及其分类自然界和人类社会可以用图形描述大量实物和事物之间的关系。例如，要反映5个队参加的球类比赛的情况，可以用圆点表示队，用点对点连接表示两个队已经比赛了。例如，职务分配问题，我们可以用点来表示工人和要完成的工作，点对点连接表示每个人都能胜任这份工作。这些例子包括物质结构、电路网络、城市规划、运输、物资配置等，也可以用点和线连接的图来模拟。如上例所示，此处研究的图与平面几何图形的图不同。它只关心图形中有多少个点，点和点之间没有连接，连接方式是直线还是曲线，点和点的相对位置如何。都不重要。(大卫亚设，Northern Exposu

8、re(连接)总而言之，这里说的图是反映对象之间关系的工具。图的理论和方法是从各式各样的具体图和与他们相关的实际问题中抽象出共同点，找出其归率、性质、方法，并应用于解决实际问题。定义1 .一个图是由E=组成的二进制组，E=是点集V=和V中元素的无序对的集合。如果v，E是有限集，那么G就成为有限图，否则就成为无限图。本章只讨论有限的图片。如果两点u，v属于v，边(u，v)属于e，则u，v将两个点相邻。u，v成为边(u，v)的端点。两个ei，EJ属于E。如果有公用端点U，则ei，EJ相邻。边ei，EJ成为点U的连接边。m(G)=|E|表示地物G中的面数，year(G)=| V |表示地物G中的点数。

9、不引起混淆，用m，n简要记录。2.顶点的二次定义以5点v结束的面数称为点v的二次，deg(v)，精简d(v)。2，图和网络的数据结构用矩阵表示图便于研究图的性质和应用，图的矩阵表示方法有矩阵、邻接矩阵、关联矩阵、循环矩阵、切集矩阵等，仅介绍其中的两个一般矩阵。，定义11网络G=(V，E)，边，其中矩阵A是网络G的加权矩阵，定义12为图G=(V，E)构造矩阵A=。其中：称为矩阵A。g为无向图时，相邻矩阵是对称矩阵。第3节最短路径问题，最短路径问题是网络理论中应用最广泛的问题之一。由于许多优化问题，因此可以创建此模型，例如设备更新、管道布局、回路布局、工厂布局等。图论方法比较有效。最短路径问题的一般公式如下：将G=(V，E)作为连接道路，地物的每一侧作为图形上的两点，获取道路，以便他使中所有道路中的总权成为最小的道路。也就是说，最小。、下面介绍了可用于解决这些最短路径问题的三种算法。1.Dijkstra算法是Dijkstra在1959