《图论与网络流》PPT课件.ppt

《《图论与网络流》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论与网络流》PPT课件.ppt（127页珍藏版）》请在三一办公上搜索。

1、图论与网络应用,B题 灾情巡视路线 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的灾情巡视路线。,1998年全国大学生数学建模竞赛题目,假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。在上述关于T,t和V的假定下，

2、如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳灾情巡视路线的影响。,2001建模竞赛题目（大专组）,C题 基金使用计划 某校基金会有一笔数额为M元的基金，打算将其存入银行或购买国库券。当前银行存款及各期国库券的利率见下表。假设国库券每年至少发行一次，发行时间不定。取款政策参考银行的现行政策。校基金会计划在n年内每年用部分本息奖励优秀师生，要求每年的奖金额大致相同，且在n年末仍保留原基金数额。校基金会希望获得最佳的基金使用计划，以提高每年的奖金额。,请你帮助校基金会在

3、如下情况下设计基金使用方案，并对M=5000万元，n=10年给出具体结果：1.只存款不购国库券；2.可存款也可购国库券；3.学校在基金到位后的第3年要举行百年校庆，基金会希望这一年的奖金比其它年度多20%。,2000“网易杯”全国大学生数学建模竞赛试题,B题 钢管订购和运输 要铺设一条 的输送天然气的主管道,如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。,一个钢厂

4、如果承担制造这种钢管，至少需要生产500个单位。钢厂 在指定期限内能生产该钢管的最大数量为 个单位，钢管出厂销价1单位钢管为 万元，如下表：,1单位钢管的铁路运价如下表：,1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3）如

5、果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。,2008年北京奥运会的建设工作已经进入全面设计和实施阶段。奥运会期间，在比赛主场馆的周边地区需要建设由小型商亭构建的临时商业网点，称为迷你超市（Mini Supermarket,以下记做MS）网，以满足观众、游客、工作人员等在奥运会期间的购物需求，主要经营食品、奥运纪念品、旅游用品、文体用品和小日用品等。在比赛主场馆周边地区设置的这种MS，在地点、大小类型和总量方面有三个基本要求：满足奥运会期间的购物需求、分布基本均衡和商业上赢利。,2004年 A题

6、 奥运会临时超市网点设计,鸟 巢,国家体育馆,水立方,请你按以下步骤对图2的20个商区设计MS网点：1）根据附录中给出的问卷调查数据，找出观众在出行、用餐和购物等方面所反映的规律。,2）假定奥运会期间（指某一天）每位观众平均出行两次，一次为进出场馆，一次为餐饮，并且出行均采取最短路径。依据1的结果，测算图2中20个商区的人流量分布（用百分比表示）。,3）如果有两种大小不同规模的MS类型供选择，给出图220个商区内MS网点的设计方案（即每个商区内不同类型MS的个数），以满足上述三个基本要求。,4）阐明你的方法的科学性，并说明你的结果是贴近实际的。,例1 最短路问题（SPPshortest pat

7、h problem）,一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？,例2 公路连接问题,某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。,例3 指派问题（assignment problem）,一家公司经理准备安排n名员工去完成n项任务，每

8、人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？,例4 中国邮递员问题（CPPchinese postman problem）,一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？,由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。,（匹配问题）,例5 旅行商问题（TSPtraveling salesman problem）,一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好

