数学建模中的图论方法.ppt

数学建模中的图论方法 数学建模中的图论方法----图论中的几个实用算法 最邻近算法 ⅰ 选任意点作为始点，找出一个与始点最近的点，形成一条边的初始路径。然后用ⅱ逐点扩充这条路径。 ⅱ 设x表示必威体育精装版加到这条路径上的点，从不在路径上的所有点中，选一个与x最邻近的点，把连接x与此点的边加到这条路径中。重复这一步，直到G中所有顶点包含在路径中。 ⅲ 把始点和最后加入的顶点之间的边放入，这样就得到一个回路。 数学建模中的图论方法----图论中的几个实用算法 例 对加权完全无向图K5如图(a)，如果从v1出发，使用“最邻近方法”得到的哈密尔顿回路如图(b)，总距离为40；最小哈密尔顿回路的总距离为37（如图(c)）。 (a) (b) (c) 数学建模中的图论方法----图论中的几个实用算法 6.匈牙利算法 分工问题：工作人员 去做n件作 ，每人适合做其中的一项或几项，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？ 数学模型：G是二分图,结点集划分为 , , ,当且仅当 适合做工作 时, ,求G中的最大匹配.解决这个问题可以用1965年Edmonds提出的匈牙利算法. 数学建模中的图论方法----图论中的几个实用算法 最佳分工问题：在分工问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个方案，使公司总效益最大。 数学模型：在分工问题的模型中，图G的每边加了权 表示 做工作 的效益，求加权图G上的权最大的完备匹配。 解决这个问题可以用Kuhn-Munkras算法。 数学建模中的图论方法----其他问题 5.其他问题 1. 地图着色问题 把无环图G的结点皆染上颜色，且使相邻的结点颜色不同，又所用的颜色最少，称这个颜色数为G的色数，记为 。 定理 设G为无环图，则 ，其中 是G中结点的最大度数。 1976年，Appel和Haken用计算机证明了下面的 四色定理 若G是平面图，则 。 数学建模中的图论方法----其他问题 (1) 考试日程问题: 选修课考试安排时,要避免任何一位学生所选不同课程在同一天考,问最少几天才能完成? 数学模型: 以每门课程为结点,仅当两门课程被同一位学生选修时,在这两个结点之间连上一条边,构作一个图G,求取 即为所求。 (2) 存储安全问题: 某公司生产若干种化学制品,其中有些制品如果放在一起可能发生化学反应,引起危险.因此公司必须把仓库分成相互隔离的若干区.问至少要划分多少小区,才可安全存放? 数学模型: 以每种货物为结点,仅当两种货物放在一起不够安全时,在这两个结点之间连上一条边,如此得到的图G的色数 即为所求。 数学建模中的图论方法----其他问题 (3) 频率分配问题: 地面上有若干无线电发射台,对每台分配一个频率供其使用,频率用自然数从1起编号,称为信道号码,为排除同信道的干扰,要求使用同信道的发射台相距必须大于指定的正数d,问至少要几个信道? 数学模型: 以 为半径,以发射台为圆心作圆,仅当两圆有公共点时,在两个圆心之间加一边,以圆心为结点,得到图G (圆盘图), 即为所求。 湖南文理学院 张莉茜 数学建模中的图论方法 1. 引言 2. 图论的基础知识 4. 图论的几个实用算法 5. 其他问题 3. 综合例题 数学建模中的图论方法----引言 1. 引言 图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模的意识和能力。 数学建模中的图论方法----引言 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连结起来（如图）。问题是：要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。 问题转化为：从任一点出发一笔画出七条线再回到起点。 数学建模中的图论方法----引言 注：图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。 欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每