基于图论的数学建模课件

1、数学建模理论与实践 基于图论的数学建模1基于图论的数学建模一、欧拉环游问题与中国邮递员问题二、最小生成树模型三、最短路模型2一、欧拉环游问题与中国邮递员问题（一）图的概念（二）欧拉环游及弗莱里算法（三）中国邮递员问题3（一）图的概念问题的提出： 现实生活中，我们经常碰到一些现象，如：在一群人中有些人互相认识，有些人互相不认识。又如：某航空公司在100个城市之间建立若干航线，某些城市间有直达航班，而另一些城市间没有直达航班等等。以上现象都有共同内容：一是有研究的“对象”，如人，城市等；二是这些对象之间存在着某种关系：如互相认识，有直达航班等。为了表示这些对象以及对象之间的关系，我们将“点”代表“

2、对象”，“边”表示“对象之间的关系”，引出了“图”这个概念。4几个基本概念：图：由若干个不同的点与连接其中某些顶点的边所组成的图形，称为图 图有二要素：“点”和“边”：“点”表示对象，“边”反映对象之间的关系。 （一）图的概念5环游与欧拉环游：（一）图的概念7七桥问题：（二）欧拉环游及弗莱里算法 流经哥尼斯堡的普雷格河的河湾有两个小岛，七座桥连接了两岸和小岛（如图1），当地流传一个游戏：要求在一次散步中恰好通过每座桥一次。8存在欧拉环游的条件：（二）欧拉环游及弗莱里算法一个图存在欧拉环游的条件是：网络有欧拉环游当且仅当中每一点的次为偶数。 一般地，一个图能“一笔画”（不要求回到起点），当且仅当

3、该图或没有奇点，或只有2个奇点。 利用上述结论，我们判定“七桥问题”不能实现“一笔画”，因为七桥问题中的图有4个奇点。 但是要注意，一个图存在欧拉环游，如果方法不对，仍然可能找不到具体的欧拉环游。 10弗莱里算法：（二）欧拉环游及弗莱里算法11弗莱里算法求欧拉环游的实例：（二）欧拉环游及弗莱里算法A()BA()BAA()BACA()BACDA()BACDEA()BACDECA()BACDECBE()DA以A为起点12奇偶点图上作业法：（ 三）中国邮递员问题奇偶点图上作业法口诀：先分奇偶点，奇点对对连；连线不重迭，重迭需改变；圈上连线长，不得过半圈。 14奇偶点图上作业法实例：（ 三）中国邮递员

4、问题再利用弗莱里算法求得的欧拉环游即最优环游。此投递路线的总长度为：71+54+47+26+15=72。15（一）森、树、生成树等有关概念问题的提出：17（一）森、树、生成树等有关概念 一个图的生成树可能不只一个，例如右面的一个图：它有许多生成树，例如下面每个树都是它的生成树：18（二）树的性质19（三）求最小生成树的三种算法算法一 (克鲁斯凯尔，Kruskal)算法二 (普赖姆，Prim)算法三 (破圈法)20算法一 (克鲁斯凯尔，Kruskal)算法一(克鲁斯凯尔，Kruskal)的中心思想是每次添加权尽可能小的边，使新的图无圈，直至得到生成树为止。该方法形象地简称为“最小边加入法”。 21算法一 (克鲁斯凯尔，Kruskal)e1e2=e3=e4e5e6=e7v4-v3-v5-v6-v7，最短路的长度为1334教材 P106-107 第 1、2、3 、4 题要求：1） 第 4 题主要用程序方法求