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

1《数学建模》讲座：数学建模中的图论方法图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模的意识和能力。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图论的基础知识图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。在历史上，图论的创立开始于对著名的nigsbergoK七桥问题的研究。nigsbergoK是18世纪欧洲的一个城市，位于Pregel河畔，河中有两个岛屿A和D，人们架设了七座桥把河岸和两个小岛连接起来。当时城中的居民热衷于讨论这样一个问题：要从任何一块陆地出发，能否通过每座桥一次且不重复，最后返回出发地(图1)？瑞士数学家欧拉于1736年解决了这个问题，他发表了图论的第一篇论文（！），证明了七桥问题是无解的。同时他提出并解决了更为一般的问题，从而奠定了图论的基础。2ACDBBCAD图1一.图的基本概念图G是由非空结点集nvvvV,,,21以及边集meeeE,,,21所组成，记作EVG,。它的结点数称为阶。根据边有无方向，图分为有向图和无向图。有向图的边去掉方向后所得的图称为原有向图的基础图(或底图)。没有自环或多重边的图称简单图。有些实际问题抽象出来的图，边上往往带有信息，在边上附加一些数字来刻划此边，称权，此时该图称加权图。无向图中与结点v相关联的边数称为v的度数，记)deg(v，有向图中以v为起点或终点的边数分别称为v的出度和入度，记)(deg)(degvv及。握手定理：（1）无向图中所有结点的度数之和等于边数的两倍。（2）有向图中所有结点的出度(入度)之和等于边数。推论：任何图的奇结点必为偶数个。例如，一群人中，有奇数个朋友的人必为偶数个。如果简单无向图的任两个结点均邻接，称之为完全图，n阶完全图记为nK，它的每个结点的度数等于1n,边数等于2)1(2nnCn。若G为n阶简单图，则在相应的完全图nK中去掉G的所有边所得的图称为G的补图，记为G。一个边的序列(或点的序列)称路径，封闭的路径称回路。边不重复的路径称简单路径，点不重复的路径称基本路径。路径所含边的条数称为路径的长度。如果存在从结点u到v的路径，则称从u到v可达。如果u到v可达，则从u到v的路径中长度最短的路径称为短程线（或测地线），它的长度称为从u到v的距离,记为),(vud；如果u到v不可达，则记),(vud。如果无向图G的任两个结点都可达，则称G为连通图。有向图的连通性复杂一些：若G中任意两结点间都相互可达，则称G是强连通的；若G中任意两结点间至少有一个结点可达另一个结点，则称G是单向连通(简称单连通)的；若G的基础图是连通的，则称G是弱连通的；否则称G是非连3通图。若两个图的结点之间存在一个保持连接关系的双射,则称之为同构.设图),(EVG，),(EVG，若存在双射函数VVf:，使f保持连接关系，即jivv,之间的连接关系与)(),(jivfvf之间的连接关系完全相同，在有向图时还要保持边的方向，多重图时还要有相同的重数，则称G与G同构，记为GG。下面给出几组同构的图（结点的对应关系如图所示）。acbabb＇＇dea＇c＇d＇e＇b＇dea＇＇c＇＇d＇＇e＇＇abcdefa＇b＇c＇d＇e＇f＇abcdea＇b＇c＇d＇e＇图2二．图的矩阵表示为适合使用计算机对图进行存储和处理，需要用矩阵表示图。常用的有：邻接矩阵、可达性矩阵、距离矩阵等。定义设n阶图EVG,的结点集nvvvV,,,21，则n阶方阵nnijaA)(4称为G的邻接矩阵，其中aij表示以vi为起点、vj为终点的边的数目。一个图的邻接矩阵完整地刻划了图中各结点间的邻接关系。如图3，它们的邻接矩阵分别为：1111102012021020)(1GA，0100110001010110)(2GA··G2v1v3v4v2图3由邻接矩阵的定义，很容易得到以下结论：（1）无向图的邻接矩阵是对称的；（2）图G没有平行边当且仅当A的元素全为0或1；（3）图G没有自环当且仅当A的主对角元全为0；（4）图G是零图当且仅当A的元素全为0；（5）若G是无向图，则),,1(,)deg(1niaaviinjiji（6）若G是有向图，则,)(deg1njijiav,)(deg1njjiiav),,1(ni定理设n阶图G的结点集nvvvV,,,21，A是G的邻接矩阵，则Ak中的元素)(kija等于G中从vi到vj的长度为k的路径条数(,,,1,nji，,2,1k)。如图3中的2G，11001200121012012A，12002300240124103A，23003500471047014A143a，1)2(43a，2)3(43a，3)4(43a，分别表示从4v到3v长度为1，2，3，4的路径条数，各为1条，1条，2条，3条，请读者自己在图上进行验证，并找出各条路径。v1v2v3v45定义设n阶图G的结点集nvvvV,,,21，则n阶方阵nnijpP)(称为G的可达矩阵，其中，否则可达到，若从01jiijvvp显然，无向图的可达矩阵是对称的，而有向图则不然。计算公式为：)()3()2()1(nAAAAP，其中)1()1()()1()2()3()1()1()2()1(,,,,AAAAAAAAAAAnn，和分别表示布尔和与布尔积。如图3中2G的可达矩阵为：1100110011111111P利用图的邻接矩阵和可达矩阵可以判断图的连通性，下面结果是显然的：(1)无向图G是连通图当且仅当它的可达矩阵P的元素全为1；(2)有向图G是强连通图当且仅当它的可达矩阵P的元素全为1；(3)有向图G是单向连通图当且仅当它的可达矩阵P及其转置PT的布尔和TPP中除主对角元外全为1；(4)有向图G是(弱)连通图当且仅当以它的邻接矩阵A及其转置AT的布尔和TAA作为邻接矩阵而得到的可达矩阵的元素全为1。另外，也可以利用图的可达性矩阵判断有无回路：图G中存在回路当且仅当它的可达性矩阵的主对角元不全为零。也可以利用可达矩阵求出无向图的连通分支等，请读者考虑具体的方法。三．几类重要的图1．无向树连通无回路图称为树。每个连通分支都是树的无向图称为森林．下面图中，(a),(b),(c),(d)都是树，(e)是森林．(a)(b)(c)6(d)(e)定理：若树的结点数为n，边数为m，则m=n-1。在结点数确定的情况下，树是连通图中边数最少的图，也是无回路图中边数最多的图．每个连通图G至少有一个生成子图是一棵树，称之为G的生成树。显然每个连通图都有生成树，而一般来说生成树不唯一(而边数是确定的)。例设有6个城市654321,,,,,vvvvvv，它们之间有输油管道连通，其布置图如图4.3(a)所示．战争期间，为了保卫油管不被破坏，需派部队看守，看守一段油管需一连士兵．为保证各城市间输油畅通，最少需派几连士兵？他们应驻于那些油管处？解：此问题即为寻找图4.3(a)的生成树问题．由图知，结点数为6，故其生成树的边数为5，即最少需派5连士兵看守．其看守地段可见图4.3(b)、(c)、(d)所画之线段．v1v3v5v2v4v6v1v3v5v2v4v6(a)(b)v1v3v5v2v4v6v1v3v5v2v4v6(c)(d)图4.3如果G是一个加权连通图，我们希望找一棵权之和最小的生成树，称为最小生成树。2．根树定义一棵非平凡的有向树，如果恰有一个结点的入度为0，其余结点的入度均为1，则称此有向树为根树．入度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点称为分枝点。7习惯上我们把根树的根画在最上方，叶画在下方，有向边的方向均指向下方，这样就可以省去全部箭头。v1(a)v3v2v4v5v6v7v8v9v10v11v12(b)v5v1v3v2v4v6v7v8v9v10v11v123.欧拉图如果图G中具有一条经过所有边的简单回路,称欧拉回路,含欧拉回路的图称为欧拉图；如果图G中具有一条经过所有边的简单(非回路)路径,称欧拉路。定理:(1)连通无向图G是欧拉图的充要条件是G的每个结点均为偶结点;(2)连通无向图G含有欧拉路的充要条件是G恰有两个奇结点,且欧拉路必始于一个奇结点而终止于另一个奇结点.图7的所有结点均为偶结点，故为欧拉图，一条欧拉回路为：aabcdefcebf。图8有2个奇结点，故不是欧拉图，但有欧拉路：bcdeabe。从欧拉回路和欧拉路的定义可知，图中的欧拉回路(欧拉路)是经过图中所有边的最短回路(路径)。abcdefabcde图7图8ABCDFEGbcdae8图9图10如图9是某街道图形。洒水车从A点出发执行洒水任务。试问是否存在一条洒水路线，使洒水车通过所有街道且不重复而最后回到车库B？此问题即为求证图中是否存在A到B的欧拉路。由于图中每个结点除A，B为奇结点外其余均为偶结点，由定理可知，这样的洒水线路是存在的，例如，ACDEFBGCFGAB或AGFEDCFBGCAB，等等。（蚂蚁比赛问题）如图10所示，甲、乙两只蚂蚁分别位于结点ba,处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点e处。如果他们的速度相同，问谁先到达目的地？在图中，仅有两个奇结点eb,，因而存在从b到e的欧拉路，蚂蚁乙走到e只要走一条欧拉路，边数为9条；而蚂蚁甲要想走完所有的边到达e，至少要先走一条边到达b，再走一条欧拉路，因而它至少要走10条边才能到达e，所以乙必胜。如图11(a)是一幢房子的平面图，前门进入一个客厅，由客厅通向四个房间。如果要求每扇门只能通过一次，现在由前门进入，能否通过所有的门走遍所有的房间（包括客厅），然后从后门走出？fdabcefadec)(a图11)(b将四个房间和一个客厅及室外作为接点，门作为边画出图(b)。由于b和e是仅有的两个奇结点，故从前门进、后门出的欧拉路是不存在的，即本题无解。如果把“前门进、后门出”这一条件去掉，则存在“每扇门通过一次且仅一次”的走法。请读者找出具体的走法。4．哈密尔顿图所谓哈密尔顿回路，起源于一个名叫“周游世界”的游戏，它是由英国数学家哈密尔顿（Hamilton）于1859年提出的。他用一个正十二面体的20个顶点代表20个大城市（图12(a)），这个正十二面体同构于一个平面图（图12(b)）。要求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点。这个游戏曾风靡一时，它有若干个解。图12(b)给出了一个解。定义：如果图G中具有一条经过所有结点的基本回路（称哈密尔顿回路），则称为哈密尔顿图。虽然哈密尔顿图判定问题与欧拉图判定问题同样有意义，但遗憾的是至今为止还没有找到一个判别它的充分必要条件，这是图论中尚未解决的主要问题之一。91324567891011121314151617181920(a)图12(b)5．二部图定义设无向图),(EVG，如果存在V的一个分划21,VV，使得G的每一条边的两个端点