9、一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商(推销员）问题。,例6 运输问题（transportation problem）,某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂。假定M个产地的产量和N家工厂的需求量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？,上述问题有两个共同的特点：,一，其目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；,二，都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（netwo

10、rk）。,与图和网络相关的最优化问题就是网络最优化或称网络优化（network optimization）问题。,由于多数网络优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网络流（network flows）或网络流规划等。,故事的背景是十八世纪的东普鲁士，美丽的Pregel 河穿过哥尼斯堡；人们在河的两岸及河中两个小岛间建立了七座桥，将它们连结成一个风景优美的公园。有一天，有人突发奇想：如何才能走遍七座桥，而每座桥都只能经过一次，最后又回到原先的出发点？,例1 七桥问题 18世纪东普鲁士哥尼斯堡被普列格尔河分为四块，它们通过七座桥相互连接起来，问能否从某块陆地出发，

11、经每座桥一次而且仅一次，回到出发点？,任何一个点作为出发点都必须先“出”后“回”，才能行遍与该点相连的桥。,行遍性问题,对此问题，欧拉给出了一个通用判定规则：,思考：能否将图的每一条线走遍，但只走一次。（不必回到原顶点）,从图的某一个顶点出发，经过每条线正好一次，当且仅当这个图连成一片且最多只有两个顶点是奇次的，且必须从某奇次点出发，到另一奇次点结束。,以下网络中哪一个是可以遍历的(即一笔而不重复地画成)？,一笔画问题,欧拉注意到：一个奇顶点在这种遍历式的旅行中，要么是起点，要么是终点由于一个遍历的网络只能有一个起点和一个终点，因而这种网络的奇点数不能多于两个,例2 人、狼、羊、菜渡河问题 一

12、个摆渡人F希望用一条小船把一只狼W、一头羊G和一篮白菜C从一条河的左岸渡到右岸去，而船小只能容纳F、W、G、C中的两个，决不能在无人看守情况下，留下狼和羊在一起，羊和白菜在一起，问应怎样渡河才能将狼、羊、白菜都运过去？,用小圆圈（顶点）表示河岸左边的各个状态，两点连线当且仅当两状态可在规定允许下转移。,一个人带三只狼和三只羊过河，一条船可容两只动物，没人在时，如果狼的数量不少于羊的数量就会吃掉羊，如何安全渡河?,有一天，一家人（爸爸、妈妈、2个女儿、2个儿子）和警察、小偷，想过河，船上只能装两个人，爸爸、妈妈、警察三人会划船，在过河的时候，爸爸不在的时候，妈妈会打儿子，妈妈不在的时候，爸爸会打

13、女儿。警察不在的时候，小偷会打一家人。怎样才能使他们安全的过河？,例3 化学药品存放问题 某公司生产几种化学药品a,b,c,d,e,f,g，其中某些化学药品不相容，为安全，公司要把相容的药品放在不同格中，问至少应将仓库划分为多少格？,我们可以用顶点表示各个化学药品，两顶点连线当且仅当两药品不相容，便可得一个图G:,图G的点色数便是所求的最少格数,为每个顶点赋一色，使凡有连线的两顶点异色，点色数即是使图得到正常点上色的最少色数。,图的正常点上色,地图着色问题（四色问题）：,任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。,用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一

14、个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”,世界近代三大数学难题：,1.费尔马大定理（1637年）,在阅读丢番图算术拉丁文译本时，曾在第11卷第8命题旁写道：将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。,关于此，我确信已发现了一种美妙的证法，可惜这里空白的地方太小，写不下。,经过三个半世纪的努力，这个世纪数论难题才由普林斯顿大学英国数学家安德鲁怀尔斯和他的学生理查泰勒于1995年成功证明。,3.哥德巴赫猜想（1742年6月7日，德国数学家在写给著名数学家欧拉的一封信

15、中提出）：,2.四色问题,1）任何不小于6的偶数，都是两个奇质数之和；2）任何不小于9的奇数，都是三个奇质数之和。,世界近代三大数学难题：,任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。,路线着色问题,一个人来到他从未造访过的小镇上，驾着车到处寻找他朋友的家，即使连路名都没有。朋友说，别担心，他会指示他如何到达，先向左，再向右，接着向左”,这个难题的假设是，在出发点（圆点）及道路（直线）的数量都固定的情况下，应该有办法以不同颜色标示道路，让人不管从哪一个点出发，都能到达固定的点。这在真实生活中的情况就像是，不管朋友住在哪里，只要知道你家的位置，绕再远都有办法到你家。,以图为范

16、本，如果按照蓝红红,蓝红红,蓝红红.的方式行走，不管从哪个点出发都能到黄色的点；如果是蓝蓝红,蓝蓝红,蓝蓝红.则一定能到绿点,（万能地图）,图：是指某类具体事物和这些事物之间的联系,如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。,图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。,最短路问题、行遍性问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。,例1 线性方程组,的解取决于

17、：,系数,常数项,复习：矩阵,对线性方程组的研究可转化为对这张表的研究.,线性方程组的系数与常数项按原位置可排为,例2 对随机抽取的1000人按性别（男或女）及色觉（正常或色盲）两个属性分类，得到二行二列的列联表:,称为 行 列矩阵.简称 矩阵.,简记为,这 个数称为 的元素，简称为元.,几种特殊矩阵,1.方阵(Square Matrix):,例如：,是一个 3 阶方阵.,注 意,2、矩阵的行数和列数可以不等,1、矩阵是一张数表,2.行矩阵(Row Matrix)(或行向量):,3.列矩阵(Column Matrix)(或列向量):,只有一行的矩阵,只有一列的矩阵,4.对角矩阵(Diagona

18、l Matrix):,记作,主对角线,5.单位矩阵(Identity Matrix):,主对角线上元素全为1,其他元素都是0的方阵,6.零矩阵(Zero Matrix):,注意,不同阶数的零矩阵是不相等的.,例如：,元素全为零的矩阵称为零矩阵，零矩阵记作 或.,?,矩阵的基本运算,1.矩阵相等,矩阵相等:,例,同型矩阵：两个矩阵的行数相等、列数也相等,设有两个 矩阵 那么矩阵 与 的和记作，规定为,2.矩阵的加减法,加法：,例,说明 只有当两个矩阵是同型矩阵时，才能进行加法运算.,减法:,负矩阵：,矩阵加法满足的运算规律:,3.数与矩阵相乘,数乘:,数乘矩阵的运算规律：,（设 为 矩阵，为数）

19、,矩阵相加与数乘矩阵合起来,统称为矩阵的线性运算.,并把此乘积记作,设 是一个 矩阵，是一个 矩阵，那么规定矩阵 与矩阵 的乘积是一个 矩阵，其中,4、矩阵与矩阵相乘,设,例,解,求,注意只有当第一个矩阵的列数等于第二个矩阵的行数时，两个矩阵才能相乘.,例如,不存在.,矩阵乘法的运算规律,（其中 为数）;,若A是 阶矩阵，则 为A的 次幂，即 并且,满足结合律、分配率,矩阵不满足交换律,例 设,则,（并非所有的矩阵都不满足交换律）,矩阵是否满足交换律？,矩阵乘法不满足消去律,矩阵乘法是否满足消去律？,例：,有,但是,输入矩阵的方法,(1)用中括号 把所有矩阵元素括起来；,(2)同一行的不同元素

20、之间用空格或逗号间隔；,(3)用分号(;)指定一行结束；,(4)也可以分成几行进行输入，用回车符代替分号；,(5)数据元素可以是表达式，系统将自动计算结果；,例：输入矩阵,matlab输入格式：,ans=,3,特殊矩阵函数,一、图与网络的基本概念,是由一个非空有限集合 和 中某些元素的无序对集合 构成的二元组，记为。,顶点集或节点集,边集,Vertex，edge,完备图,简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集。,图中(a),(b)为二分图，(c)为完全二分图K3,3,最小生成树：,二、图与网络的数据结构,（每边有两个顶点与其相

21、关联）,1 5 3 4 6 7,三、最短距离问题,在生产管理、交通运输和通讯领域，经常会碰到这样的问题：沿着哪条路线可以最短的时间或最少的费用把货物运往目的地？沿着哪条路线传送信息最可靠或最快捷？如何组织生产可使生产成本最低？如何制定投资计划可使利润最大？这些都可看成是在给定的加权图中，求最短路径问题。,邻接矩阵,例 某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市到其它城市间的票价最便宜的路线图。,行 遍 性 问 题,一、中 国 邮 递 员 问 题,二、推 销 员 问 题,（一）欧 拉 图,（二）中 国 邮 递 员 问 题,（一

22、）哈 密 尔 顿 图,（二）推 销 员 问 题,欧 拉 图,巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1,欧拉道路：v1e1v2e2v3e5v1e4v4e3v3,欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1,欧拉图,非欧拉图,推论1 设G是非平凡连通图，则G有欧拉道路的充要条件是G最多有两个奇次顶点.,该推论为判别图形能否一笔画给出了依据,中国邮递员问题-定义,邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线。这就是中国邮递员问题。,若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口

23、用点表示，则一个投递区构成一个赋权连通无向图.,中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最佳巡回,（管梅谷1962年）,一笔画问题,割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边,G的边e为割边,e 不含在G的圈中,圈：起点与终点重合的路径,顶点、边均不重复的通路,中国邮递员问题-算法,Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.,此时G的任何一个欧拉巡回便是最佳巡回问题归结为在欧

24、拉图中确定一个欧拉巡回,1.G是欧拉图,若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小,2.G不是欧拉图,先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回,基本思想：,（3）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对,（2）以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1,定义：设M是G

25、的一个匹配，,（1）若M渗透了G的每个顶点，则称M是G的理想匹配,（2）若M是G中含边最多的匹配，则称M为G的最大匹配,显然理想匹配是最大匹配，,但最大匹配不一定是理想匹配,理想匹配可能有多个，权最小的为最小权理想匹配。,中国邮递员问题的应用与推广：,1.铲雪车的行使路线问题：马里兰州维克米城被大雪覆盖，有两辆铲雪车清除积雪。如何安排行使路线，使得两辆车同时完成任务。,2.容量约束中国邮递员问题：城市环保局每天要派出洒水车为城市街道洒水。由于洒水车的容量有限，中途需要返回加水，若已知每英里道路需要的水量以及洒水车的容量，问如何安排车的行使路线使总行程最短？,又如：城市垃圾收集、流动餐车、道路洒

26、盐.,哈 密 尔 顿 图,1859年，数学家哈密尔顿发明了一种周游世界的游戏：在一个12面体的每个角点代表一个城市，问能否从某城市出发，沿12面体的棱行走，经过每个城市一且仅一次，最后回到出发地。,用图论的语言来讲，就是在12面体图上找出生成圈。,哈 密 尔 顿 图,推销员问题-定义,流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题,若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题,定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳H圈（

27、）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路,一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈,H回路，长22,最佳推销员回路，长4,推销员问题近似算法：二边逐次修正法：,例对以下完备图，用二边逐次修正法求较优H圈,练习 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：,例考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。,证明：设G是具有七个顶点的图，每个顶点对应于一门课程考试，如果这两个顶点对应的课程考试是由不同教师担任的，那么这两个顶点点之间有一条边，因为每个教师所担任课程数不超过4，故每个顶点的度数至少是3，任两个顶点的度数之和至少是6，故G总是包含一条哈密尔顿路，它对应于一个七门考试课目的一个适当的安排。,navTag=7,数学教研室网站,全国数学建模网站,路漫漫其修远兮，吾将上下而求索。屈原离骚,THANKS,