1、菏泽学院本科生毕业设计（论文）1图论的发展及其在生活中的应用数学与应用数学 张佳丽指导教师 刘秀丽摘要 主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。关键词 图论 生活 问题 应用Graph Theory Development and the Application in LifeMathematics and applied mathematics Zhang JialiTutor Liu XiuliAbst
2、ract 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
3、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引言图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系图论中以
4、图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系事实上，任何一个包含了二元关系的系统都可以用图论来模拟而且,图论能把纷杂的信息变的有序、直观、清晰由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要图论在自然科学、社会科学等各个领域都有广泛的应用随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从 20 世纪 50 年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论
5、与线性规划、张佳丽：图论的发展及其在生活中的应用2动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支之一1 图论的起源与发展11 图论的起源 11736年是图论的历史元年这一年，欧拉（LEuler）研究了哥尼斯堡（Knigsberg）七桥问题，并发表了关于图论的首篇文章欧拉也因此被称为图论之父哥尼斯堡城濒临蓝色的波罗的海，城中有一条普莱格尔（Pregel）河，河的两条支流在这里汇合，然后横穿全城，流入大海河水把城市分成4块，于是，人们建造了7座各具特色的桥，把哥尼斯堡城连成一体，如图一所示早在18世纪，这些形态各异的小桥吸引了众多的游客，他们在陶醉于美丽风光
6、的同时，不知不觉间，脚下的桥触发了人们的灵感，一个有趣的问题在居民中传开图一图二谁能够从两岸A，B， C，D四个陆地中的任一个地方出发一次走遍所有的7座桥，而且每座桥都无重复的只通过一次？这个问题看起来似乎不难，谁都乐意用这个问题来测试一下自己的智力但是，谁也没有找到一条这样的路线这个问题极大的刺激了人们的好奇心，许多人都热衷于解决这个问题，然而始终没有人能够成功“七桥菏泽学院本科生毕业设计（论文）3问题” 难住了哥尼斯堡城的所有居民哥尼斯堡城也因“七桥问题” 而出了名这就是数学史上著名的七桥问题问题看来并不复杂，但就是谁也解决不了，也说不出所以然来1736年，当时著名的数学家欧拉仔细研究了这
7、个问题，他将上述四块陆地与七座桥间的关系用一个抽象图形来描述(见图二)，其中A、B、C、D四个陆地分别用四个点来表示，而陆地之间有桥相连者则用连接两个点的连线来表示，这样，上述的哥尼斯堡七桥问题就变成了由点和边所组成的如下问题：试求从图中的任一点出发，不重复的通过每条边一次，最后返回到该点，这样的路线是否存在？这样问题就变得简洁明了了，同时问题也变得更一般、更深刻了这样，七桥问题就转变为图论中的一笔画问题即能不能不重复的一笔画出图二中的这个图形原先人们是要求找出一条不重复的路线，欧拉想，既然成千上万的人都失败了，那么这样的路线也许根本就不存在于是，欧拉就想：这样不重复的路线究竟存不存在？由于改
8、变了一下提问的角度，欧拉抓住了问题的实质最后，欧拉认真考虑了一笔画图形的结构特征欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：每当画一条线进入中间的一个点时，还必须画一条线离开这个点否则，这个图形就不可能用一笔画出也就是说，单独考察图中的任何一点（起点和终点除外），这个点都应该与偶数条线相连；如果起点与终点重合，那么，连这个点也应该与偶数条线相连在七桥问题的几何图中，A、B、D三点分别与3条线相连，C点与5条线相连连线数都是奇数条因此，欧拉断定：一笔画出这个图形是不可能的也就是说，不重复地通过7座桥的路线是根本不存在的！天才的欧拉只用了一步就证明了这个难题，从这里我们也可以看到图论的强大
9、威力.欧拉对七桥问题的研究，是拓扑学研究的先声1750年，欧拉又发现了一个有趣的的现象欧拉因此得到了后人以他的名字命名的“多面体欧拉公式”正4面体有4个顶点、6条棱，它的面数加顶点数减去棱数等于2；正6面体有8个顶点、12条棱，它的面数加顶点数减去棱数也等于2接着，欧拉又考察了正12面体、正24面体，发现都有相同的结论于是继续深入研究这个问题，终于发现了一个著名的定理：(面数) (顶点数) (棱数) 2FVE张佳丽：图论的发展及其在生活中的应用4这个公式证明了多面体只有正四面体、正六面体、正八面体、正十二面体、正二十面体五种这个定理成为拓扑学的第一个定理，这个公式被认为开启了数学史上新的一页，
10、促成了拓扑学的发展12 图论的发展图论的产生和发展经历了二百多年的历史，大体上可以分为三个阶段：第一阶段是从 1736 年到 19 世纪中叶当时的图论问题是盛行的迷宫问题和游戏问题最具代表性的工作是著名数学家欧拉于 1736 年解决的哥尼斯堡七桥问题(见11)第二阶段是从 19 世纪中叶到 1936 年图论主要研究一些游戏问题:迷宫问题、博弈问题、棋盘上马的行走路线问题等， 2随着对这些问题的深入研究，图论又产生了新的一系列问题，例如：连通性、嵌入问题、染色问题、矩阵表示以及网络流等连通性是图论研究的基本问题之一，欧拉路、中国邮路问题、哈密顿问题、树与图的支撑树、匹配问题都是连通性的典型问题；
11、地图着色问题即是对无论多么复杂的地图，只需用四种颜色就足够将相邻的区域分开平面图的染色问题是与四色问题紧密相联的于是产生了着色问题即给定一个图，如果要求把所有顶点涂上颜色，使得相邻顶点具有不同的颜色，问最少需要几种不同的颜色?这个问题叫做图的点着色问题如果对给定图的全部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色?这个问题叫做边的着色问题，边的着色问题可以转化为点着色问题由这些问题人们逐渐丰富并发展了图论学科知识同时出现了以图为工具去解决其他领域中一些问题的成果1847 年德国的克希霍夫将树的概念和理论应用于工程技术的电网路方程组的研究1936 年匈牙利的数学家哥尼格写出了第一本图
12、论专著有限图与无限图的理论标志着图论成为了一门独立学科第三阶段是 1936 年以后.由于生产管理、军事、交通运输、计算机和通讯网路等方面大量实际问题的出现，大大促进了图论的发展特别是电子计算机的大量应用，使大规模问题的求解成为可能实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都很复杂的，需要计算机的帮助才有可能进行分析和解决目前，图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中都有应用2 图论在生活中几种应用菏泽学院本科生毕业设计（论文）521 渡河问题211 基本理论定义 2.13 有向图：一个有
13、向图是一个有序的二元组 ，记作 ，其中,VED（1） 称为顶点集，其元素称为顶点或结点V（2） 为边集，它是笛卡尔积 的多重子集，其元素称为有向边，简称边EV212 应用举例例 4 （渡河问题） 一个摆渡人要把一只狼，一只羊和一捆菜运过河去，由于船很小，每次摆渡人至多只能带一样东西另外，如果人不在旁时，狼就要吃羊，羊就要吃菜问这个人怎样才能安全的将它们运过河去？解 用 表示摆渡人， 表示狼， 表示羊， 表示菜FWSC若用 表示人和其他三样东西在河的原岸的状态，这样原岸全部可能出现的状WSC态为以下 16 种：FFSSFSCCCWS表示原岸什么也没有，即人、狼、羊、菜都运到河对岸了根据题意，我们
14、知道这 16 种情况中有 6 种是不允许的，它们是 、WSC、 、 、 、 ，如 表示人和菜在原岸而狼和羊在对岸，这当然是不允FCSFC许的因此，允许出现的情况只有 10 种以这 10 种状态为结点，以摆渡前原岸的一种状态与摆渡一次后出现在原岸的状态所对应的结点之间的连线为边，作有向图 2.1：FSSFSWWFSCCFWCWCFWSC图 2.1上图给出了两种方案，方案为上图中从 到 的不同的基本通路：C张佳丽：图论的发展及其在生活中的应用6 FWSCFCSFS W它们的长度均为 7 故摆渡人只需摆渡 7 次就能将它们全部运到对岸，并且羊和菜完好无损22 旅行推销员问题该问题是说：“给定 个城市
15、和它们之间的距离，问如何设计一条路线，使得一n个推销员从他所在的城市出发途经其余 个城市刚好一次，最后回到原驻地并使得1n行程最短 5？”221 基本理论定义 2.26 给定图 （ 为无向图或有向图） ，设 ： （ 为实,GVEWER数集） ，对 中任意的边 ( 为有向图时， )，设 ，称ijev,ijeveijw实数 为边 上的权，并将 标注在边 上，称 为带权图，此时常将带权图 记作ijweijweGG设 ，称 为 的权，记作 ，即 = ,VEWeEGWeE最邻近法 7(1)由任意选择的结点开始，找与该点最近（即权最小）的点，形成有一条边的初始路径(2)设 表示最新加到这条路上的结点，从不
16、在路上的所有结点中选一个与 最X X靠近的结点，把连接 与这一结点的边加到这条路上，重复这一步，直到 中所有结G点包含在路上(3)将连接起始点与最后加入的结点之间的边加到这条路上，就得到一个圈，即为问题的近似解222 应用举例例 8 某流动售票员居住在 城，为推销货物他要访问 、 、 城后返回 城，ABCDA若该四城间的距离如下图 2.2 所示，找出完成该访问的最短路线菏泽学院本科生毕业设计（论文）7CDBA 671681311图 2.2解 步骤如下图CDBA 8CDBA 68CDBA 678张佳丽：图论的发展及其在生活中的应用8CDBA 67811最短距离为：8+6+7+11=3223 最小
17、生成树231 基本理论定义 2.3.19 设 ， 为两个图（同为无向图或同为有向图） ，,GVE,若 且 ，则称 是 的子图， 为 的母图，记作 又若 或，VEGGV则称 为 的真子图，若 ，则称 为 的生成子图定义 2.3.210 不含圈的连通图称为树定义 2.3.311 如果 是 的一个生成子图而且又是一棵树，则称 是图 的一T T棵生树定义 2.3.412 设无向连通带权图 ， 是 的一棵生成树， 的各边,GVEWTG权之和称为 的权 的所有生成树中，权最小的生成树称为 的最小生成树TG破圈法 13在 中任取一个圈，去掉其中一条边，然后再取一个圈，再去掉这个圈中的一条边，如此继续下去，最
18、后得到的连通图的无圈的生成子图就是 的一棵生成树G用破圈法求带权的最小生成树的方法在赋权图 中任取一个圈，然后去掉这个圈中权最大的边，如此继续进行直到G中不再有圈时为止，这时剩下的边组成的子图就是最小树 14232 应用举例旅游线路中的最短问题 对于旅客来说，要求在最短的时间内用最少的钱来旅游最多的景点，考虑到无论采取哪种方案，在门票的花费均相同且路费在速度恒定的情况下可由路程的多少来求得，从而把问题转化为求最短的旅游路线的问题 15例 16 公园的路径系统图如图 2.3，其中 为入口， 为出口， ， ， ， ，STABCD菏泽学院本科生毕业设计（论文）9为五个景点，现求如何能使观光旅游车从入口 到出口 所经过的距离最短E STBETDACS751431427452图 2.3解 用破圈法求带权的最小生成树的方法求解，求解步骤如下图BETDACS75143142742BETDACS7514314272张佳丽：图论的发展及其在生活中的应用10BETDACS751431422BETDACS75131422BETDACS7513122BETDACS513122由图可知，从如口 到出口 的最短路径为STSABDT
