数学建模中的图论方法

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

2、论方法数学建模中的图论方法-引言引言 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸连结起来（如图）。问题是：要从这四块陆地中的任何一块开始通过每要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。一座桥正好一次，再回到起点。问题转化为：从任一点出发一笔画出七条线再回到起点。问题转化为：从任一点出发一笔画出七条线再回到起点。数学建模中的图论方法数学建模中的图论方法-引言引言 注：图论中的注：图论中的“图图”并不是通常意义下的几何图形并不是通常意义下的几何图形或物体的形状图，而是以一种抽象的

3、形式来表达一些确定或物体的形状图，而是以一种抽象的形式来表达一些确定的事物及其关系的一个数学系统。的事物及其关系的一个数学系统。 欧拉考察了一般一笔画的结构特点，给出了欧拉考察了一般一笔画的结构特点，给出了一笔一笔画的一个判定法则画的一个判定法则：这个图是连通的，且每个点都与这个图是连通的，且每个点都与偶数线相关联，偶数线相关联，将这个判定法则应用于七桥问题，得将这个判定法则应用于七桥问题，得到了到了“不可能走通不可能走通”的结果，不但彻底解决了这个问的结果，不但彻底解决了这个问题，而且开创了图论研究的先河题，而且开创了图论研究的先河。数学建模中的图论方法数学建模中的图论方法-图论的基础知识图

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

5、入度)之和等于边数。推论推论：任何图的奇结点必为偶数个。 例如，一群人中，有奇数个朋友的人必为偶数个。12,nvv vv12,mee ee,gv e deg v deg,degvv数学建模中的图论方法数学建模中的图论方法-图论的基础知识图论的基础知识 如果简单无向图的任两个结点均邻接，称之为完全图完全图，n阶完全图记为 ，它的每个结点的度数等于 ,边数等于 。nk1n212nn nc 一个边的序列(或点的序列)称路径路径，封闭的路径称回回路路。边不重复的路径称简单路径简单路径，点不重复的路径称基本基本路径路径。路径所含边的条数称为路径的长度长度。 如果存在从结点u到v的路径，则称从u到v可达可

