图论与网络流.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,图论与网络应用,1,.,2,.,3,.,B,题 灾情巡视路线,下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。,今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。灾情巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。,若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的灾情巡视路线。,1998,年全国大学生数学建模竞赛题目,4,.,假定巡视人员在各乡（镇）停留时间,T=2,小时，在各村停留时间,t=1,小时汽车行驶速度,V=35,公里,/,小时。要,24,小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的灾情巡视路线。,在上述关于,T,t,和,V,的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的灾情巡视路线。,若巡视组数已定,(,如三组），要求尽快完成巡视，讨论,T,，,t,和,V,改变对最佳灾情巡视路线的影响。,5,.,6,.,2001,建模竞赛题目（大专组）,C,题 基金使用计划,某校基金会有一笔数额为,M,元的基金，打算将其存入银行或购买国库券。当前银行存款及各期国库券的利率见下表。假设国库券每年至少发行一次，发行时间不定。取款政策参考银行的现行政策。,校基金会计划在,n,年内每年用部分本息奖励优秀师生，要求每年的奖金额大致相同，且在,n,年末仍保留原基金数额。校基金会希望获得最佳的基金使用计划，以提高每年的奖金额。,7,.,请你帮助校基金会在如下情况下设计基金使用方案，并对,M=5000,万元，,n=10,年给出具体结果：,1.,只存款不购国库券；,2.,可存款也可购国库券；,3.,学校在基金到位后的第,3,年要举行百年校庆，基金会希望这一年的奖金比其它年度多,20%,。,8,.,银行存款税后年利率（,%,）,国库券年利率（,%,）,活期,0.792,半年期,1.664,一年期,1.800,二年期,1.944,255,三年期,2.160,2.89,五年期,2.304,3.14,9,.,2000“,网易杯”全国大学生数学建模竞赛试题,B,题 钢管订购和运输,要铺设一条 的输送天然气的主管道,如图一所示,(,见下页,),。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道,(,假设沿管道或者原来有公路，或者建有施工公路,),，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程,(,单位,km),。为方便计，,1km,主管道钢管称为,1,单位钢管。,10,.,一个钢厂如果承担制造这种钢管，至少需要生产,500,个单位。钢厂 在指定期限内能生产该钢管的最大数量为 个单位，钢管出厂销价,1,单位钢管为 万元，如下表：,1,单位钢管的铁路运价如下表：,11,.,1000km,以上每增加,1,至,100km,运价增加,5,万元。,公路运输费用为,1,单位钢管每公里,0.1,万元（不足整公里部分按整公里计算）。,钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。,（,1,）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用,),。,（,2,）请就（,1,）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。,（,3,）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（,1,）的要求给出模型和结果,。,12,.,13,.,2008,年北京奥运会的建设工作已经进入全面设计和实施阶段。奥运会期间，在比赛主场馆的周边地区需要建设由小型商亭构建的临时商业网点，称为迷你超市（,Mini Supermarket,以下记做,MS,）网，以满足观众、游客、工作人员等在奥运会期间的购物需求，主要经营食品、奥运纪念品、旅游用品、文体用品和小日用品等。在比赛主场馆周边地区设置的这种,MS,，在地点、大小类型和总量方面有三个基本要求：满足,奥运会期间的购物需求、分布基本均衡和商业上赢利,。,2004,年,A,题,奥运会临时超市网点设计,14,.,鸟 巢,国家体育馆,水立方,15,.,16,.,请你按以下步骤对图,2,的,20,个商区设计,MS,网点：,1,）根据附录中给出的问卷调查数据，找出观众在出行、用餐和购物等方面所反映的规律。,2,）假定奥运会期间（指某一天）每位观众平均出行两次，一次为进出场馆，一次为餐饮，并且出行均采取最短路径。依据,1,的结果，测算图,2,中,20,个商区的人流量分布（用百分比表示）。,3,）如果有两种大小不同规模的,MS,类型供选择，给出图,220,个商区内,MS,网点的设计方案（即每个商区内不同类型,MS,的个数），以满足上述三个基本要求。,4,）阐明你的方法的科学性，并说明你的结果是贴近实际的。,17,.,例,1,最短路问题,（,SPP,shortest path problem,）,一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？,例,2,公路连接问题,某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。,18,.,例,3,指派问题,（,assignment problem,）,一家公司经理准备安排,n,名员工去完成,n,项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？,例,4,中国邮递员问题,（,CPP,chinese postman problem,）,一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？,由于这一问题是我国管梅谷教授,1960,年首先提出的，所以国际上称之为中国邮递员问题。,（匹配问题）,19,.例,5,旅行商问题,（,TSP,traveling salesman problem,）,一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商,(,推销员）问题。,例,6,运输问题,（,transportation problem,）,某种原材料有,M,个产地，现在需要将原材料从产地运往,N,个使用这些原材料的工厂。假定,M,个产地的产量和,N,家工厂的需求量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？,20,.,上述问题有两个共同的特点,：,一，其目的都是从若干可能的安排或方案中寻求某种意义下的,最优安排或方案,，数学上把这种问题称为,最优化或优化,（,optimization,）,问题,；,二，都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为,网络,（,network,）。,与图和网络相关的最优化问题就是,网络最优化或称网络优化,（,network optimization,）问题。,由于多数网络优化问题是以网络上的流（,flow,）为研究的对象，因此网络优化又常常被称为网络流（,network flows,）或网络流规划等。,21,.,故事的背景是十八世纪的东普鲁士，美丽的,Pregel,河穿过哥尼斯堡；人们在河的两岸及河中两个小岛间建立了七座桥，将它们连结成一个风景优美的公园。有一天，有人突发奇想：如何才能走遍七座桥，而每座桥都只能经过一次，最后又回到原先的出发点？,22,.,例,1,七桥问题,18,世纪东普鲁士哥尼斯堡被普列格尔河分为四块，它们通过七座桥相互连接起来，问能否从某块陆地出发，经每座桥一次而且仅一次，回到出发点？,A,C,B,D,A,B,C,D,任何一个点作为出发点,都必须先“出”后“回”，才能,行遍与该点相连的桥。,行遍性问题,23,.,对此问题，欧拉给出了一个通用,判定规则,：,从图的某一个顶点出发，经过每条线正好一次，最后回到原来的顶点，当且仅当这个图连成一片且每个顶点都有,偶数条线,和它连接。,思考：,能否将图的每一条线走遍，但只走一次。,（不必回到原顶点）,从图的某一个顶点出发，经过每条线正好一次，当且仅当这个图连成一片且,最多只有两个顶点是奇次的，且必须从某奇次点出发，到另一奇次点结束。,A,B,C,D,24,.,以下网络中哪一个是可以遍历的,(,即一笔而不重复地画成,),？,25,.,26,.,一笔画问题,欧拉注意到：一个奇顶点在这种遍历式的旅行中，要么是起点，要么是终点由于一个遍历的网络只能有一个起点和一个终点，因而这种网络的,奇点数不能多于两个,27,.,例,2,人、狼、羊、菜渡河问题,一个摆渡人,F,希望用一条小船把一只狼,W,、一头羊,G,和一篮白菜,C,从一条河的左岸渡到右岸去，而船小只能容纳,F,、,W,、,G,、,C,中的两个，决不能在无人看守情况下，留下狼和羊在一起，羊和白菜在一起，问应怎样渡河才能将狼、羊、白菜都运过去？,用小圆圈（顶点）表示河岸左边的各个状态，,两点连线当且仅当两状态可在规定允许下转移,。,FWGC,FWG,FWC,FGC,FG,WC,W,G,C,0,0,FWGC,WC,FWC,C,W,FGC,FWG,G,FG,28,.,一个人带三只狼和三只羊过河，一条船可容两只动物，没人在时，如果狼的数量不少于羊的数量就会吃掉羊，如何安全渡河,?,29,.,有一天，一家人（爸爸、妈妈、,2,个女儿、,2,个儿子和警察、小偷，想过河，船上只能装两个人，爸爸、妈妈、警察三人会划船，在过河的时候，爸爸不在的时候，妈妈会打儿子，妈妈不在的时候，爸爸会打女儿。警察不在的时候，小偷会打一家人。怎样才能使他们安全的过河？,30,.,例,3,化学药品存放问题,某公司生产几种化学药品,a,b,c,d,e,f,g,，其中某些化学药品不相容，为安全，公司要把相容的药品放在不同格中，问至少应将仓库划分为多少格？,我们可以用顶点表示各个化学药品，两顶点连线当且仅当两药品不相容，便可得一个图,G:,a,d,c,b,e,f,g,图,G,的点色数便是所求的最少格数,为每个顶点赋一色，使凡有连线的两顶点异色，点色数即是使图得到正常点上色的最少色数。,图的正常点上色,31,.,地图着色问题（四色问题）,：,任何一张地图只用,四,种颜色就能使具有共同边界的国家着上不同的颜色。,1,1,1,2,2,3,3,4,4,用数学语言表示，即,“,将平面任意地细分为不相重迭的区域，每一个区域总可以用,1,，,2,，,3,，,4,这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。,”,32,.,33,.,世界近代三大数学难题：,1.,费尔马大定理,（,1637,年）,在阅读丢番图,算术,拉丁文译本时，曾在第,11,卷第,8,命题旁写道：将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。,关于此，我确信已发现了一种美妙的证法，可惜这里空白的地方太小，写不下,。,经过三个半世纪的努力，这个世纪数论难题才由普林斯顿大学英国数学家安德鲁,怀尔斯和他的学生理查,泰勒于,1995,年成功证明。,34,.,3.,哥德巴赫猜想（,1742,年,6,月,7,日，德国数学家在写给著名数学家欧拉的一封信中提出）：,2.,四色问题,1,）任何不小于,6,的偶数，都是两个奇质数之和；,2,）任何不小于,9,的奇数，都是三个奇质数之和。,世界近代三大数学难题：,任何一张地图只用,四,种颜色就能使具有共同边界的国家着上不同的颜色。,35,.,路线着色问题,一个人来到他从未造访过的小镇上，驾着车到处寻找他朋友的家，即使连路名都没有。朋友说，别担心，他会指示他如何到达，先向左，再向右，接着向左,”,这个难题的假设是，在出发点（圆点）及道路（直线）的数量都固定的情况下，应该有办法以不同颜色标示道路，让人不管从哪一个点出发，都能到达固定的点。这在真实生活中的情况就像是，不管朋友住在哪里，只要知道你家的位置，绕再远都有办法到你家。,以图为范本，如果按照,蓝,红,红,蓝,红,红,蓝,红,红,.,的方式行走，不管从哪个点出发都能到黄色的点；如果是,蓝,蓝,红,蓝,蓝,红,蓝,蓝,红,.,则一定能到绿点,（万能地图）,36,.,图,：是指某类具体事物和这些事物之间的联系,如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个,“,图,”,的几何形象。,图与网络是运筹学（,Operations Research,）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。,最短路问题、行遍性问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。,37,.,38,.,例,1,线性方程组,的解取决于：,系数,常数项,复习：,矩阵,对线性方程组的,研究可转化为对,这张表的研究,.,线性方程组的系数与常数项按原位置可排为,39,.,例,2,对随机抽取的,1000,人按性别（男或女）及色觉（正常或色盲）两个属性分类，得到二行二列的列联表,:,40,.,行,列,由 个数,排成的 行 列的数表,定义：,称为 行 列矩阵,.,简称 矩阵,.,简记为,这 个数称为 的元素，简称为元,.,41,.,几种特殊矩阵,1.,方阵,(Square Matrix):,例如：,是一个,3,阶方阵,.,行数与列数都等于 的矩阵，,也可记作,注 意,2,、矩阵的行数和列数可以不等,1,、矩阵是一张数表,42,.,2.,行矩阵,(Row Matrix),(,或行向量,),:,3.,列矩阵,(Column Matrix),(,或列向量,):,只有一行的矩阵,只有一列的矩阵,43,.,形如 的方阵,4.,对角矩阵,(Diagonal Matrix):,记作,元素不全为,0,主对角线,5.,单位矩阵,(Identity Matrix):,主对角线上元素全为,1,其他元素都是,0,的方阵,44,.,6.,零矩阵,(Zero Matrix):,注意,不同阶数的零矩阵是不相等的,.,例如：,元素全为零的矩阵称为零矩阵，零,矩阵记作 或,.,?,45,.,矩阵的基本运算,1.,矩阵相等,矩阵相等,:,例,同型,矩阵：两个矩阵的行数相等、列数也相等,46,.,设有两个 矩阵 那么矩阵,与 的和记作 ，规定为,2.,矩阵的加减法,加法,：,47,.,例,说明,只有当两个矩阵是同型矩阵时，才能进,行加法运算,.,48,.,减法,:,负矩阵,：,49,.,矩阵加法满足的,运算规律,:,50,.,3.,数与矩阵相乘,数乘,:,51,.,数乘矩阵的,运算规律：,（设 为 矩阵，为数）,矩阵相加与数乘矩阵合起来,统称为矩阵的,线性运算,.,52,.,并把此乘积记作,设 是一个 矩阵，是一个,矩阵，那么规定矩阵 与矩阵 的乘积,是一个 矩阵 ，其中,4,、矩阵与矩阵相乘,53,.,设,例,解,求,54,.,注意只有当,第一个矩阵的列数,等于,第二个矩阵,的行数,时，两个矩阵才能相乘,.,例如,不存在,.,55,.,矩阵乘法的,运算规律,（其中 为数）,;,若,A,是 阶矩阵则 为,A,的 次幂，即,并且,满足,结合律、分配率,56,.,矩阵不满足交换律,例,设,则,（并非所有的矩阵都不满足交换律）,矩阵是否满足交换律？,57,.,矩阵乘法不满足消去律,矩阵乘法是否满足消去律？,例：,有,但是,58,.,输入矩阵的方法,(1),用中括号,把所有矩阵元素括起来；,(2),同一行的不同元素之间用空格或逗号间隔；,(3),用分号,(;),指定一行结束；,(4),也可以分成几行进行输入，用回车符代替分号；,(5),数据元素可以是表达式，系统将自动计算结果；,59,.,例：输入矩阵,matlab,输入格式：,ans=,-3 9 -1,1 3 7,ans=,3,60,.,61,.,特殊矩阵函数,函数,描述,举例,空矩阵,A(:,2)=,%,删除矩阵,A,的第,2,列,eye,单位矩阵,A=eye(3),ones,元素全部为,1,的矩阵,A=ones(2,3),%A,为,23,元素全为,1,的矩阵,zeros,元素全部为,0,的矩阵,A=zeros(2,3),%A,为,23,元素全为,0,的矩阵,rand,元素值为,0,到,1,之间均匀分布的随机矩阵,A=rand(3),62,.,函数,描述,举例,randn,元素值服从均值为,0,方差为,1,的正态分布的随机矩阵,A=randn(4),triu,求给定矩阵的上三角阵,B=triu(A),tril,求给定矩阵的下三角阵,B=tril(A),63,.,矩阵的基本运算,运算,功能,命令形式,矩阵,加法和减法,将两个同型矩阵相加,(,减,),AB,数乘,将数与矩阵做乘法,k*A,k,是一个数,A,是一个矩阵,矩阵,乘法,将两个矩阵进行矩阵相乘,A*B,A,的列数与,B,的行数相等,矩阵的,左除,计算,AB,A,必须为方阵,矩阵的,右除,计算,A/B,B,必须为方阵,求矩阵,行列式,计算方阵的行列式,det(A),A,必须为方阵,64,.,矩阵的基本运算,运算,功能,命令形式,求矩阵的,逆,求方阵的逆,Inv(A),或,矩阵,乘幂,计算,A,n,A,n,A,必须为方阵,n,是正整数,矩阵的,转置,求矩阵的转置,Transpose(A),或,A,矩阵,求秩,求矩阵的秩,rank(A),矩阵,行变换化简,求,A,阶梯形的行最简形式,rref(A),65,.,66,.,一、图与网络的基本概念,是由一个非空有限集合 和 中某些元素的,无序对,集合 构成的二元组，记为 。,顶点集或节点集,边集,Vertex,，,edge,67,.,完备图,若,表示 集合中的元素个数），中无相邻顶点对，中亦然，则称 为,二分图,；特别地，若,则 ，则称 为,完全二分图,，记成 。,68,.,简而言之，就是顶点集,V,可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集。,图中,(a),(b),为二分图，,(c),为完全二分图,K,3,3,69,.,70,.,树,71,.,最小生成树：,72,.,73,.,二、图与网络的数据结构,74,.,75,.,76,.,（每边有两个顶点与其相关联）,77,.,78,.,79,.,1 5 3 4 6 7,80,.,三、最短距离问题,在生产管理、交通运输和通讯领域，经常会碰到这样的问题：沿着哪条路线可以最短的时间或最少的费用把货物运往目的地？沿着哪条路线传送信息最可靠或最快捷？如何组织生产可使生产成本最低？如何制定投资计划可使利润最大？这些都可看成是在给定的加权图中，求最短路径问题。,81,.,82,.,83,.,邻接矩阵,84,.,85,.,86,87,.,88,.,89,.,90,.,91,.,92,.,93,.,2,v,1,v,3,v,4,v,5,v,65,70,80,50,20,3,100,30,94,.,95,.,96,.,97,.,2,v,1,v,3,v,4,v,5,v,65,70,80,50,20,3,100,30,98,.,例 某公司在六个城市中有分公司，从到的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市到其它城市间的票价最便宜的路线图。,99,.,行 遍 性 问 题,100,.,一、中 国 邮 递 员 问 题,二、推 销 员 问 题,（一）欧 拉 图,（二）中 国 邮 递 员 问 题一）哈 密 尔 顿 图,（二）推 销 员 问 题,101,.,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,6,欧 拉 图,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,巡回：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,e,5,v,1,欧拉道路：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,欧拉巡回：,v,1,e,1,v,2,e,2,v,3,e,5,v,1,e,4,v,4,e,3,v,3,e,6,v,1,102,.,e,3,v,1,v,2,v,3v,4,e,1,e,2,e,4,e,5,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,e,6,欧拉图,非欧拉图,推论,1,设,G,是非平凡连通图，则,G,有欧拉道路的充要条件是,G,最多有两个奇次顶点,.,该推论为判别图形能否一笔画给出了依据,103,.,中国邮递员问题,-,定义,邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线。这就是,中国邮递员问题,。,若将,投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图,.,中国邮递员问题转化为：,在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为,最佳巡回,（管梅谷,1962,年）,一笔画问题,104,.,V,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,V,5,V,6,e,6,e,7,e,8,e,9,割边,割边的定义,：设,G,连通，,e E(G),若从,G,中删除边,e,后，图,G-e,不连通，则称边,e,为图,G,的割边,G,的边,e,为,割边,e,不含在,G,的圈中,圈,：起点与终点重合的,路径,顶点、边均不重复的通路,105,.,中国邮递员问题,-,算法,Fleury,算法,-,基本思想,：,从任一点出发，每当访问,一条边时，先要进行检查如果可供访问的边不只,一条，则应选一条不是未访问的边集的导出子图的,割边,作为访问边，直到没有边可选择为止,.,此时,G,的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回,1.G,是欧拉图,106,.,V,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,V,5,V,6,e,6,e,7,e,8,e,9,e,10,107,.,若,G,不是欧拉图，则,G,的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是，在一些点对之间,引入重复边（重复边与它平行的边具有相同的权），,使原图成为欧拉图，但希望所有添加的重复边的,权的总和为最小,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,2.G,不是欧拉图,108,.,V,7,e,3,v,1,v,2,v,3,v,4,e,1,e,2,e,4,e,5,V,5,V,6,e,6,e,7,e,8,e,9,109,.,先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边得欧拉图,G*,，,G*,的欧拉巡回便是原图的最佳巡回,基本思想,：,110,.,（,3,）求出,G1,的,最小权理想匹配,M,，得到奇次顶点的最佳配对,（,2,）以,G,的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图,G,中的最短距离，将此完备加权图记为,G,1111,.,定义,：设,M,是,G,的一个匹配，,（,1,）若,M,渗透了,G,的每个顶点，则称,M,是,G,的理想匹配,（,2,）若,M,是,G,中含边最多的匹配，则称,M,为,G,的最大匹配,显然理想匹配是最大匹配，,但最大匹配不一定是理想匹配,理想匹配可能有多个，权最小的为最小权理想匹配。,112,.,113,.,中国邮递员问题的应用与推广：,1.,铲雪车的行使路线问题：马里兰州维克米城被大雪覆盖，有两辆铲雪车清除积雪。如何安排行使路线，使得两辆车同时完成任务。,2.,容量约束中国邮递员问题：城市环保局每天要派出洒水车为城市街道洒水。由于洒水车的容量有限，中途需要返回加水，若已知每英里道路需要的水量以及洒水车的容量，问如何安排车的行使路线使总行程最短？,又如：城市垃圾收集、流动餐车、道路洒盐,.,114,.,哈 密 尔 顿 图,1859,年，数学家哈密尔顿发明了一种周游世界的游戏：在一个,12,面体的每个角点代表一个城市，问能否从某城市出发，沿,12,面体的棱行走，经过每个城市一且仅一次，最后回到出发地。,用图论的语言来讲，就是在,12,面体图上找出生成圈。,115,.,哈 密 尔 顿 图,116,.,推销员问题,-,定义,流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题,若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为,在加权图中寻找一条经过每个顶点至少一次的最短闭通路,问题,117,.,定义在加权图,G=(V,E),中，,（）权最小的哈密尔顿圈称为,最佳,H,圈,（）经过每个顶点至少一次的权最小的闭通路称为,最佳推销员回路,一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈,H,回路，长,22,最佳推销员回路，长,4,118,.,119,.,推销员问题近似算法：,二边逐次修正法,：,120,.,例,对以下完备图，用二边逐次修正法求较优,H,圈,121,.,122,.,练习,从北京（,Pe,）乘飞机到东京,(T),、纽约,(N)墨西哥城,(M),、伦敦,(L),、巴黎,(Pa),五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：,L,M,N,Pa,Pe,T,L,56,35,21,51,60,M,56,21,57,78,70,N,35,21,36,68,68,Pa,21,57,36,51,61,Pe,51,78,68,51,13,T,60,70,68,61,13,123,.,例考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。,证明：,设,G,是具有七个顶点的图，每个顶点对应于一门课程考试，如果这两个顶点对应的课程考试是由不同教师担任的，那么这两个顶点点之间有一条边，因为每个教师所担任课程数不超过,4,，故每个顶点的度数至少是,3,，任两个顶点的度数之和至少是,6,，故,G,总是包含一条哈密尔顿路，它对应于一个七门考试课目的一个适当的安排。,124,.,