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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（二）树的性质

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

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

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

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

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

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

算法三 (破圈法)

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

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

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

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

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

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

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

（二）Dijkstra算法 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); ! 设每个有向路用xij来表示，其中i是起点编号、j是终点编号; ! xij非0即1：最短路经过此边时为1；否则为0; ! 结果：X14=X43=X35=X56=X67=1，其余为0； ! 此为最短路之一：v1->v4->v3->v5->v6->v7，最短路的长度为13

书面作业 教材 P79-80 第 1、2、3 、4 题 要求： 1） 第 4 题主要用程序方法求解。若能够写出手工求解方法，则更佳； 2）解答题，写出具体解法； 3）程序设计题，写出用有关软件实现的、并且是调试通过的程序。