“数学建模”讲座：图论方法和其建模.doc

《数学建模》讲座： 数学建模中的图论方法 图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模的意识和能力。 MCM中与图论有关的题目： 1．90-B 扫雪问题（二邮递员中国邮路问题） 求欧拉回路的Fleury算法 2．91-B 通讯网络的最小生成树 寻找最优Steiner树 3．92-B 应急电力修复系统 最小生成树算法 4．94-B 计算机网络的最小接通时间 中国大学生数学建模竞赛试题： 1. 94-A 逢山开路 利用求最短路的Dijkstra算法 94-B 锁具装箱 DFS算法 2. 98-B 灾情巡视路线 多邮递员中国邮路问题 3. 99-B 钻井布局 4. 00-B 钢管订购和运输 §1 图论的基础知识 图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。 在历史上，图论的创立开始于对著名的七桥问题的研究。是18世纪欧洲的一个城市，位于河畔，河中有两个岛屿和，人们架设了七座桥把河岸和两个小岛连接起来。当时城中的居民热衷于讨论这样一个问题：要从任何一块陆地出发，能否通过每座桥一次且不重复，最后返回出发地(图1)？瑞士数学家欧拉于1736年解决了这个问题，他发表了图论的第一篇论文（！），证明了七桥问题是无解的。同时他提出并解决了更为一般的问题，从而奠定了图论的基础。 图1 一.图的基本概念 图G是由非空结点集以及边集所组成，记作。它的结点数称为阶。 根据边有无方向，图分为有向图和无向图。有向图的边去掉方向后所得的图称为原有向图的基础图(或底图)。 没有自环或多重边的图称简单图。 有些实际问题抽象出来的图，边上往往带有信息，在边上附加一些数字来刻划此边，称权，此时该图称加权图。 无向图中与结点v相关联的边数称为v的度数，记，有向图中以v为起点或终点的边数分别称为v的出度和入度，记。 握手定理：（1）无向图中所有结点的度数之和等于边数的两倍。 （2）有向图中所有结点的出度(入度)之和等于边数。 推论：任何图的奇结点必为偶数个。 例如，一群人中，有奇数个朋友的人必为偶数个。 如果简单无向图的任两个结点均邻接，称之为完全图，n阶完全图记为，它的每个结点的度数等于,边数等于。 若为n阶简单图，则在相应的完全图中去掉的所有边所得的图称为的补图，记为。 一个边的序列(或点的序列)称路径，封闭的路径称回路。边不重复的路径称简单路径，点不重复的路径称基本路径。路径所含边的条数称为路径的长度。 如果存在从结点u到v的路径，则称从u到v可达。如果u到v可达，则从u到v的路径中长度最短的路径称为短程线（或测地线），它的长度称为从u到v的距离,记为；如果u到v不可达，则记。G的任两个结点都可达，则称G为连通图。 有向图的连通性复杂一些：若G中任意两结点间都相互可达，则称G是强连通的；若G中任意两结点间至少有一个结点可达另一个结点，则称G是单向连通(简称单连通)的；若G的基础图是连通的，则称G是弱连通的；否则称G是非连通图。 若两个图的结点之间存在一个保持连接关系的双射,则称之为同构. 设图，，若存在双射函数，使保持连接关系，即之间的连接关系与之间的连接关系完全相同，在有向图时还要保持边的方向，多重图时还要有相同的重数，则称与同构，记为。 下面给出几组同构的图（结点的对应关系如图所示）。 图2 二．图的矩阵表示 为适合使用计算机对图进行存储和处理，需要用矩阵表示图。常用的有：邻接矩阵、可达性矩阵、距离矩阵等。 定义 设n阶图的结点集，则n阶方阵称为G的邻接矩阵，其中aij表示以vi为起点、vj为终点的边的数目。 一个图的邻接矩阵完整地刻划了图中各结点间的邻接关系。 如图3，它们的邻接矩阵分别为： ， 图3 由邻接矩阵的定义，很容易得到以下结论： （1）无向图的邻接矩阵是对称的； （2）图没有平行边当且仅当的元素全为0或1； （3）图没有自环当且仅当的主对角元全为0； （4）图是零图当且仅当的元素全为0； （5）若是无向图，则 （6）若是有向图，则 定理 设n阶图G的结点集，A是G的邻接矩阵，则Ak中的元素等于G中从vi到vj的长度为k的路径条数(，)。 如图3中的， ，， ，，，，分别表示从到长度为1，2，3，4的路径条数，各为1条，