1 数学建模理论与实践 —— 基于图论的数学建模. 2 基于图论的数学建模 一、欧拉环游问题与中国邮递员问题 二、最小生成树模型 三、最短路模型.

Presentation on theme: "1 数学建模理论与实践 —— 基于图论的数学建模. 2 基于图论的数学建模 一、欧拉环游问题与中国邮递员问题 二、最小生成树模型 三、最短路模型."— Presentation transcript:

1 1 数学建模理论与实践 —— 基于图论的数学建模

2 2 基于图论的数学建模 一、欧拉环游问题与中国邮递员问题 二、最小生成树模型 三、最短路模型

3 3 一、欧拉环游问题与中国邮递员问题 （一）图的概念 （二）欧拉环游及弗莱里算法 （三）中国邮递员问题

4 4 （一）图的概念 问题的提出： 现实生活中，我们经常碰到一些现象，如：在一 群人中有些人互相认识，有些人互相不认识。又如： 某航空公司在 100 个城市之间建立若干航线，某些 城市间有直达航班，而另一些城市间没有直达航班 等等。以上现象都有共同内容：一是有研究的 “ 对 象 ” ，如人，城市等；二是这些对象之间存在着某种 关系：如互相认识，有直达航班等。为了表示这些 对象以及对象之间的关系，我们将 “ 点 ” 代表 “ 对象 ” ， “ 边 ” 表示 “ 对象之间的关系 ” ，引出了 “ 图 ” 这个概念。

5 5 几个基本概念： 图：由若干个不同的点与连接其中某些顶点的边所组成的图 形，称为图 图有二要素： “ 点 ” 和 “ 边 ” ： “ 点 ” 表示对象， “ 边 ” 反映对象之间的关系。 （一）图的概念

6 6 进一步的概念： （一）图的概念

7 7 环游与欧拉环游： （一）图的概念

8 8 七桥问题： （二）欧拉环游及弗莱里算法 流经哥尼斯堡的普雷格河的河湾有两个小岛，七座桥连接 了两岸和小岛（如图 1 ），当地流传一个游戏：要求在一次散 步中恰好通过每座桥一次。

9 9 七桥问题： （二）欧拉环游及弗莱里算法 在这个问题中，我们可以将 “ 两个小岛和两岸 ” 看成 “ 点 ” 。连 接他们之间的 “ 七座桥 ” 看成 “ 边 ” ，得到图 2 。 “ 七桥问题 ” 可以归结为 “ （回 到起点的）一笔画 ” 问题：即 能否用一支笔不离开纸面地 画出经过所有桥一次的路线。 用图论的术语，就是一个图 是否存在欧拉环游？如果有， 如何找出来？

10 10 存在欧拉环游的条件： （二）欧拉环游及弗莱里算法 一个图存在欧拉环游的条件是：网络有欧拉环游当且仅当中每 一点的次为偶数。 一般地，一个图能 “ 一笔画 ” （不要求回到起点），当且 仅当该图或没有奇点，或只有 2 个奇点。 利用上述结论，我们判定 “ 七桥问题 ” 不能实现 “ 一笔画 ” ， 因为七桥问题中的图有 4 个奇点。 但是要注意，一个图存在欧拉环游，如果方法不对， 仍然可能找不到具体的欧拉环游。

11 11 弗莱里算法： （二）欧拉环游及弗莱里算法

12 12 弗莱里算法求欧拉环游的实例： （二）欧拉环游及弗莱里算法 A(~)BA(~)BA A(~)BAC A(~)BACD A(~)BACDEA(~)BACDEC A(~)BACDECBE(~)DA 以 A 为起点 …

13 13 问题提出： （ 三）中国邮递员问题 邮递员从邮局中取出邮件，递送到不同地点，然后再返 回邮局。假设要求他至少一次走过他投递范围内的每一条街道， 我们希望选择一条尽可能短的路线。 中国邮递员问题要求的是在具有非负权的网络中找出一 条权最小的环游，即最优环游。 如果网络存在欧拉环游，我们可以按照上面的弗莱里算 法求得其欧拉环游。对于一个没有欧拉环游的网络，可以通过 添重复边的方法使得添加重复边后的网络具有欧拉环游。这里 的关键问题是要求所添加重复边的权的和尽可能地小。 问题解法： 点数较多时，可用 Edmonds 和 Johnson 算法（这一算法较 为复杂，这里不作介绍）； 点数较少时，可用奇偶点图上作业法求解。

