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

数学建模中的图论方法,湖南文理学院,张莉茜,数学建模中的图论方法,1. 引言,2. 图论的基础知识,4. 图论的几个实用算法,5. 其他问题,3. 综合例题,数学建模中的图论方法-引言,1. 引言,图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模的意识和能力。,数学建模中的图论方法-引言,图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连结起来（如图）。问题是：要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。,问题转化为：从任一点出发一笔画出七条线再回到起点。,数学建模中的图论方法-引言,注：图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。,欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。,数学建模中的图论方法-图论的基础知识,2.图的基础知识,图G是由非空结点集 以及边集 所组成，记作 。它的结点数称为阶。 根据边有无方向，图分为有向图和无向图。有向图的边去掉方向后所得的图称为原有向图的基础图(或底图)。 没有自环或多重边的图称简单图。 有些实际问题抽象出来的图，边上往往带有信息，在边上附加一些数字来刻划此边，称权，此时该图称加权图。 无向图中与结点v相关联的边数称为v的度数，记 ，有向图中以v为起点或终点的边数分别称为v的出度和入度，记 。 握手定理：（1）无向图中所有结点的度数之和等于边数的两倍。 （2）有向图中所有结点的出度(入度)之和等于边数。 推论：任何图的奇结点必为偶数个。 例如，一群人中，有奇数个朋友的人必为偶数个。,数学建模中的图论方法-图论的基础知识,如果简单无向图的任两个结点均邻接，称之为完全图，n阶完全图记为 ，它的每个结点的度数等于 ,边数等于 。,一个边的序列(或点的序列)称路径，封闭的路径称回路。边不重复的路径称简单路径，点不重复的路径称基本路径。路径所含边的条数称为路径的长度。,如果存在从结点u到v的路径，则称从u到v可达。如果u到v可达，则从u到v的路径中长度最短的路径称为短程线（或测地线），它的长度称为从u到v的距离,记为 ；如果u到v不可达，则记 。 如果无向图G的任两个结点都可达，则称G为连通图。,数学建模中的图论方法-图论的基础知识,，,如图1，它们的邻接矩阵分别为：,数学建模中的图论方法-图论的基础知识,，,连通无回路图称为树。每个连通分支都是树的无向图称为森林,在结点数确定的情况下，树是连通图中边数最少的图，也是无回路图中边数最多的图,每个连通图G至少有一个生成子图是一棵树，称之为G的生成树。显然每个连通图都有生成树，而一般来说生成树不唯一(而边数是确定的)。,如果G是一个加权连通图，我们希望找一棵权之和最小的生成树，称为最小生成树。,定理：若树的结点数为n，边数为m，则m=n-1。,数学建模中的图论方法-图论的基础知识,例 设有6个城市，它们之间有输油管道连通，其布置图如图(a)所示战争期间，为了保卫油管不被破坏，需派部队看守，看守一段油管需一连士兵为保证各城市间输油畅通，最少需派几连士兵？他们应驻于那些油管处？ 解：此问题即为寻找图(a)的生成树问题 由图知，结点数为6，故其生成树的边数为5，即最少需派5连士兵看守其看守地段可见图(b)、(c)、(d)所画之线段,数学建模中的图论方法-图论的基础知识,如果图G中具有一条经过所有边的简单回路,称欧拉回路,含欧拉回路的图称为欧拉图；如果图G中具有一条经过所有边的简单(非回路)路径,称欧拉路。 定理:(1)连通无向图G是欧拉图的充要条件是G的每个结点均为偶结点; (2) 连通无向图G含有欧拉路的充要条件是G恰有两个奇结点,且欧拉路必始于一个奇结点而终止于另一个奇结点.,数学建模中的图论方法-图论的基础知识,图1的所有结点均为偶结点，故为欧拉图，一条欧拉回路为： 。 图2有2个奇结点，故不是欧拉图，但有欧拉路： 。,（1）,（2）,数学建模中的图论方法-图论的基础知识,如左图是某街道图形。洒水车从A点出发执行洒水任务。试问是否存在一条洒水路线，使洒水车通过所有街道且不重复而最后回到车库B？,（蚂蚁比赛问题）如右图所示，甲、乙两只蚂蚁分别位于结点 处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结 点 处。如果他们的速度相同，问谁先到达目的地？,数学建模中的图论方法-图论的基础知识,哈密尔顿回路，起源于一个名叫“周游世界”的游戏，它是由英国数学家哈密尔顿（Hamilton）于1859年提出的。他用一个正十二面体的20个顶点代表20个大城市（图(a)），这个正十二面体同构于一个平面图（图(b)）。要求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点。这个游戏曾风靡一时，它有若干个解。图(b)给出了一个解。,（a）,（b）,数学建模中的图论方法-图论的基础知识,如果图G中具有一条经过所有结点的基本回路（称哈密尔顿回路），则称为哈密尔顿图。,虽然哈密尔顿图判定问题与欧拉图判定问题同样有意义，但遗憾的是至今为止还没有找到一个判别它的充分必要条件，这是图论中尚未解决的主要问题之一。,数学建模中的图论方法-图论的基础知识,设无向图 ，如果存在 的一个分划 ，使得G的每一条边的两个端点分属 和 ，则称G为二部图(或偶图)。 和 称为互补结点子集，此时可将G记为 。,设 是二部图，若 ，且M中任何两条边均不相邻，则称M是G的一个匹配；具有最大边数的匹配称为最大匹配；若最大匹配M满足 ，则称M是G的一个完备匹配，此时若 ，则称M为V1到V2的一个完备匹配；若 ，则称M是G的一个完美匹配,数学建模中的图论方法-综合例题,例1 证明任意六个人的集会上，总会有三人互相认识或者不认识,证明 这是1947年匈牙利数学竞赛出的一道试题，因为它很有趣且很重要，后来曾收录到美国数学月刊及其它数学刊物上。这类问题可以转化为图论中的完全图染色问题,把参加集会的人看作结点，作一个完全图，如果两个人认识，则两结点间的连线涂上红色，否则涂上蓝色问题转化为：无论怎样涂色，总可以找到红或蓝,3.综合例题,数学建模中的图论方法-综合例题,例1 证明任意六个人的集会上，总会有三人互相认识或者不认识,证明 设六个结点为 。从 引出的边有五条，而颜色只有红蓝两种，由抽屉原理，至少有三条边同色，不失一般性，假定有三条边 为红色。,（1）如果结点 之间至少有一条红边，比如 是红边，则得到红色的三角形 ； （2）如果结点 之间的边全是蓝色的，则得到蓝色的三角形 。 关于问题中的结点数，对任何 ，命题都成立但 当 时，命题便不成立了。这说明：不同的六个点是保证用两色涂染其边，存在同色三角形的最少点数。,数学建模中的图论方法-综合例题,例2 出席某次国际学术会议的有六个成员a, b, c, d, e, f，其中：a会讲汉语、法语和日语；b会讲德语、日语和俄语；c会讲英语和法语；d会讲汉语和西班牙语；e会讲英语和德语；f会讲俄语和西班牙语如将此六人分成两组，是否会发生同一组内的任意两人不能互相直接交谈的情况？,数学建模中的图论方法-综合例题,例3 某中学有3个课外小组：英语组(A)、物理组(B)和生物组(C)，有5名学生a, b, c, d, e， (1)已知a, b为A组成员，a, c, d为B组成员，c, d, e为C组成员； (2)已知a为A组成员，b, c, d为B组成员，b, c, d, e为C组成员； (3)已知a为A组成员，a又为B组成员，b, c, d, e为C组成员 问在以上三种情况下，能否各选出3名不兼职的组长？,解： 根据三种已知情况，分别画出二部图，如图所示 记 ，,数学建模中的图论方法-图论中的几个实用算法,4.图论中的几个实用算法,1加权图中的最短路径的Dijkstra算法,最短路径问题：给定连接若干城市的铁路网，寻找从指定城市到各城市去的最短路线。,问题：在加权的简单连通无向图G(V,E,W)中，求一结点a(源点)到其它结点x的距离称单源问题。,Dijkstra算法的基本思想是：若 是从 到 的最短路径，则也必然是从 到 的最短路径。,数学建模中的图论方法-图论中的几个实用算法,2求最小生成树的Kruskal算法,数学模型：在一个连通加权图上求权最小的连通生成子图，显然，即求权最小的生成树，称最小生成树。,筑路选线问题：欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为 ，设计一个线路图，使总造价最低。,Kruskal算法（避圈法）1956年 设G为由n个顶点、m条边构成的加权连通图。先将G中所有的边按权的大小次序进行排列，不妨设 ，, ； 若 导出的子图不含回路，则 ； 若A中已有n-1条边，则stop；否则 ，转。,数学建模中的图论方法-图论中的几个实用算法,例：求图(a)中加权图的最小生成树,解： 用Kruscal算法可以求得最小生成树如图(b),数学建模中的图论方法-图论中的几个实用算法,3.中国邮路问题,中国邮路问题：邮递员传送报纸和信件，都要从邮局出发，经过他所管辖的每一条街道，最后回到邮局，要求最短的传送路线,数学模型：在加权图上找一条经过所有边至少一次的回路，使它的权数最小。,如果是欧拉图,则所求回路必为欧拉回路。下面给出在欧拉图上求取欧拉回路的Fleury算法。,数学建模中的图论方法-图论中的几个实用算法,(1)Fleury算法,(3) 重复步骤(2),直至不能进行下去为止。,(1) 任取起始结点 ,令 ； (2) 设路径 已选定,则从 中选一边,使得:,() 与 相连(共端)； () 除非已无选择余地, 不要选 的桥(断边),即 仍连通；,数学建模中的图论方法-图论中的几个实用算法,(2)Edmonds-Johnson算法,如果G不是欧拉图，即存在奇结点，这时某些边必被重复走过，我们称这样的边为重复边。考虑到奇结点必为偶数个，我们可以把奇结点划分成若干对，每对之间在G中有相应的最短路，将这些最短路的边以原来的权作为重复边叠加在原图上形成一个多重图G*，则G*是一个欧拉图，可用Fleury算法求出欧拉回路。问题是当G的奇结点较多时，可能有很多的配对方法，应怎样选择配对，使相应的欧拉回路的权最小呢？1973年，Edmonds和Johnson给出下面的算法：,数学建模中的图论方法-图论中的几个实用算法,(2)Edmonds-Johnson算法,设G是连通加权图, (1) 求出G的奇结点集 ； (2) 用Dijkstra算法求得V0中每对结点 的距离 ； (3) 构作加权完全图 :以 为结点集,以 为边 的权； (4) 求 中权之和最小的完备匹配M； (5) 用Dijkstra算法求M中边的端点之间在G中的最短路径； (6) 在(5)中求得的每条最短路径上每条边添加一条同权的新边,即得所求之欧拉图G*； (7) 在G*上用Fleury算法求一条欧拉回路,即为问题的解。,数学建模中的图论方法-图论中的几个实用算法,4.迷宫和DFS算法,迷宫问题：一座迷宫，游人事先未知其结构，如何搜索前进，保证万无一失地通过每一通道再从入口退出？,纵深搜索原则：任选一条未曾走过的通道就尽可能远地走下去，直至无未曾走过的路可走时，沿未逆行过的最晚来路返回，发现有未走过的路，则沿它尽可能远地走下去，依次运行至重返入口止。 1973年，Hopcroft和Tarjan把上述纵深搜索原则编写成DFS(Depth First Search)算法.,例如，在地图是未知的情形下，双车道单车扫雪车，按右侧通行交通规则，依DFS算法的过程安排扫雪工作程序即可。,数学建模中的图论方法-图论中的几个实用算法,5.TSP(货郎担问题)及“最邻近算法”,一个与哈密尔顿图有密切关系的问题是所谓“货郎担”问题或“旅行商”问题(Travelling Salesman Problem)：货郎为了销售物品，要去访问若干个村、镇，然后回到自己所住的地方。假设每个村镇间都有路，那么他应该怎样设计所走的路线，使得能对每个村镇恰好访问一次且走的路程最短？用图论的话来讲就是：在一个加权的完全无向图中，如何寻找一条最短的哈密尔顿回路？,迄今为止还没有找到一个解决“货郎担”问题的有效算法（多项式算法）。一般来讲，这个问题比哈密尔顿问题更加困难些。下面介绍一个近似解法“最邻近方法”（或称“贪婪算法”），这是实际工作中经常采用的方法：,数学建模中的图论方法-图论中的几个实用算法,最邻近算法, 选任意点作为始点，找出一个与始点最近的点，形成一条边的初始路径。然后用逐点扩充这条路径。 设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 (圆盘图), 即为所求。,数学建模中的图论方法-其他问题,2. 网络流的最大流问题 把商品由产地运往市场，交通网上每个路段运输能力给定的条件下，设计一个运输方案，使得运输最快。 1956年，Ford和Fulkson给出求最大流的2F算法。,3. 规划审核技术与关键轨道方法 规划审核技术PERT(Program evaluation and review technique)与关键轨道方法CPM(Critical path method)是典型的统筹方法. 总工期问题；赶工优化问题；工程设备量问题。,数学建模中的图论方法-其他问题,4. 图的连通度 破坏交通问题：游击队破坏敌人的铁路或公路，用炸毁车站、炸断桥梁或拆毁铁轨的游击战术。今欲使指定的两个车站间交通瘫痪，问至少要破坏两个指定车站以外的几个车站或几段铁路？ 数学模型：图的分离集与分离数。,可靠通讯网的构作问题：我们要构作一个有线通讯网，使得敌人炸坏我几个通讯站之后，其余通讯站仍然能彼此通话，有两个要求应该得以满足，一个是不怕敌人炸毁的站数要多，一个是整体造价要低。 数学模型：G是加权连通图，k是给定的自然数，求G的有最小权的k连通生成子图。 1962年，Harary给出了一种解法。,数学建模中的图论方法-其他问题,5. 覆盖集与控制集 消防设施的安置：在一些交叉路口安置一些消防设施，只有与路口直接相连的街道才能使用它们。为使所有街道必要时都有消防设施可用，在哪些路口安置设施才最节省呢？ 数学模型：求最小覆盖集(Minimum Covering Set)。,监狱看守问题：一座监狱的几间牢室有道路相连，看守要设在通过道路能直接监视所有牢室的地方。如果看守不得走动，那么他们应呆在某些牢室(即路口)所在地，问至少需要几名看守才能完成监视任务呢？ 数学模型：求最小控制集(Minimum Dominating Set)。,