数学建模中的图论方法

数学建模中的图论方法湖南文理学院张莉茜数学建模中的图论方法1.引言2.图论的基础知识4.图论的几个实用算法5.其他问题3.综合例题数学建模中的图论方法----引言1.引言图论是离散数学的重要组成部分，它对于自然科学、工程技术、经济管理和社会现象等诸多问题，能够提供有力的数学模型加以解决，特别在国内外大学生数学建模竞赛当中，有不少问题可以应用图论模型解决。我们在此有针对性地把图论的骨干概念和结论以及相关的有效算法做一简要介绍，愿听者增强图论建模的意识和能力。数学建模中的图论方法----引言图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连结起来（如图）。问题是：要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。问题转化为：从任一点出发一笔画出七条线再回到起点。数学建模中的图论方法----引言注：图论中的“图”并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。数学建模中的图论方法----图论的基础知识2.图的基础知识图G是由非空结点集以及边集所组成，记作。它的结点数称为阶。根据边有无方向，图分为有向图和无向图。有向图的边去掉方向后所得的图称为原有向图的基础图(或底图)。没有自环或多重边的图称简单图。有些实际问题抽象出来的图，边上往往带有信息，在边上附加一些数字来刻划此边，称权，此时该图称加权图。无向图中与结点v相关联的边数称为v的度数，记，有向图中以v为起点或终点的边数分别称为v的出度和入度，记。握手定理：（1）无向图中所有结点的度数之和等于边数的两倍。（2）有向图中所有结点的出度(入度)之和等于边数。推论：任何图的奇结点必为偶数个。例如，一群人中，有奇数个朋友的人必为偶数个。12,,nVvvv12,,mEeee,GVEdegvdeg,degvv数学建模中的图论方法----图论的基础知识如果简单无向图的任两个结点均邻接，称之为完全图，n阶完全图记为，它的每个结点的度数等于,边数等于。nK1n212nnnC一个边的序列(或点的序列)称路径，封闭的路径称回路。边不重复的路径称简单路径，点不重复的路径称基本路径。路径所含边的条数称为路径的长度。如果存在从结点u到v的路径，则称从u到v可达。如果u到v可达，则从u到v的路径中长度最短的路径称为短程线（或测地线），它的长度称为从u到v的距离,记为；如果u到v不可达，则记。如果无向图G的任两个结点都可达，则称G为连通图。,duv,duv数学建模中的图论方法----图论的基础知识1111102012021020)(1GA0100110001010110)(2GA设n阶图的结点集，则n阶方阵称为G的邻接矩阵，其中表示以为起点、为终点的边的数目。一个图的邻接矩阵完整地刻划了图中各结点间的邻接关系。,GVE12,,nVvvvijnnAaijaivjv，如图1，它们的邻接矩阵分别为：v1v2v3v4··G2v1v3v4v21G数学建模中的图论方法----图论的基础知识，连通无回路图称为树。每个连通分支都是树的无向图称为森林．在结点数确定的情况下，树是连通图中边数最少的图，也是无回路图中边数最多的图．每个连通图G至少有一个生成子图是一棵树，称之为G的生成树。显然每个连通图都有生成树，而一般来说生成树不唯一(而边数是确定的)。如果G是一个加权连通图，我们希望找一棵权之和最小的生成树，称为最小生成树。定理：若树的结点数为n，边数为m，则m=n-1。数学建模中的图论方法----图论的基础知识例设有6个城市，它们之间有输油管道连通，其布置图如图(a)所示．战争期间，为了保卫油管不被破坏，需派部队看守，看守一段油管需一连士兵．为保证各城市间输油畅通，最少需派几连士兵？他们应驻于那些油管处？解：此问题即为寻找图(a)的生成树问题．由图知，结点数为6，故其生成树的边数为5，即最少需派5连士兵看守．其看守地段可见图(b)、(c)、(d)所画之线段．v1v3v5v2v4v6v1v3v5v2v4v6(a)(b)v1v3v5v2v4v6v1v3v5v2v4v6(c)(d)数学建模中的图论方法----图论的基础知识如果图G中具有一条经过所有边的简单回路,称欧拉回路,含欧拉回路的图称为欧拉图；如果图G中具有一条经过所有边的简单(非回路)路径,称欧拉路。定理:(1)连通无向图G是欧拉图的充要条件是G的每个结点均为偶结点;(2)连通无向图G含有欧拉路的充要条件是G恰有两个奇结点,且欧拉路必始于一个奇结点而终止于另一个奇结点.数学建模中的图论方法----图论的基础知识图1的所有结点均为偶结点，故为欧拉图，一条欧拉回路为：。图2有2个奇结点，故不是欧拉图，但有欧拉路：。abcdefcebfabcdeabeabcdefabcde（1）（2）数学建模中的图论方法----图论的基础知识ABCDFEGbcdae如左图是某街道图形。洒水车从A点出发执行洒水任务。试问是否存在一条洒水路线，使洒水车通过所有街道且不重复而最后回到车库B？（蚂蚁比赛问题）如右图所示，甲、乙两只蚂蚁分别位于结点处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点处。如果他们的速度相同，问谁先到达目的地？,abe数学建模中的图论方法----图论的基础知识哈密尔顿回路，起源于一个名叫“周游世界”的游戏，它是由英国数学家哈密尔顿（Hamilton）于1859年提出的。他用一个正十二面体的20个顶点代表20个大城市（图(a)），这个正十二面体同构于一个平面图（图(b)）。要求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点。这个游戏曾风靡一时，它有若干个解。图(b)给出了一个解。1324567891011121314151617181920（a）（b）数学建模中的图论方法----图论的基础知识meeeE,,,21如果图G中具有一条经过所有结点的基本回路（称哈密尔顿回路），则称为哈密尔顿图。虽然哈密尔顿图判定问题与欧拉图判定问题同样有意义，但遗憾的是至今为止还没有找到一个判别它的充分必要条件，这是图论中尚未解决的主要问题之一。数学建模中的图论方法----图论的基础知识设无向图，如果存在的一个分划，使得G的每一条边的两个端点分属和，则称G为二部图(或偶图)。和称为互补结点子集，此时可将G记为。,GVEV12,VV1V2V1V2V12,,VEV设是二部图，若，且M中任何两条边均不相邻，则称M是G的一个匹配；具有最大边数的匹配称为最大匹配；若最大匹配M满足，则称M是G的一个完备匹配，此时若，则称M为V1到V2的一个完备匹配；若，则称M是G的一个完美匹配．12,,GVEVME12min,MVV12VVM12VV数学建模中的图论方法----综合例题例1证明任意六个人的集会上，总会有三人互相认识或者不认识．证明这是1947年匈牙利数学竞赛出的一道试题，因为它很有趣且很重要，后来曾收录到《美国数学月刊》及其它数学刊物上。这类问题可以转化为图论中的完全图染色问题．把参加集会的人看作结点，作一个完全图，如果两个人认识，则两结点间的连线涂上红色，否则涂上蓝色．问题转化为：无论怎样涂色，总可以找到红或蓝．3.综合例题数学建模中的图论方法----综合例题例1证明任意六个人的集会上，总会有三人互相认识或者不认识．证明设六个结点为。从引出的边有五条，而颜色只有红蓝两种，由抽屉原理，至少有三条边同色，不失一般性，假定有三条边为红色。1,2,,6ivi1v121314,,,,,vvvvvv（1）如果结点之间至少有一条红边，比如是红边，则得到红色的三角形；（2）如果结点之间的边全是蓝色的，则得到蓝色的三角形。关于问题中的结点数，对任何，命题都成立．但当时，命题便不成立了。这说明：不同的六个点是保证用两色涂染其边，存在同色三角形的最少点数。234,,vvv23,vv123vvv234,,vvv234vvv6n5n数学建模中的图论方法----综合例题例2出席某次国际学术会议的有六个成员a,b,c,d,e,f，其中：a会讲汉语、法语和日语；b会讲德语、日语和俄语；c会讲英语和法语；d会讲汉语和西班牙语；e会讲英语和德语；f会讲俄语和西班牙语．如将此六人分成两组，是否会发生同一组内的任意两人不能互相直接交谈的情况？abdfec图18解用结点表示成员，两成员间如有共同语言，则用边相连，可得下图．由于图中的回路长度均为偶数，故此图为二部图．设，，当六位代表如此分组时，则同一组内的任意两个人都不能直接交谈．1,,Vacf2,,Vbde数学建模中的图论方法----综合例题例3某中学有3个课外小组：英语组(A)、物理组(B)和生物组(C)，有5名学生a,b,c,d,e，(1)已知a,b为A组成员，a,c,d为B组成员，c,d,e为C组成员；(2)已知a为A组成员，b,c,d为B组成员，b,c,d,e为C组成员；(3)已知a为A组成员，a又为B组成员，b,c,d,e为C组成员．问在以上三种情况下，能否各选出3名不兼职的组长？解：根据三种已知情况，分别画出二部图，如图所示．记，12,,,,,,,VABCVabcdeABCabcdeCBAedcbaG1G2G3CBAedcba数学建模中的图论方法----图论中的几个实用算法4.图论中的几个实用算法1．加权图中的最短路径的Dijkstra算法最短路径问题：给定连接若干城市的铁路网，寻找从指定城市到各城市去的最短路线。数学模型：设是一个加权图，边的权记为，路径P的长度定义为路径中边的权之和，记为。两结点u和v之间的距离定义为,,GVEW,uv,uvP不可达到当间的路径为，vuvuPPvud,,)(min),(问题：在加权的简单连通无向图G(V,E,W)中，求一结点a(源点)到其它结点x的距离——称单源问题。Dijkstra算法的基本思想是：若是从到的最短路径，则也必然是从到的最短路径。12nvvv1nv1v1vnv数学建模中的图论方法----图论中的几个实用算法2．求最小生成树的Kruskal算法数学模型：在一个连通加权图上求权最小的连通生成子图，显然，即求权最小的生成树，称最小生成树。筑路选线问题：欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为，设计一个线路图，使总造价最低。ijCKruskal算法（避圈法）1956年设G为由n个顶点、m条边构成的加权连通图。先将G中所有的边按权的大小次序进行排列，不妨设，12meeeⅰ；ⅱ若导出的子图不含回路，则；ⅲ若A中已有n-1条边，则stop；否则，转ⅱ。1,kAAeAAe1kk数学建模中的图论方法----图论中的几个实用算法例：求图(a)中加权图的最小生成树．解：用Kruscal算法可以求得最小生成树如图(b)．1234567811910121235689(a)(b)数学建模中的图论方法----图论中的几个实用算法3.中国邮路问题中国邮路问题：邮递员传送报纸和信件，都要从邮局出发，经过他所管辖的每一条街道，最后回到邮局，要求最短的传送路线．数学模型：在加权图上找一条经过所有边至少一次的回路，使它的权数最小。如果是欧拉图,则所求回路必为欧拉回路。下面给出在欧拉图上求取欧拉回路的Fleury算法。数学建模中的图论方法----图论中的几个实用算法(1)Fleury算法(3)重复步骤(2),直至不