基于图论的数学建模名师优质课获奖市赛课一等奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。,数学建模理论与实践,基于图论数学建模,第1页,1,基于图论数学建模,一、欧拉周游问题与中国邮递员问题,二、最小生成树模型,三、最短路模型,第2页,2,一、欧拉周游问题与中国邮递员问题,（一）图概念,（二）欧拉周游及弗莱里算法,（三）中国邮递员问题,第3页,3,（一）图概念,问题提出：,现实生活中，我们经常碰到一些现象，如：在一群人中有些人相互认识，有些人相互不认识。又如：某航空企业在,100,个城市之间建立若干航线，一些城市间有直达航班，而另一些城市间没有直达航班等等。以上现象都有共同内容：一是有研究“,对象,”，如人，城市等；二是这些对象之间存在着某种,关系,：如相互认识，有直达航班等。为了表示这些对象以及对象之间关系，我们将“点”代表“对象”，“边”表示“对象之间关系”，引出了“,图,”这个概念。,第4页,4,几个基本概念：,图,：由若干个不一样点与连接其中一些顶点边所组成图形，称为图,图有二要素：,“,点,”,和,“,边,”,：,“,点,”,表示对象，,“,边,”,反应对象之间关系。,（一）图概念,第5页,5,深入概念：,（一）图概念,第6页,6,周游与欧拉周游：,（一）图概念,第7页,7,七桥问题：,（二）欧拉周游及弗莱里算法,流经哥尼斯堡普雷格河河湾有两个小岛，七座桥连接了两岸和小岛（如图,1,），当地流传一个游戏：要求在一次散步中恰好经过每座桥一次。,第8页,8,七桥问题：,（二）欧拉周游及弗莱里算法,在这个问题中，我们能够将“两个小岛和两岸”看成“点”。连接他们之间“七座桥”看成“边”，得到图,2,。,“七桥问题”能够归结为“一笔画”问题：即能否用一支笔不离开纸面地画出经过全部桥一次路线。用图论术语，就是一个图是否存在欧拉周游？假如有，怎样找出来？,第9页,9,存在欧拉周游条件：,（二）欧拉周游及弗莱里算法,一个图存在欧拉周游条件是：网络有欧拉周游当且仅当中每一点次为偶数。,普通地，一个图能“一笔画”（不要求回到起点），当且仅当该图或没有奇点，或只有,2,个奇点。,利用上述结论，我们判定“七桥问题”不能实现“一笔画”，因为七桥问题中图有,4,个奇点。,不过要注意，一个图存在欧拉周游，假如方法不对，依然可能找不到详细欧拉周游。,第10页,10,弗莱里算法：,（二）欧拉周游及弗莱里算法,第11页,11,弗莱里算法求欧拉周游实例：,（二）欧拉周游及弗莱里算法,A()B,A()BA,A()BAC,A()BACD,A()BACDE,A()BACDEC,A()BACDECBE()DA,以,A,为起点,第12页,12,问题提出：,（三）中国邮递员问题,邮递员从邮局中取出邮件，递送到不一样地点，然后再返回邮局。假设要求他最少一次走过他投递范围内每一条街道，我们希望选择一条尽可能短路线。,中国邮递员问题要求是在含有非负权网络中找出一条权最小周游，即最优周游。,假如网络存在欧拉周游，我们能够按照上面弗莱里算法求得其欧拉周游。对于一个没有欧拉周游网络，能够经过添重复边方法使得添加重复边后网络含有欧拉周游。这里关键问题是要求所添加重复边权和尽可能地小。,问题解法：,点数较多时，可用,Edmonds,和,Johnson,算法（这一算法较为复杂，这里不作介绍）；,点数较少时，可用,奇偶点图上作业法,求解。,第13页,13,奇偶点图上作业法：,（三）中国邮递员问题,奇偶点图上作业法,口诀：,先分奇偶点，奇点对对连；,连线不重迭，重迭需改变；,圈上连线长，不得过半圈。,第14页,14,奇偶点图上作业法实例：,（三）中国邮递员问题,再利用弗莱里算法求得欧拉周游即最优周游。,此投递路线总长度为：,71+54+47+26+15=72,。,第15页,15,二、最小生成树模型,（一）森、树、生成树等相关概念,（二）树性质,（三）求最小生成树三种算法,第16页,16,（一）森、树、生成树等相关概念,问题提出：,第17页,17,（一）森、树、生成树等相关概念,一个图生成树可能不只一个，比如右面一个图：,它有许多生成树，例以下面每个树都是它生成树：,第18页,18,（二）树性质,第19页,19,（三）求最小生成树三种算法,算法一,(,克鲁斯凯尔，,Kruskal),算法二,(,普赖姆，,Prim),算法三,(,破圈法,),第20页,20,算法一,(,克鲁斯凯尔，,Kruskal),算法一,(,克鲁斯凯尔，,Kruskal),中心思想是每次添加权尽可能小边，使新图无圈，直至得到生成树为止。该方法形象地简称为“,最小边加入法,”。,第21页,21,算法一,(,克鲁斯凯尔，,Kruskal),e1e2=e3=e4e5e6=e7v4-v3-v5-v6-v7,，最短路长度为,13,第34页,34,教材,P106-107,第,1,、,2,、,3,、,4,题,要求：,1,）第,4,题主要用程序方法求解。若能够写出手工求解方法，则更佳；,2,）解答题，写出详细解法；,3,）程序设计题，写出用相关软件实现、而且是调试经过程序。,书面作业,第35页,35,