6、达。如果u到v可达，则从u到v的路径中长度最短的路径称为短程线短程线（或测地线测地线），它的长度称为从u到v的距离距离,记为 ；如果u到v不可达，则记 。 如果无向图g的任两个结点都可达，则称g为连通图连通图。,d u v,d u v 数学建模中的图论方法数学建模中的图论方法-图论的基础知识图论的基础知识1111102012021020)(1ga0100110001010110)(2ga 设n阶图 的结点集 ，则n阶方阵 称为g的邻接矩阵，其中 表示以 为起点、 为终点的边的数目。 一个图的邻接矩阵完整地刻划了图中各结点间的邻接关系。,gv e12,nvv vvijn naaijaivjv，

7、如图1，它们的邻接矩阵分别为：v1v2v3v4 g2 v1 v3 v4 v2 1g数学建模中的图论方法数学建模中的图论方法-图论的基础知识图论的基础知识， 连通无回路图称为树树。每个连通分支都是树的无向图称为森林森林 在结点数确定的情况下，树是连通图中边数最少的图，也是无回路图中边数最多的图 每个连通图g至少有一个生成子图是一棵树，称之为g的生成树生成树。显然每个连通图都有生成树，而一般来说生成树不唯一(而边数是确定的)。 如果g是一个加权连通图，我们希望找一棵权之和最小的生成树，称为最小生成树最小生成树。 定理定理：若树的结点数为n，边数为m，则m=n-1。数学建模中的图论方法数学建模中的图

8、论方法-图论的基础知识图论的基础知识例例 设有6个城市，它们之间有输油管道连通，其布置图如图(a)所示战争期间，为了保卫油管不被破坏，需派部队看守，看守一段油管需一连士兵为保证各城市间输油畅通，最少需派几连士兵？他们应驻于那些油管处？解：解：此问题即为寻找图(a)的生成树问题由图知，结点数为6，故其生成树的边数为5，即最少需派5连士兵看守其看守地段可见图(b)、(c)、(d)所画之线段 v1 v3 v5 v2 v4 v6 v1 v3 v5 v2 v4 v6 (a) (b) v1v3v5v2v4v6v1v3v5v2v4v6(c)(d)数学建模中的图论方法数学建模中的图论方法-图论的基础知识图论的

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

10、图论方法数学建模中的图论方法-图论的基础知识图论的基础知识abcdfegbcdae如左图是某街道图形。洒水车从a点出发执行洒水任务。试问是否存在一条洒水路线，使洒水车通过所有街道且不重复而最后回到车库b？（蚂蚁比赛问题）如右图所示，甲、乙两只蚂蚁分别位于结点 处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结 点 处。如果他们的速度相同，问谁先到达目的地？, a be数学建模中的图论方法数学建模中的图论方法-图论的基础知识图论的基础知识 哈密尔顿回路，起源于一个名叫“周游世界”的游戏，它是由英国数学家哈密尔顿（hamilton）于1859年提出的。他用一

11、个正十二面体的20个顶点代表20个大城市（图(a)），这个正十二面体同构于一个平面图（图(b)）。要求沿着正十二面体的棱，从一个城市出发，经过每个城市恰好一次，然后回到出发点。这个游戏曾风靡一时，它有若干个解。图(b)给出了一个解。 1 3 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 （a）（b）数学建模中的图论方法数学建模中的图论方法-图论的基础知识图论的基础知识meeee,21 如果图g中具有一条经过所有结点的基本回路（称哈密尔顿回路），则称为哈密尔顿图哈密尔顿图。 虽然哈密尔顿图判定问题与欧拉图判定问题同样有意义，但遗憾的是至今为止还没有

12、找到一个判别它的充分必要条件，这是图论中尚未解决的主要问题之一。数学建模中的图论方法数学建模中的图论方法-图论的基础知识图论的基础知识 设无向图 ，如果存在 的一个分划 ，使得g的每一条边的两个端点分属 和 ，则称g为二部图二部图(或偶图偶图)。 和 称为互补结点子集互补结点子集，此时可将g记为 。,gv ev12,v v1v2v1v2v12,v e v 设 是二部图，若 ，且m中任何两条边均不相邻，则称m是g的一个匹配匹配；具有最大边数的匹配称为最大匹配最大匹配；若最大匹配m满足 ，则称m是g的一个完备匹配完备匹配，此时若 ，则称m为v1到v2的一个完备匹配；若 ，则称m是g的一个完美匹配完

13、美匹配12,gv e vme12min,mvv12vvm12vv数学建模中的图论方法数学建模中的图论方法-综合例题综合例题例例1 1 证明任意六个人的集会上，总会有三人互相认识或者不认识证明证明 这是1947年匈牙利数学竞赛出的一道试题，因为它很有趣且很重要，后来曾收录到美国数学月刊及其它数学刊物上。这类问题可以转化为图论中的完全图染色问题 把参加集会的人看作结点，作一个完全图，如果两个人认识，则两结点间的连线涂上红色，否则涂上蓝色问题转化为：无论怎样涂色，总可以找到红或蓝3.3.综合例题综合例题数学建模中的图论方法数学建模中的图论方法-综合例题综合例题例例1 1 证明任意六个人的集会上，总会

14、有三人互相认识或者不认识证明证明 设六个结点为 。从 引出的边有五条，而颜色只有红蓝两种，由抽屉原理，至少有三条边同色，不失一般性，假定有三条边 为红色。1,2,6iv i 1v 121314,v vv vv v（1）如果结点 之间至少有一条红边，比如 是红边，则得到红色的三角形 ；（2）如果结点 之间的边全是蓝色的，则得到蓝色的三角形 。 关于问题中的结点数，对任何 ，命题都成立但 当 时，命题便不成立了。这说明：不同的六个点是保证用两色涂染其边，存在同色三角形的最少点数。234,v v v23,v v1 2 3v v v234,v v v2 3 4v v v6n 5n 数学建模中的图论方法

15、数学建模中的图论方法-综合例题综合例题例例2 2 出席某次国际学术会议的有六个成员a, b, c, d, e, f，其中：a会讲汉语、法语和日语；b会讲德语、日语和俄语；c会讲英语和法语；d会讲汉语和西班牙语；e会讲英语和德语；f会讲俄语和西班牙语如将此六人分成两组，是否会发生同一组内的任意两人不能互相直接交谈的情况？ abdfec图18解解 用结点表示成员，两成员间如有共同语言，则用边相连，可得下图由于图中的回路长度均为偶数，故此图为二部图设 ， ，当六位代表如此分组时，则同一组内的任意两个人都不能直接交谈1, ,va c f2, ,vb d e数学建模中的图论方法数学建模中的图论方法-综合

16、例题综合例题例例3 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, , , , ,va b cva b c d e a b c a b c d e c b a e d c b a g1 g2

17、g3 c b a e d c b a 数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法4.4.图论中的几个实用算法图论中的几个实用算法1 1加权图中的最短路径的加权图中的最短路径的dijkstradijkstra算法算法 最短路径问题：给定连接若干城市的铁路网，寻找从指定城市到各城市去的最短路线。 数学模型：设 是一个加权图，边 的权记为 ，路径p的长度定义为路径中边的权之和，记为 。两结点u和v之间的距离距离定义为 ,gv e w, u v, u v p 不不可可达达到到当当间间的的路路径径为为，vuvuppvud , ,)(min),( 问题问题：在加权的

18、简单连通无向图g(v,e,w)中，求一结点a(源点)到其它结点x的距离称单源问题单源问题。dijkstra算法的基本思想是：若 是从 到 的最短路径，则也必然是从 到 的最短路径。1 2nv vv1nv1v1vnv数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法2 2求最小生成树的求最小生成树的kruskalkruskal算法算法 数学模型：在一个连通加权图上求权最小的连通生成子图，显然，即求权最小的生成树，称最小生成树。最小生成树。 筑路选线问题：欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为 ，设计一个线路图，使总造价最低。ijckruskalk

19、ruskal算法算法（避圈法）1956年 设g为由n个顶点、m条边构成的加权连通图。先将g中所有的边按权的大小次序进行排列，不妨设 ， 12meee ； 若 导出的子图不含回路，则 ； 若a中已有n-1条边，则stop；否则 ，转。 1,ka ae aae1kk数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法例：求图(a)中加权图的最小生成树解：解： 用kruscal算法可以求得最小生成树如图(b) 1 2 3 4 5 6 7 8 11 9 10 12 1 2 3 5 6 8 9 (a) (b) 数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图

20、论中的几个实用算法3.3.中国邮路问题中国邮路问题 中国邮路问题：邮递员传送报纸和信件，都要从邮局出发，经过他所管辖的每一条街道，最后回到邮局，要求最短的传送路线 数学模型：在加权图上找一条经过所有边至少一次的回路，使它的权数最小。 如果是欧拉图,则所求回路必为欧拉回路。下面给出在欧拉图上求取欧拉回路的fleury算法。数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法(1)fleury(1)fleury算法算法(3) 重复步骤(2),直至不能进行下去为止。(1) 任取起始结点 ,令 ；(2) 设路径 已选定,则从 中选一边,使得: 0vv gwv0 1 1 2

21、iiiwv ev eev 12,ie ge ee() 与 相连(共端)；() 除非已无选择余地, 不要选 的桥(断边),即 仍连通；1ieie1ie12,iigge ee1iige数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法(2)edmonds-johnsonedmonds-johnson算法算法 如果g不是欧拉图，即存在奇结点，这时某些边必被重复走过，我们称这样的边为重复边重复边。考虑到奇结点必为偶数个，我们可以把奇结点划分成若干对，每对之间在g中有相应的最短路，将这些最短路的边以原来的权作为重复边叠加在原图上形成一个多重图g*，则g*是一个欧拉图，可用

22、fleury算法求出欧拉回路。问题是当g的奇结点较多时，可能有很多的配对方法，应怎样选择配对，使相应的欧拉回路的权最小呢？1973年，edmonds和johnson给出下面的算法：数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法(2)edmonds-johnsonedmonds-johnson算法算法设g是连通加权图,(1) 求出g的奇结点集 ；(2) 用dijkstra算法求得v0中每对结点 的距离 ；(3) 构作加权完全图 :以 为结点集,以 为边 的权；(4) 求 中权之和最小的完备匹配m；(5) 用dijkstra算法求m中边的端点之间在g中的最短路径

23、；(6) 在(5)中求得的每条最短路径上每条边添加一条同权的新边,即得所求之欧拉图g*；(7) 在g*上用fleury算法求一条欧拉回路,即为问题的解。 0,1 mod2vvvv gd v, u v,d u v0vk0v,d u v, u v0vk数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法4.4.迷宫和迷宫和dfsdfs算法算法 迷宫问题：一座迷宫，游人事先未知其结构，如何搜索前进，保证万无一失地通过每一通道再从入口退出？ 纵深搜索原则：任选一条未曾走过的通道就尽可能远地走下去，直至无未曾走过的路可走时，沿未逆行过的最晚来路返回，发现有未走过的路，则沿它

24、尽可能远地走下去，依次运行至重返入口止。 1973年，hopcroft和tarjan把上述纵深搜索原则编写成dfs(depth first search)算法. 例如，在地图是未知的情形下，双车道单车扫雪车，按右侧通行交通规则，依dfs算法的过程安排扫雪工作程序即可。数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法5.tsp(5.tsp(货郎担问题货郎担问题) )及及“最邻近算法最邻近算法” 一个与哈密尔顿图有密切关系的问题是所谓“货郎担”问题或“旅行商”问题(travelling salesman problem)：货郎为了销售物品，要去访问若干个村、镇，然

25、后回到自己所住的地方。假设每个村镇间都有路，那么他应该怎样设计所走的路线，使得能对每个村镇恰好访问一次且走的路程最短？用图论的话来讲就是：在一个加权的完全无向图中，如何寻找一条最短的哈密尔顿回路？ 迄今为止还没有找到一个解决“货郎担”问题的有效算法（多项式算法）。一般来讲，这个问题比哈密尔顿问题更加困难些。下面介绍一个近似解法“最邻近方法最邻近方法”（或称“贪婪算法”），这是实际工作中经常采用的方法：数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法meeee,21最邻近算法最邻近算法 选任意点作为始点，找出一个与始点最近的点，形成一条边的初始路径。然后用逐点扩

26、充这条路径。 设x表示最新加到这条路径上的点，从不在路径上的所有点中，选一个与x最邻近的点，把连接x与此点的边加到这条路径中。重复这一步，直到g中所有顶点包含在路径中。 把始点和最后加入的顶点之间的边放入，这样就得到一个回路。数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法meeee,21例 对加权完全无向图k5如图(a)，如果从v1出发，使用“最邻近方法”得到的哈密尔顿回路如图(b)，总距离为40；最小哈密尔顿回路的总距离为37（如图(c)）。 v1 v2 v3 v4 v5 14 13 11 8 12 5 7 10 9 6 v1 v2 v3 v4 v5 14

27、 8 5 7 6 v1 v2 v3 v4 v5 5 7 10 9 6 (a)(b)(c)数学建模中的图论方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法6.6.匈牙利算法匈牙利算法 分工问题：工作人员 去做n件作 ，每人适合做其中的一项或几项，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？12,nx xx12,ny yy 数学模型：g是二分图,结点集划分为 , , ,当且仅当 适合做工作 时, ,求g中的最大匹配.解决这个问题可以用1965年edmonds提出的匈牙利算法.xy12,nxx xx12,nyy yyixjy ,ijx ye g数学建模中的图论

28、方法数学建模中的图论方法-图论中的几个实用算法图论中的几个实用算法 最佳分工问题：在分工问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个方案，使公司总效益最大。 数学模型：在分工问题的模型中，图g的每边加了权 表示 做工作 的效益，求加权图g上的权最大的完备匹配。,0ijx yixjy 解决这个问题可以用kuhn-kuhn-munkrasmunkras算法。算法。 数学建模中的图论方法数学建模中的图论方法-其他问题其他问题5.5.其他问题其他问题1. 1. 地图着色问题地图着色问题 把无环图g的结点皆染上颜色，且使相邻的结点颜色不同，又所用的颜色最少，称这个颜色数为g的色数

29、，记为 。 定理 设g为无环图，则 ，其中 是g中结点的最大度数。 1976年，appel和haken用计算机证明了下面的 四色定理四色定理 若g是平面图，则 。 g 1g 4g数学建模中的图论方法数学建模中的图论方法-其他问题其他问题(1) 考试日程问题: 选修课考试安排时,要避免任何一位学生所选不同课程在同一天考,问最少几天才能完成? 数学模型: 以每门课程为结点,仅当两门课程被同一位学生选修时,在这两个结点之间连上一条边,构作一个图g,求取 即为所求。 g(2) 存储安全问题: 某公司生产若干种化学制品,其中有些制品如果放在一起可能发生化学反应,引起危险.因此公司必须把仓库分成相互隔离的若干区.问至少要划分多少小区,才可安全存放? 数学模型: 以每种货物为结点,仅当两种货物放在一起不够安全时,在这两个结点之间连上一条边,如此得到的图g的色数 即为所求。 g数学建模中的图论方法数学建模中的图论方法-其他问题其他问题(3) 频率分配问题: 地面上有若干无线电发射台,对每台分配一个频率供其使用,频率用自然数从1起编号,称