图论的发展及其在现实生活中的几个应用

菏泽学院本科生毕业设计（论文）图论的发展及其在生活中的应用数学与应用数学 张佳丽指导教师 刘秀丽摘要 主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。关键词 图论 生活 问题 应用Graph Theory Development and the Application in LifeMathematics and applied mathematics Zhang Jiali Tutor Liu XiuliAbstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problemIt also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so onKey words graph theory life problem application引言图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系事实上，任何一个包含了二元关系的系统都可以用图论来模拟而且,图论能把纷杂的信息变的有序、直观、清晰由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要图论在自然科学、社会科学等各个领域都有广泛的应用随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支之一1 图论的起源与发展11 图论的起源11736年是图论的历史元年这一年，欧拉（LEuler）研究了哥尼斯堡（Knigsberg）七桥问题，并发表了关于图论的首篇文章欧拉也因此被称为图论之父哥尼斯堡城濒临蓝色的波罗的海，城中有一条普莱格尔（Pregel）河，河的两条支流在这里汇合，然后横穿全城，流入大海河水把城市分成4块，于是，人们建造了7座各具特色的桥，把哥尼斯堡城连成一体，如图一所示早在18世纪，这些形态各异的小桥吸引了众多的游客，他们在陶醉于美丽风光的同时，不知不觉间，脚下的桥触发了人们的灵感，一个有趣的问题在居民中传开图一图二谁能够从两岸A，B， C，D四个陆地中的任一个地方出发一次走遍所有的7座桥，而且每座桥都无重复的只通过一次？这个问题看起来似乎不难，谁都乐意用这个问题来测试一下自己的智力但是，谁也没有找到一条这样的路线这个问题极大的刺激了人们的好奇心，许多人都热衷于解决这个问题，然而始终没有人能够成功“七桥问题” 难住了哥尼斯堡城的所有居民哥尼斯堡城也因“七桥问题” 而出了名这就是数学史上著名的七桥问题问题看来并不复杂，但就是谁也解决不了，也说不出所以然来1736年，当时著名的数学家欧拉仔细研究了这个问题，他将上述四块陆地与七座桥间的关系用一个抽象图形来描述(见图二)，其中A、B、C、D四个陆地分别用四个点来表示，而陆地之间有桥相连者则用连接两个点的连线来表示，这样，上述的哥尼斯堡七桥问题就变成了由点和边所组成的如下问题：试求从图中的任一点出发，不重复的通过每条边一次，最后返回到该点，这样的路线是否存在？这样问题就变得简洁明了了，同时问题也变得更一般、更深刻了这样，七桥问题就转变为图论中的一笔画问题即能不能不重复的一笔画出图二中的这个图形原先人们是要求找出一条不重复的路线，欧拉想，既然成千上万的人都失败了，那么这样的路线也许根本就不存在于是，欧拉就想：这样不重复的路线究竟存不存在？由于改变了一下提问的角度，欧拉抓住了问题的实质最后，欧拉认真考虑了一笔画图形的结构特征欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：每当画一条线进入中间的一个点时，还必须画一条线离开这个点否则，这个图形就不可能用一笔画出也就是说，单独考察图中的任何一点（起点和终点除外），这个点都应该与偶数条线相连；如果起点与终点重合，那么，连这个点也应该与偶数条线相连在七桥问题的几何图中，A、B、D三点分别与3条线相连，C点与5条线相连连线数都是奇数条因此，欧拉断定：一笔画出这个图形是不可能的也就是说，不重复地通过7座桥的路线是根本不存在的！天才的欧拉只用了一步就证明了这个难题，从这里我们也可以看到图论的强大威力.欧拉对七桥问题的研究，是拓扑学研究的先声1750年，欧拉又发现了一个有趣的的现象欧拉因此得到了后人以他的名字命名的“多面体欧拉公式”正4面体有4个顶点、6条棱，它的面数加顶点数减去棱数等于2；正6面体有8个顶点、12条棱，它的面数加顶点数减去棱数也等于2接着，欧拉又考察了正12面体、正24面体，发现都有相同的结论于是继续深入研究这个问题，终于发现了一个著名的定理：(面数) (顶点数) (棱数) 2这个公式证明了多面体只有正四面体、正六面体、正八面体、正十二面体、正二十面体五种这个定理成为拓扑学的第一个定理，这个公式被认为开启了数学史上新的一页，促成了拓扑学的发展12 图论的发展图论的产生和发展经历了二百多年的历史，大体上可以分为三个阶段：第一阶段是从1736年到19世纪中叶当时的图论问题是盛行的迷宫问题和游戏问题最具代表性的工作是著名数学家欧拉于1736年解决的哥尼斯堡七桥问题(见11)第二阶段是从19世纪中叶到1936年图论主要研究一些游戏问题:迷宫问题、博弈问题、棋盘上马的行走路线问题等，2随着对这些问题的深入研究，图论又产生了新的一系列问题，例如：连通性、嵌入问题、染色问题、矩阵表示以及网络流等连通性是图论研究的基本问题之一，欧拉路、中国邮路问题、哈密顿问题、树与图的支撑树、匹配问题都是连通性的典型问题；地图着色问题即是对无论多么复杂的地图，只需用四种颜色就足够将相邻的区域分开平面图的染色问题是与四色问题紧密相联的于是产生了着色问题即给定一个图，如果要求把所有顶点涂上颜色，使得相邻顶点具有不同的颜色，问最少需要几种不同的颜色?这个问题叫做图的点着色问题如果对给定图的全部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色?这个问题叫做边的着色问题，边的着色问题可以转化为点着色问题由这些问题人们逐渐丰富并发展了图论学科知识同时出现了以图为工具去解决其他领域中一些问题的成果1847年德国的克希霍夫将树的概念和理论应用于工程技术的电网路方程组的研究1936年匈牙利的数学家哥尼格写出了第一本图论专著有限图与无限图的理论标志着图论成为了一门独立学科第三阶段是1936年以后.由于生产管理、军事、交通运输、计算机和通讯网路等方面大量实际问题的出现，大大促进了图论的发展特别是电子计算机的大量应用，使大规模问题的求解成为可能实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都很复杂的，需要计算机的帮助才有可能进行分析和解决目前，图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中都有应用2 图论在生活中几种应用21 渡河问题211 基本理论定义2.13 有向图：一个有向图是一个有序的二元组，记作，其中（1）称为顶点集，其元素称为顶点或结点（2）为边集，它是笛卡尔积的多重子集，其元素称为有向边，简称边212 应用举例例4 （渡河问题） 一个摆渡人要把一只狼，一只羊和一捆菜运过河去，由于船很小，每次摆渡人至多只能带一样东西另外，如果人不在旁时，狼就要吃羊，羊就要吃菜问这个人怎样才能安全的将它们运过河去？解 用表示摆渡人，表示狼，表示羊，表示菜若用表示人和其他三样东西在河的原岸的状态，这样原岸全部可能出现的状态为以下16种： 表示原岸什么也没有，即人、狼、羊、菜都运到河对岸了根据题意，我们知道这16种情况中有6种是不允许的，它们是、，如表示人和菜在原岸而狼和羊在对岸，这当然是不允许的因此，允许出现的情况只有10种以这10种状态为结点，以摆渡前原岸的一种状态与摆渡一次后出现在原岸的状态所对应的结点之间的连线为边，作有向图2.1：图2.1上图给出了两种方案，方案为上图中从到的不同的基本通路： 它们的长度均为7故摆渡人只需摆渡7次就能将它们全部运到对岸，并且羊和菜完好无损22 旅行推销员问题该问题是说：“给定个城市和它们之间的距离，问如何设计一条路线，使得一个推销员从他所在的城市出发途经其余个城市刚好一次，最后回到原驻地并使得行程最短5？”221 基本理论定义2.26 给定图（为无向图或有向图），设：（为实数集），对中任意的边 ( 为有向图时，)，设，称实数为边上的权，并将标注在边上，称为带权图，此时常将带权图记作设，称为的权，记作，即=最邻近法7(1)由任意选择的结点开始，找与该点最近（即权最小）的点，形成有一条边的初始路径(2)设表示最新加到这条路上的结点，从不在路上的所有结点中选一个与最靠近的结点，把连接与这一结点的边加到这条路上，重复这一步，直到中所有结点包含在路上(3)将连接起始点与最后加入的结点之间的边加到这条路上，就得到一个圈，即为问题的近似解222 应用举例例8 某流动售票员居住在城，为推销货物他要访问、城后返回城，若该四城间的距离如下图2.2所示，找出完成该访问的最短路线图2.2解 步骤如下图最短距离为：8+6+7+11=3223 最小生成树231 基本理论定义2.3.19 设，为两个图（同为无向图或同为有向图），若且，则称是的子图，为的母图，记作又若或，则称为的真子图，若，则称为的生成子图定义2.3.210 不含圈的连通图称为树定义2.3.311 如果是的一个生成子图而且又是一棵树，则称是图的一棵生树定义2.3.412 设无向连通带权图，是的一棵生成树，的各边权之和称为的权的所有生成树中，权最小的生成树称为的最小生成树破圈法13在中任取一个圈，去掉其中一条边，然后再取一个圈，再去掉这个圈中的一条边，如此继续下去，最后得到的连通图的无圈的生成子图就是的一棵生成树用破圈法求带权的最小生成树的方法在赋权图中任取一个圈，然后去掉这个圈中权最大的边，如此继续进行直到中不再有圈时为止，这时剩下的边组成的子图就是最小树14232 应用举例旅游线路中的最短问题 对于旅客来说，要求在最短的时间内用最少的钱来旅游最多的景点，考虑到无论采取哪种方案，在门票的花费均相同且路费在速度恒定的情况下可由路程的多少来求得，从而把问题转化为求最短的旅游路线的问题15例16 公园的路径系统图如图2.3，其中为入口，为出口，为五个景点，现求如何能使观光旅游车从入口到出口所经过的距离最短图2.3 解 用破圈法求带权的最小生成树的方法求解，求解步骤如下图 由图可知，从如口到出口的最短路径为最短距离为：2+2+3+1+5=1324 四色问题1852年10月23日英国数学家德摩根写给当时还属于英国的爱尔兰数学家哈密尔顿的一封信中，他写道：“我的一位学生今天请我解释一个我过去不知道，现在仍不甚了了的事实他说任意划分一个地图并给各部分着上颜色，使任何具有公共边界的部分颜色不同，那么需要且仅需要四种颜色就够了”德摩根提到的这位学生名叫弗雷德里克格里斯而据他后来撰文披露，该问题的真正发现者实际是他是的哥哥弗兰西斯格里斯172.4.1 基本理论定义2.4.118 设为无向标定图，中的顶点与边的交替序列 称为到的通路，其中，为的端点，=1,2, ， ，分别称为的始点与终点，中边的条数称为它的长度，若 =，则称通路为回路若的所有边各异，则称为简单通路，又若=，则称为简单回路若的所有顶点（除 与可能相同外）各异，所有边也各异，则称为初级通路或路径，此时又若=，则称为初级回路或圈，将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈定义2.4.219 对无环图的每个顶点涂上一种颜色，使相邻的顶点涂不同的颜色，称为对图的一种着色若能用种颜色给的顶点着色，就称对进行了着色，也称是可着色的若是可着色的，但不是可着色的，就称是色图，并称这样的为的色数，记作 定义2.4.320 在（4）边形内放置一个顶点，使这个顶点与上的所有顶点均相邻，所得阶简单图称为阶轮图为奇数的轮图称为奇阶轮图，为偶数的轮图称为偶阶轮图定理2.4.1（四色定理）21 每个平面的色数至多是4定理2.4.219 奇圈和奇阶轮图的色数均为3，而偶阶轮图的色数为4242 应用举例例122 在期末考试周期间，一所学院的8名选修数学的学生得到许可去参加大学生科研讨论会假设他们回来之后需要在星期一对所错过的考试进行补考，星期一安排这些考试的可能时间段为：8:0010:00 10:1512:15 12:302:302:454:45 5:007:00 7:159:15应用图论的相关知识，确定这8名学生完成考试的最早时间要求：如果有某个学生必须要参加某两门课的考试，那么，这两门课程就不能安排在同一时间段内这8名学生以及他们选修的课程：高等微积分（）、微分方程（）、几何学（）、图论（）、线性规划（）、近世代数（）、统计学（）、拓扑学（），列表如下： ：， ：， ：， ：， ：， ：， ：， ：，解 首先构造图2.4.1，其顶点为这8门课程，如果有某个学生同时考两门课程则在这两个顶点间连一条边1、2、3、4表示四种不同的颜色，如1表示用第一种颜色着色记最小的时间段数为，由于中含有奇圈，由定理2知，需要3种颜色为该图上的顶点着色由于与该图上的所有顶点都邻接，所以需要用第四种颜色来为染色因此4；又由定理1知4，因而4图2.4.1故在四个时间段内可安排这8门课程的考试，安排方法为：时间段1：统计学、几何学、图论 时间段2：高等微积分、拓扑学时间段3：微分方程、近世代数 时间段4：线性规划故可在安排时间段(1) 8:0010:00 (2) 10:1512:15 (3) 12:302：30 (4) 2:454:45故完成考试的最短时间为4:45例222 有8种化学药品需要空运飞越整个国家.运费根据运送的容器数量来确定.运送一个容器需要125元.某些药品之间可以发生化学反应,所以把它们放在同一个容器中是很危险的.这些化学药品被标记成, ,.下面列出的是与某个给定药品能够发生反应的其他药品名称:, : , : , : , : , : ,: , : ,这些化学药品应该如何放置于那些容器中使得运送这些化学药品所需的费用最少?最少是多少?解 首先构造图2.4.2,其顶点为这8种化学药品.如果某两种药品能发生化学反应就在这两个顶点间连一条边.1，2，3，4表示四种不同的颜色，如1表示用第一种颜色着色记最小的容器数为，由于中含有奇圈,，,由定理2知，需要3种颜色为该图上的顶点着色由于与该图上的所有顶点都邻接，所以需要用第四种颜色来为染色因此4；又由定理1知4，因而4图2.4.2故将这8种化学药品放置在四个容器内,安排方法为：第一个容器: , 第二个容器: ,第三个容器: , 第四个容器: ,最少费用为4125500. 25 用边染色解决安排问题2.5.1 基本理论定义2.5.123 非空图的一个边染色是指给的边分配颜色，每条边分配一种颜色，使得邻接的边分配不同的颜色对的边染色所需的最少颜色数称为是边色数，记为应用种颜色的边染色称为是边染色定义2.5.224 设为一无向图，称作为边的端点次数之和为的度数，简记为度，记作，在不发生混淆时，简记为 定理2.5.123 对于任意非空图，或者定理2.5.223 设是一个阶为，边数为的图若则2.5.2 应用举例例123 ()曾邀请3对夫妇到他的避暑别墅住一个星期,他们是 ()和 (), ()和 (), ()和 ()由于这6位客人都喜欢网球运动,所以他决定进行一些网球比赛6位客人中的每一位都要与其配偶之外的每位客人比赛另外, 将分别与, , , 进行一场比赛若没有人在同一天进行两场比赛,则要在最少天数完成比赛,该如何安排?解 首先构造图2.5.1,其顶点为住在的避暑别墅的人,因此, 中的两个顶点是邻接的,如果这两个顶点(人)需要进行一场比赛为了解答这个问题,我们需要确定的边色数图2.5.1易见, 根据定理251, 或者此外, 的阶为,边数为由于由定理252,可知图列出了的一个6边染色,从而也给出了一个具有最少天数(6)的时间安排表第一天: 第二天: 第三天: 第四天: 第五天: 第六天: 例225来自亚特兰大、波士顿、芝加哥、丹佛、路易维尔、迈阿密以及纳什维尔的7支垒球队受邀请参加比赛，其中每只队都被安排与一些其他队比赛，如下：亚特兰大（）：波士顿，芝加哥，迈阿密，纳什维尔波士顿（）：亚特兰大，芝加哥，纳什维尔芝加哥（）：亚特兰大，波士顿，丹佛，路易维尔丹佛()：芝加哥，路易维尔，迈阿密，纳什维尔路易维尔()：芝加哥，丹佛，迈阿密迈阿密()：亚特兰大，丹佛，路易维尔，纳什维尔纳什维尔()：亚特兰大，波士顿，丹佛，迈阿密每支队在同一天最多只能进行一场比赛。建立一个具有最少天数的比赛时间表.解 首先构造图2.5.2,其顶点为7支球队,因此, 中的两个顶点是邻接的,如果这两个顶点需要进行一场比赛为了解答这个问题,我们需要确定的边色数图2.5.2易见, 根据定理251, 或者此外, 的阶为,边数为由于由定理252,可知图列出了的一个5边染色,从而也给出了一个具有最少天数(5)的时间安排表第一天：亚特兰大波士顿纳什维尔迈阿密芝加哥路易维尔第二天：波士顿纳什维尔亚特兰大芝加哥丹佛路易维尔第三天：亚特兰大迈阿密芝加哥波士顿丹佛纳什维尔第四天：芝加哥丹佛路易维尔迈阿密亚特兰大纳什维尔第五天：丹佛迈阿密2.6 中国邮递员问题中国邮递员问题即为邮递员路线问题邮递员从邮局出发,经过他所投递范围的每一条街道至少一次,完成邮件的投递任务以后返回邮局如何安排邮递员的行走路线,以使总路程最短,这个问题是中国学者管梅谷1962年首先提出,并给出了一个解法,被国际上称为中国邮递员问题2.6.1 基本理论定义2.6.126 在图上,从某个顶点出发,对各条边只通过一次,这样的迹称为迹闭迹叫做环游一个图若包含环游,则这个图称为图定义2.6.227 将边的两个端点再用一条权同样为的新边连接，即得重复边定理2.6.1 27 若是图，则中任意用Fleury算法做出的迹都是上午环游定理2.6.227 设赋权图经添加重复边集后得到赋权欧拉图，重复边集权值总和最小的充要条件是：每条边最多重复一次，并且中任一个圈，其所含重复边的权值之和都不大于所在圈中所有边权值的二分之一算法27 :(1) 任意选取一个顶点,置；(2) 假设迹已经选定，那么按下述方法从中选取边：1）和相关联；2）除非没有别的边可选择，否则不是的割边(3)当2）不能再执行时，算法停止，得到中一条迹非图求最优环游的算法步骤27 ：(1)开始任给一个初始方案，使非赋权图各顶点变为偶点，得到一个初始赋权图；(2)检查检查各圈是否满足圈中“重复边总权值小于等于非重复边总权值”的最优解条件若条件已满足，则现行方案为最优解，再由算法得到一条最优环游，否则转（3）；(3)调整调整重复边并保持图仍为赋权图转（2）262应用举例例28 设邮递员所辖的投递区如下图2.6所示，其中边旁的数字为街道长度，问从邮局出发，如何走遍全区各街最后回到邮局而又最短的路径图2.6解 ，故此图为非欧拉图添加重复边使其变为欧拉图，如下图2.6.1，经检查所有圈皆符合定理262，故下图为最优方案图2.6.1按算法可得到一条最优环游,这条最优环游是: . 参考文献1李冰图论的起源和发展J大众文艺，2010（9）：342黄会芸图论思想在生活中的运用J赤峰学院学报（自然科学版），2009,25(12):23-243耿素云、屈婉玲离散数学M2版北京：高等教育出版社，2004:2674傅彦离散数学基础及应用M成都：电子科技大学出版社，2000：1491505程钊图论中若干著名问题的历史标记J数学的实践与认识，2009，39（24）：75 6耿素云、屈婉玲离散数学M2版北京：高等教育出版社，2004:302 7乔维声、汤惟离散数学M西安：西安电子科技大学出版社，2005:157 8乔维声、汤惟 离散数学M西安：西安电子科技大学出版社，2005:1589耿素云、屈婉玲离散数学M2版北京：高等教育出版社，2004:27410王朝瑞图论M3版北京：北京理工大学出版社，2002:2611王朝瑞图论M3版北京：北京理工大学出版社，2002:3312耿素云、屈婉玲离散数学M2版北京：高等教育出版社，2004:31113王朝瑞图论M3版北京：北京理工大学出版社，2002:3414王朝瑞图论M3版北京：北京理工大学出版社，2002:23215方冬云图论在旅游路线选择中的应用J长春工业大学学报（自然科学版），2009,30（5）：58316刘海英最短路径问题在管理中的应用J福建广播电视大学学报,2010，4（29）：8717程钊图论中若干著名问题的历史标记J数学的实践与认识，2009，39（24）：78 18耿素云、屈婉玲离散数学M2版北京：高等教育出版社，2004:27619耿素云、屈婉玲离散数学M2版北京：高等教育出版社，2004:33320耿素云、屈婉玲离散数学M2版北京：高等教育出版社，2004:332 21Gary Chartrand、Ping Zhang图论导引M范益政等，译北京：人民邮电出版社，2007：23722Gary Chartrand、Ping Zhang图论导引M范益政，朱明，龚世才等译北京：人民邮电出版社，2007：24624723 Gary Chartrand、Ping Zhang图论导引M范益政，朱明，龚世才等译北京：人民邮电出版社，2007：24825024耿素云、屈婉玲离散数学M2版北京：高等教育出版社，2004:26925 Gary Chartrand、Ping Zhang图论导引M范益政，朱明，龚世才等译北京：人民邮电出版社，2007：255.26刘缵武应用图论M长沙：国防科技大学出版社，2004：8327刘缵武应用图论M长沙：国防科技大学出版社，2004：858728刘缵武应用图论M长沙：国防科技大学出版社，2004：97致谢在此论文撰写过程中，要特别感谢我的导师刘秀丽老师的指导与督促。刘秀丽老师对该论文从选题，构思到最后定稿的各个环节都给予细心指导和不懈的支持,使我得以最终完成毕业论文设计。此外，本文最终得以顺利完成，也是与数学系其他老师的帮助分不开的，虽然他们没有直接参与我的论文指导，但在这个过程中却给我提供了不少的意见，提出了一系列可行性的建议，在此向他们表示深深的感谢！最后再一次感谢所有在毕业设计中曾经帮助过我的良师益友和同学，以及在设计中被我引用或参考的论著的作者。19