14 14 奇偶点图上作业法： （ 三）中国邮递员问题 奇偶点图上作业法口诀： 先分奇偶点，奇点对对连； 连线不重迭，重迭需改变； 圈上连线长，不得过半圈。

15 15 奇偶点图上作业法实例： （ 三）中国邮递员问题 再利用弗莱里算法求得 的欧拉环游即最优环游。 此投递路线的总长度为： 7×1+5×4+4×7+2×6+1 ×5=72 。

16 16 二、最小生成树模型 （一）森、树、生成树等有关概念 （二）树的性质 （三）求最小生成树的三种算法

17 17 （一）森、树、生成树等有关概念 问题的提出：

18 18 （一）森、树、生成树等有关概念 一个图的生成树可能 不只一个，例如右面的 一个图： 它有许多生成树，例如下面每个树都是它的生成树：

19 19 （二）树的性质

20 20 （三）求最小生成树的三种算法 算法一 ( 克鲁斯凯尔， Kruskal) 算法二 ( 普赖姆， Prim) 算法三 ( 破圈法 )

21 21 算法一 ( 克鲁斯凯尔， Kruskal) 算法一 ( 克鲁斯凯尔， Kruskal) 的中心思想是每次添 加权尽可能小的边，使新的图无圈，直至得到生成树 为止。该方法形象地简称为 “ 最小边加入法 ” 。

22 22 算法一 ( 克鲁斯凯尔， Kruskal) e1<e2<=e3<=e4<e5<e6<=e7<=e8 从 e1,e2 开始加入 e3 ，不可， 则去掉 e3 保留 e4 、保留 e5 加入 e8 ，不可， 则去掉 e8 加入 e7 ，不可， 则去掉 e7 加入 e6 ，不可， 则去掉 e6 实例：

23 23 算法二 ( 普赖姆， Prim) 算法二 ( 普赖姆， Prim) 这是一种迭代算法，每进行一次 迭代将产生组成网络 N 最小生成树 T 的一条边。它是一 种 “ 蚕食性 ” 的算法，慢慢扩张自己的地盘。

24 24 算法二 ( 普赖姆， Prim) 实例：

25 25 算法三 ( 破圈法 ) 算法三 ( 破圈法 ) 就是在图中任意取一个圈， 从圈中去掉权最大的边，将这个圈破掉。 重复这个过程，直到图中没有圈为止，保 留下的边组成的图即为最小生成树。

26 26 算法三 ( 破圈法 )

27 27 三、最短路模型 （一）有向图及最短有向路 （二） Dijkstra 算法

28 28 （一）有向图及最短有向路 问题的提出：

29 29 （一）有向图及最短有向路

30 30 （一）有向图及最短有向路

31 31 （一）有向图及最短有向路

32 32 （二） Dijkstra 算法 Dijkstra （狄克斯特拉）算法是一种求 最短有向路的方法 限于时间，此方法的介绍省略。 下面补充一种用 0-1 规划的计算机方法求解 最短有向路

33 33 （二） Dijkstra 算法 求下图中从 v1 到 v7 的最短有向路 :

34 34 （二） Dijkstra 算法 ! 设每个有向路用 xij 来表示，其中 i 是起点编号、 j 是终点编号 ; ! xij 非 0 即 1 ：最短路经过此边时为 1 ；否则为 0, LINGO 程序如下 ; min=2*x12+5*x13+3*x14 +7*x26+2*x23 +5*x36+3*x35 +1*x43+5*x45 +1*x56+7*x57 +5*x67; x12+x13+x14=1; x67+x57=1; x12-x23-x26=0; x23+x13+x43-x35-x36=0; x14-x43-x45=0; x35+x45-x57-x56=0; x26+x36+x56-x67=0; @bin(x12);@bin(x13);@bin(x14);@bin(x26);@bin(x23);@bin(x36); @bin(x35);@bin(x43);@bin(x45);@bin(x56);@bin(x57);@bin(x67); ! 结果： X14=X43=X35=X56=X67=1 ，其余为 0 ； ! 此为最短路 v1->v4->v3->v5->v6->v7 ，最短路的长度为 13

35 35 教材 P78-79 第 1 、 2 、 3 、 4 题 要求： 1 ）解答题，写出具体解法； 2 ）程序设计题，写出用有关软件实现的、并且是调试 通过的程序。 书面作业