数学建模中的图论方法.ppt

《数学建模中的图论方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模中的图论方法湖南文理学院张莉茜数学建模中的图论方法1.引言2.图论的基础知识4.图论的几个实用算法5.其他问题3.综合例题数学建模中的图论方法----引言1.引言图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模的意识和能力。数学建模中的图论方法----引言图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1

2、736年发表的“哥尼斯堡的七座桥”。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连结起来（如图）。问题是：要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。问题转化为：从任一点出发一笔画出七条线再回到起点。数学建模中的图论方法----引言注：图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但

3、彻底解决了这个问题，而且开创了图论研究的先河。数学建模中的图论方法----图论的基础知识2.图的基础知识图G是由非空结点集以及边集所组成，记作。它的结点数称为阶。根据边有无方向，图分为有向图和无向图。有向图的边去掉方向后所得的图称为原有向图的基础图(或底图)。没有自环或多重边的图称简单图。有些实际问题抽象出来的图，边上往往带有信息，在边上附加一些数字来刻划此边，称权，此时该图称加权图。无向图中与结点v相关联的边数称为v的度数，记，有向图中以v为起点或终点的边数分别称为v的出度和入度，记。握手定理：（1）无向图中所有结点的度数之和等于边数的两

4、倍。（2）有向图中所有结点的出度(入度)之和等于边数。推论：任何图的奇结点必为偶数个。例如，一群人中，有奇数个朋友的人必为偶数个。数学建模中的图论方法----图论的基础知识如果简单无向图的任两个结点均邻接，称之为完全图，n阶完全图记为，它的每个结点的度数等于,边数等于。一个边的序列(或点的序列)称路径，封闭的路径称回路。边不重复的路径称简单路径，点不重复的路径称基本路径。路径所含边的条数称为路径的长度。如果存在从结点u到v的路径，则称从u到v可达。如果u到v可达，则从u到v的路径中长度最短的路径称为短程线（或测地线），它的长度称为从u到v的

5、距离,记为；如果u到v不可达，则记。如果无向图G的任两个结点都可达，则称G为连通图。数学建模中的图论方法----图论的基础知识设n阶图的结点集，则n阶方阵称为G的邻接矩阵，其中表示以为起点、为终点的边的数目。一个图的邻接矩阵完整地刻划了图中各结点间的邻接关系。，如图1，它们的邻接矩阵分别为：v1v2v3v4数学建模中的图论方法----图论的基础知识，连通无回路图称为树。每个连通分支都是树的无向图称为森林．在结点数确定的情况下，树是连通图中边数最少的图，也是无回路图中边数最多的图．每个连通图G至少有一个生成子图是一棵树，称之为G的生成树。显然

6、每个连通图都有生成树，而一般来说生成树不唯一(而边数是确定的)。如果G是一个加权连通图，我们希望找一棵权之和最小的生成树，称为最小生成树。定理：若树的结点数为n，边数为m，则m=n-1。数学建模中的图论方法----图论的基础知识例设有6个城市，它们之间有输油管道连通，其布置图如图(a)所示．战争期间，为了保卫油管不被破坏，需派部队看守，看守一段油管需一连士兵．为保证各城市间输油畅通，最少需派几连士兵？他们应驻于那些油管处？解：此问题即为寻找图(a)的生成树问题．由图知，结点数为6，故其生成树的边数为5，即最少需派5连士兵看守．其看守地段可见

7、图(b)、(c)、(d)所画之线段．数学建模中的图论方法----图论的基础知识如果图G中具有一条经过所有边的简单回路,称欧拉回路,含欧拉回路的图称为欧拉图；如果图G中具有一条经过所有边的简单(非回路)路径,称欧拉路。定理:(1)连通无向图G是欧拉图的充要条件是G的每个结点均为偶结点;(2)连通无向图G含有欧拉路的充要条件是G恰有两个奇结点,且欧拉路必始于一个奇结点而终止于另一个奇结点.数学建模中的图论方法----图论的基础知识图1的所有结点均为偶结点，故为欧拉图，一条欧拉回路为：。图2有2个奇结点，故不是欧拉图，但有欧拉路：。（1）（2）数

8、学建模中的图论方法----图论的基础知识如左图是某街道图形。洒水车从A点出发执行洒水任务。试问是否存在一条洒水路线，使洒水车通过所有街道且不重复而最后回到车库B？（蚂蚁比赛问题）