学校数模培训课件宁万涛-数学建模.ppt

图论与数学建模,西安电子科技大学数学与统计学院 宁万涛 wtning@,1 引言,图论起源于18世纪.瑞士数学家欧拉在1736年发表了第一篇关于“哥尼斯堡七桥问题”的图论论文. 主要成就:提出函数的概念 创立分析力学 给出欧拉公式 解决了哥尼斯堡七桥问题,在哥尼斯堡有七座桥将河中的两个岛及岛与河岸连结起来.问题是能否从这四块陆地中的任何一块出发,通过每座桥恰好一次,最后回到出发点?,当然可以通过试验去尝试解决这个问题,但该城居民的任何尝试均未成功.,欧拉给出了一个判定法则:这个图是连通的,且每个点都与偶数条边相关联.因此,得到了“不可能走通”的结果,不但彻底解决了这个问题,而且开创了图论研究的先河.,图论中所谓的“图”是指某类具体事物和这些事物之 间的联系,如果我们用点表示这些具体事物,用连接 两点的线段(直的或曲的)表示两个事物的某种联系, 就得到了描述这个“图”的几何形象.,图论为一个包含了一种二元关系的离散系统提供了 一个数学模型,借助于图论的概念、理论和方法,可 以对该模型求解.,我们先通过一些例子来了解图论优化问题. 例1 最短路问题(SPP－shortest path problem) 一名货车司机想要在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地有多种行车路线,这名司机应选择哪条线路呢?假设货车的运行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路.,例2 公路连接问题 某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来.假定已经知道了任意两个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总成本最小?,例3 中国邮递员问题(CPP) 一名邮递员负责投递某个街区的邮件. 如何为他设计一条最短的投递路线 (从邮局出发,经过投区内每条街道 至少一次,最后返回邮局)?由于这一 问题是我国管梅谷教授1960年首先 提出的,所以国际上称之为中国邮 递员问题.,上述问题有两个共同的特点: 它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案,数学上把这种问题称为优化问题.,它们都易于用图形直观地描述和表达,数学上把这种与图相关的结构称为网络.与图和网络相关的优化问题就称为网络优化问题.,2 图与网络的基本概念和问题,常用术语,1) 边和它的两端点称为互相关联.,2)与同一条边关联的两个端点称为相 邻的顶点.,3) 端点重合为一点的边称为环.,4) 若一对顶点之间有两条以上的边联结,则这些边,称为重边．,5) 既没有环也没有重边的图,称为简单图．,,,例 在右图中：,途径：,迹：,路：,,,,,,,,,,例、证明：对任意6个人,总有3人互相认识,或总有3人互相不认识.,证明：以顶点表示人,红边表示认识,黑边表示不认识.,1,1至少与其它顶点中的三个之间连红边(认识)或者连黑边(不认识).不妨设1与2，3，4之间连红边.,目标:找到红色的三角形或者黑色的三角形.,,,,,,,,,,,,,2,3,4,5,6,2如果与3或者4之间连红边,则结论成立.,1,设2与3和4之间连黑边,则不论3,4之间连什么边,结论都成立.,目标:找到红色的三角形或者黑色的三角形.,3 图与网络的数据结构,这里我们介绍计算机上用来描述图与网络的4种常用表示方法:邻接矩阵表示法、关联矩阵表示法、邻接表表示法和星形表示法.,,,(1) 邻接矩阵表示法,邻接矩阵表示法是将图以邻接矩阵的形式存储在计算机中.图 的邻接矩阵C是如下定义的：C是一 的0-1矩阵,即 也就是说,如果两顶点之间有一条弧,则邻接矩阵中对应的元素为1;否则为0.,,,,对于赋权图,也可以用类似邻接矩阵的矩阵表示.只是此时一条弧所对应的元素不再是1,而是相应的权而已.,例1 对于所示的图,可以用邻接矩阵表示为,(2) 关联矩阵表示法,关联矩阵表示法是将图以关联矩阵的形式存储在计算机中.图 的关联矩阵B是如下定义的：B是一个 的矩阵,即,,,,如果一个顶点是一条弧的起点,则关联矩阵中对应的元素为1;如果一个顶点是一条弧的终点,则关联矩阵中对应的元素为-1;如果一个顶点与一条弧不关联,则关联矩阵中对应的元素为0.,例2 对于例1所示的图,如果关联矩阵中每列对应弧的顺序 为(1,2),(1,3),(2,4),(3,2),(4,3),(4,5),(5,3)和(5,4),则关联矩阵表示为(列单位为弧).,(3) 邻接表表示法,邻接表表示法将图以邻接表的形式存储在计算机 中.邻接表表示法就是对图的每个顶点,用一个单向 链表列出从该顶点出发的所有弧,链表中每个单元对 应于一条出弧.为了记录弧上的权,链表中每个单元 除列出弧的另一个端点外,还可以包含弧上的权等作 为数据域.图的整个邻接表可以用一个指针数组表示.,,,,(4) 星形表示法,星形表示法的思想与邻接表表示法的思想有一定的相似之 处.对每个顶点,它也是记录从该顶点出发的所有弧,但它 不是采用单向链表而是采用一个单一的数组表示.,4 最短路问题,例,0,,,,,,,8,15,10,,12,15,,11,,31,13,,,,选址问题--中心问题,思考： 某人带着狼、羊以及蔬菜渡河,一小船除需人划 外,每次只能载一物过河.而人不在场时,狼要吃羊, 羊要吃菜,问此人应该如何渡河.请用最短路求解.,5 完全图、二部图,n支球队循环比赛.,每场比赛只计胜负,没有平局.,要求：根据比赛结果排出各队名次.,,完全图应用：竞赛图法求球队排名问题,竞赛图: 完全图的定向图.,方法1：顺箭头方向寻找通过全部顶点的一条路.,,,,,,,,312456,146325,方法2: 计算得分: 1队胜4场,2,3队各胜3场. 4,5队各胜2场, 6队胜1场.,2, 3队, 4, 5队无法排名,6支球队比赛结果,……,32，45,例,3个顶点的竞赛图,名次,{1，2，3},{(1,2,3)}并列,{1, 2, 3, 4},{2,(1,3,4)},{(1,3,4), 2},4个顶点的竞赛图,{1, 2, 3, 4}?,竞赛图的3种形式,具有唯一的完全路径, 如(1).,双向连通图——任一对顶点存在两条有向路径相互连通, 如(4)；,其他, 如(2),(3) .,竞赛图的性质,必存在完全路径.,若存在唯一的完全路径,则由它确定的顶点顺 序与按得分排列的顺序一致,如(1) .,双向连通竞赛图G=(V,E)的名次排序,邻接矩阵,排名为{1, 2, 4, 3},,{1, 2, 3, 4}?,,一般竞赛图排名问题的算法：,,当竞赛图既没有唯一完全路径,又不是双向连通图时,通常可以将它分解为若干个双向连通的子竞赛图(只有一个顶点的图可视为双向连通竞赛图的特例).,每个双向连通子竞赛图内的名次按前述方法排名.,双向连通子竞赛图间的名次则由连接它们的边的方向决定.,6 树,,最小生成树算法,图G的所有生成树中权最小的生成树称为图G的最小生成树.,,应用：现需从自来水厂接自来水管道到各个城镇,自来水厂到各城镇之间铺设自来水管道价格如下,问如何铺设最经济.,7 Euler图和Hamilton图,,该算法是尽可能避割边行走.,(1)、 任意选择一个顶点v0, 置w0=v0;,(2)、 假设迹wi=v0e1v1…eivi已经选定, 那么按 下述方法从E-｛e1,e2,…,ei｝中选取边ei+1:,1)、 ei+1与vi+1相关联；,2)、除非没有别的边可选择,否则 ei+1不能是,Gi=G-｛e1,e2,…,ei｝的割边.,(3)、 当(2)不能执行时, 算法停止.,在下面欧拉图G中求一条欧拉回路.,,,,,,,,,,,,,,,,,,中国邮递员问题,定理： 若W是图G中一条包含所有边的闭途径,则W在这样的闭途径中具有最短的长度当且仅当下列两个条件被满足：,(1) 每一条边最多重复经过一次；,(2) 在G的每一个圈上,重复经过的边的条数不超过圈长 的一半.,中国邮递员问题求解法(非赋权图)：,解：由定理,,,,,,,,求包含下图G的一个最优欧拉环游.,修改后得:,中国邮递员问题求解法（赋权图）：,哈密尔顿问题(环球旅行游戏),图G中包含每个顶点的圈称为哈密尔顿圈(H-圈).,十二面体的20个顶点代表世界上20个城市,能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,,,,,,,,,例 对下图的K6, 用二边逐次修正法求较优H圈.,较优H圈:,其权为W(C3)=192,,98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”,今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自,救,县领导决定,带领有关部门负责人到全县各乡（镇）、,村巡视. 巡视路线指从县政府所在地出发,走遍各乡,（镇）、村,又回到县政府所在地的路线.,中的前两个问题是这样的：,1）若分三组（路）巡视,试设计总路程最短且各组尽可 能均衡的巡视路线.,2）假定巡视人员在各乡（镇）停留时间T=2 小时, 在各村,停留时间t=1小时, 汽车行驶速度V =35公里/小时. 要在 24小时内完成巡视，至少应分几组；给出这种分组下 最佳的巡视路线.,公路边的数字为该路段的公里数.,问题分析：,本题给出了某县的公路网络图,要求的是在不同的条件下,灾情巡视的最佳分组方案和路线.,将每个乡（镇）或村看作一个图的顶点,各乡镇、村之间 的公路看作此图对应顶点间的边,各条公路的长度（或行驶时 间）看作对应边上的权,所给公路网就转化为加权网络图,问题 就转化图论中的旅行商问题,即在给定的加权网络图中寻找从 给定点O出发,行遍所有顶点至少一次再回到点O,使得总权（路 程或时间）最小.,如第一问是三个旅行商问题,第二问是四个旅行商问题.,本题是旅行商问题的延伸,－多旅行商问题.,本题所求的分组巡视的最佳路线,也就是m条经过同一点并,众所周知,旅行商问题属于NP完全问题,即求解没有多 项式时间算法.,显然本问题更应属于NP完全问题. 一定要针,覆盖所有其他顶点又使边权之和达到最小的闭迹.,对问题的实际特点寻找简便方法,想找到解决此类问题的一,般方法是不现实的,对于规模较大的问题可使用近似算法求解,作业: 1、2 必做，3 抽查,要求:用最短路算法解决该问题,并编程求解.,3 学习：对图论中的算法用例子及程序实现.,2 求解PPT31页的思考题.,谢谢大家,。