“数学建模”讲座：图论方法及其建模

《“数学建模”讲座：图论方法及其建模》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数学建模》讲座：数学建模中的图论方法图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模的意识和能力。MCM中与图论有关的题目：1．90-B扫雪问题（二邮递员中国邮路问题）求欧拉回路的Fleury算法2．91-B通讯网络的最小生成树寻找最优Steiner树3．92-B应急电力修复系统最小生成树算法4．94-B计算机网络的最小接通时间中国大学生数学建模竞赛试题：1

2、.94-A逢山开路利用求最短路的Dijkstra算法94-B锁具装箱DFS算法2.98-B灾情巡视路线多邮递员中国邮路问题3.99-B钻井布局4.00-B钢管订购和运输§1图论的基础知识图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。在历史上，图论的创立开始于对著名的七桥问题的研究。是18世纪欧洲的一个城市，位于河畔，河中有两个岛屿和，人们架设了七座桥把河岸和两个小岛连接起来。当时城中的居民热衷于讨论这样一个问题：要从任何一块陆地出发，能否通过每座桥一次且不重复，最后返回出发地(图1)？瑞士数学家欧拉于1736年

3、解决了这个问题，他发表了图论的第一篇论文（！），证明了七桥问题是无解的。同时他提出并解决了更为一般的问题，从而奠定了图论的基础。24图1一.图的基本概念图G是由非空结点集以及边集所组成，记作。它的结点数称为阶。根据边有无方向，图分为有向图和无向图。有向图的边去掉方向后所得的图称为原有向图的基础图(或底图)。没有自环或多重边的图称简单图。有些实际问题抽象出来的图，边上往往带有信息，在边上附加一些数字来刻划此边，称权，此时该图称加权图。无向图中与结点v相关联的边数称为v的度数，记，有向图中以v为起点或终点的边数分别称为v的出度和入度，记。握手定理：（1）无向图中所有结点的度数之和等于边数

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

5、；如果u到v不可达，则记。如果无向图G的任两个结点都可达，则称G为连通图。有向图的连通性复杂一些：若G中任意两结点间都相互可达，则称G是强连通的；若G中任意两结点间至少有一个结点可达另一个结点，则称G是单向连通(简称单连通)的；若G的基础图是连通的，则称G是弱连通的；否则称G24是非连通图。若两个图的结点之间存在一个保持连接关系的双射,则称之为同构.设图，，若存在双射函数，使保持连接关系，即之间的连接关系与之间的连接关系完全相同，在有向图时还要保持边的方向，多重图时还要有相同的重数，则称与同构，记为。下面给出几组同构的图（结点的对应关系如图所示）。图2二．图的矩阵表示为适合使用计算机

6、对图进行存储和处理，需要用矩阵表示图。常用的有：邻接矩阵、可达性矩阵、距离矩阵等。定义设n阶图的结点集，则n阶方阵24称为G的邻接矩阵，其中aij表示以vi为起点、vj为终点的边的数目。一个图的邻接矩阵完整地刻划了图中各结点间的邻接关系。如图3，它们的邻接矩阵分别为：，v1v2v3v4图3由邻接矩阵的定义，很容易得到以下结论：（1）无向图的邻接矩阵是对称的；（2）图没有平行边当且仅当的元素全为0或1；（3）图没有自环当且仅当的主对角元全为0；（4）图是零图当且仅当的元素全为0；（5）若是无向图，则（6）若是有向图，则定理设n阶图G的结点集，A是G的邻接矩阵，则Ak中的元素等于G中从v

7、i到vj的长度为k的路径条数(，)。如图3中的，，，，，，，分别表示从到长度为1，2，3，4的路径条数，各为1条，1条，2条，3条，请读者自己在图上进行验证，并找出各条路径。24定义设n阶图G的结点集，则n阶方阵称为G的可达矩阵，其中显然，无向图的可达矩阵是对称的，而有向图则不然。计算公式为：，其中，和分别表示布尔和与布尔积。如图3中的可达矩阵为：利用图的邻接矩阵和可达矩阵可以判断图的连通性，下面结果是显然的：(1)无向图G是连通图当且仅当它的可达矩阵P的