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

菏泽学院本科生毕业设计（论文）1图论的发展及其在生活中的应用数学与应用数学张佳丽指导教师刘秀丽摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。关键词图论生活问题应用GraphTheoryDevelopmentandtheApplicationinLifeMathematicsandappliedmathematicsZhangJialiTutorLiuXiuliAbstractThispapermainlyintroducestheoriginanddevelopmentofgraphtheoryanditsseveralapplicationsinourlife,suchas:crossingriverproblem,travelingsalesmanproblem,minimumspanningtreeproblem,fourcolorproblem，arrangementproblem，Chinesepostmanproblem．Italsoresearchesseveralmethodsthataremorewidelyappliedingraphtheory,forexample:themethodofmostneighboring,themethodofsolvingtheminimumspanningtree，themethodofthebestroute，andsoon．Keywordsgraphtheorylifeproblemapplication引言图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展使图论成为数学领域中发展最快的分支之一．张佳丽：图论的发展及其在生活中的应用21图论的起源与发展1．1图论的起源[1]1736年是图论的历史元年．这一年，欧拉（L•Euler）研究了哥尼斯堡（Königsberg）七桥问题，并发表了关于图论的首篇文章．欧拉也因此被称为图论之父．哥尼斯堡城濒临蓝色的波罗的海，城中有一条普莱格尔（Pregel）河，河的两条支流在这里汇合，然后横穿全城，流入大海．河水把城市分成4块，于是，人们建造了7座各具特色的桥，把哥尼斯堡城连成一体，如图一所示．早在18世纪，这些形态各异的小桥吸引了众多的游客，他们在陶醉于美丽风光的同时，不知不觉间，脚下的桥触发了人们的灵感，一个有趣的问题在居民中传开．图一图二谁能够从两岸A，B，C，D四个陆地中的任一个地方出发一次走遍所有的7座桥，而且每座桥都无重复的只通过一次？这个问题看起来似乎不难，谁都乐意用这个问题来测试一下自己的智力．但是，谁也没有找到一条这样的路线．这个问题极大的刺激了人们的好奇心，许多人都热衷于解决这个问题，然而始终没有人能够成功．“七桥问题”难住了哥尼斯堡城的所有居民．哥尼斯堡城也因“七桥问题”而出了名．这就是数学史上著名的七桥问题．菏泽学院本科生毕业设计（论文）3问题看来并不复杂，但就是谁也解决不了，也说不出所以然来．1736年，当时著名的数学家欧拉仔细研究了这个问题，他将上述四块陆地与七座桥间的关系用一个抽象图形来描述(见图二)，其中A、B、C、D四个陆地分别用四个点来表示，而陆地之间有桥相连者则用连接两个点的连线来表示，这样，上述的哥尼斯堡七桥问题就变成了由点和边所组成的如下问题：试求从图中的任一点出发，不重复的通过每条边一次，最后返回到该点，这样的路线是否存在？这样问题就变得简洁明了了，同时问题也变得更一般、更深刻了．这样，七桥问题就转变为图论中的一笔画问题．即能不能不重复的一笔画出图二中的这个图形．原先人们是要求找出一条不重复的路线，欧拉想，既然成千上万的人都失败了，那么这样的路线也许根本就不存在．于是，欧拉就想：这样不重复的路线究竟存不存在？由于改变了一下提问的角度，欧拉抓住了问题的实质．最后，欧拉认真考虑了一笔画图形的结构特征．欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：每当画一条线进入中间的一个点时，还必须画一条线离开这个点．否则，这个图形就不可能用一笔画出．也就是说，单独考察图中的任何一点（起点和终点除外），这个点都应该与偶数条线相连；如果起点与终点重合，那么，连这个点也应该与偶数条线相连．在七桥问题的几何图中，A、B、D三点分别与3条线相连，C点与5条线相连．连线数都是奇数条．因此，欧拉断定：一笔画出这个图形是不可能的．也就是说，不重复地通过7座桥的路线是根本不存在的！天才的欧拉只用了一步就证明了这个难题，从这里我们也可以看到图论的强大威力.欧拉对七桥问题的研究，是拓扑学研究的先声．1750年，欧拉又发现了一个有趣的的现象．欧拉因此得到了后人以他的名字命名的“多面体欧拉公式”．正4面体有4个顶点、6条棱，它的面数加顶点数减去棱数等于2；正6面体有8个顶点、12条棱，它的面数加顶点数减去棱数也等于2．接着，欧拉又考察了正12面体、正24面体，发现都有相同的结论．于是继续深入研究这个问题，终于发现了一个著名的定理：F(面数)＋V(顶点数)－E(棱数)＝2这个公式证明了多面体只有正四面体、正六面体、正八面体、正十二面体、正二十面体五种．这个定理成为拓扑学的第一个定理，这个公式被认为开启了数学史上新的一张佳丽：图论的发展及其在生活中的应用4页，促成了拓扑学的发展．1．2图论的发展图论的产生和发展经历了二百多年的历史，大体上可以分为三个阶段：第一阶段是从1736年到19世纪中叶．当时的图论问题是盛行的迷宫问题和游戏问题．最具代表性的工作是著名数学家欧拉于1736年解决的哥尼斯堡七桥问题(见1．1)．第二阶段是从19世纪中叶到1936年．图论主要研究一些游戏问题:迷宫问题、博弈问题、棋盘上马的行走路线问题等，[2]随着对这些问题的深入研究，图论又产生了新的一系列问题，例如：连通性、嵌入问题、染色问题、矩阵表示以及网络流等．连通性是图论研究的基本问题之一，欧拉路、中国邮路问题、哈密顿问题、树与图的支撑树、匹配问题都是连通性的典型问题；地图着色问题即是对无论多么复杂的地图，只需用四种颜色就足够将相邻的区域分开．平面图的染色问题是与四色问题紧密相联的．于是产生了着色问题即给定一个图，如果要求把所有顶点涂上颜色，使得相邻顶点具有不同的颜色，问最少需要几种不同的颜色?这个问题叫做图的点着色问题．如果对给定图的全部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色?这个问题叫做边的着色问题，边的着色问题可以转化为点着色问题．由这些问题人们逐渐丰富并发展了图论学科知识．同时出现了以图为工具去解决其他领域中一些问题的成果．1847年德国的克希霍夫将树的概念和理论应用于工程技术的电网路方程组的研究．1936年匈牙利的数学家哥尼格写出了第一本图论专著《有限图与无限图的理论》．标志着图论成为了一门独立学科．第三阶段是1936年以后.由于生产管理、军事、交通运输、计算机和通讯网路等方面大量实际问题的出现，大大促进了图论的发展．特别是电子计算机的大量应用，使大规模问题的求解成为可能．实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都很复杂的，需要计算机的帮助才有可能进行分析和解决．目前，图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中都有应用．2图论在生活中几种应用2．1渡河问题2．1．1基本理论定义2.1[3]有向图：一个有向图是一个有序的二元组,VE，记作D，其中菏泽学院本科生毕业设计（论文）5（1）V称为顶点集，其元素称为顶点或结点．（2）E为边集，它是笛卡尔积VV的多重子集，其元素称为有向边，简称边．2．1．2应用举例例[4]（渡河问题）一个摆渡人要把一只狼，一只羊和一捆菜运过河去，由于船很小，每次摆渡人至多只能带一样东西．另外，如果人不在旁时，狼就要吃羊，羊就要吃菜．问这个人怎样才能安全的将它们运过河去？解用F表示摆渡人，W表示狼，S表示羊，C表示菜若用FWSC表示人和其他三样东西在河的原岸的状态，这样原岸全部可能出现的状态为以下16种：FWSCFWSFWCFSCWSCFWFSFCWSWCSCFWSC表示原岸什么也没有，即人、狼、羊、菜都运到河对岸了根据题意，我们知道这16种情况中有6种是不允许的，它们是WSC、FW、FC、WS、SC、F，如FC表示人和菜在原岸而狼和羊在对岸，这当然是不允许的．因此，允许出现的情况只有10种．以这10种状态为结点，以摆渡前原岸的一种状态与摆渡一次后出现在原岸的状态所对应的结点之间的连线为边，作有向图2.1：FSSFSWWFSCCFWCWCFWSCΦ图2.1上图给出了两种方案，方案为上图中从FWSC到的不同的基本通路：⑴FWSCWCFWCCFSCSFS⑵FWSCWCFWCWFWSSFS．它们的长度均为7故摆渡人只需摆渡7次就能将它们全部运到对岸，并且羊和菜完好无损．张佳丽：图论的发展及其在生活中的应用62．2旅行推销员问题该问题是说：“给定n个城市和它们之间的距离，问如何设计一条路线，使得一个推销员从他所在的城市出发途经其余1n个城市刚好一次，最后回到原驻地并使得行程最短[5]？”2．2．1基本理论定义2.2[6]给定图,GVE（G为无向图或有向图），设W：ER（R为实数集），对G中任意的边,ijevv(G为有向图时，,ijevv)，设Weijw，称实数ijw为边e上的权，并将ijw标注在边e上，称G为带权图，此时常将带权图G记作,,VEW．设GG，称eEGWe为G的权，记作WG，即WG=eEGWe．最邻近法[7](1)由任意选择的结点开始，找与该点最近（即权最小）的点，形成有一条边的初始路径．(2)设X表示最新加到这条路上的结点，从不在路上的所有结点中选一个与X最靠近的结点，把连接X与这一结点的边加到这条路上，重复这一步，直到G中所有结点包含在路上．(3)将连接起始点与最后加入的结点之间的边加到这条路上，就得到一个圈，即为问题的近似解．2．2．2应用举例例[8]某流动售票员居住在A城，为推销货物他要访问B、C、D城后返回A城，若该四城间的距离如下图2.2所示，找出完成该访问的最短路线．CDBA671681311图2.2解步骤如下图①—④菏泽学院本科生毕业设计（论文）7CDBA8①CDBA68②CDBA678③CDBA67811④最短距离为：8+6+7+11=32．2．3最小生成树2．3．1基本理论定义2.3.1[9]设,GVE，,GVE为两个图（同为无向图或同为有向图），张佳丽：图论的发展及其在生活中的应用8若VV且EE，则称G是G的子图，G为G的母图，记作GG．又若VV或，EE则称G为G的真子图，若VV，则称G为G的生成子图．定义2.3.2[10]不含圈的连通图称为树．定义2.3.3[11]如果T是G的一个生成子