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

《图论发展和在现实生活中几个的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.图论的发展及其在生活中的应用数学与应用数学张佳丽指导教师刘秀丽摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。关键词图论生活问题应用GraphTheoryDevelopmentandtheApplicationinLifeMathematicsandappliedmathematicsZhangJialiTutorLiuXiul

2、iAbstractThispapermainlyintroducestheoriginanddevelopmentofgraphtheoryanditsseveralapplicationsinourlife,suchas:crossingriverproblem,travelingsalesmanproblem,minimumspanningtreeproblem,fourcolorproblem，arrangementproblem，Chinesepostmanproblem．Italsoresearches

3、severalmethodsthataremorewidelyappliedingraphtheory,forexample:themethodofmostneighboring,themethodofsolvingtheminimumspanningtree，themethodofthebestroute，andsoon．Keywordsgraphtheorylifeproblemapplication引言图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分

4、析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。从20世纪5

5、0年代以后，由于计算机的迅速发展，有力地推动了图论的发展，加速了图论向各个学科的渗透，尤其是网络理论的建立，图论与线性规划、动态规划等优化理论和方法互相渗透。同时，计算机的发展......使图论成为数学领域中发展最快的分支之一．1图论的起源与发展1．1图论的起源[1]1736年是图论的历史元年．这一年，欧拉（L•Euler）研究了哥尼斯堡（Königsberg）七桥问题，并发表了关于图论的首篇文章．欧拉也因此被称为图论之父．哥尼斯堡城濒临蓝色的波罗的海，城中有一条普莱格尔（Pregel）河，河的两条支流在这里汇合

6、，然后横穿全城，流入大海．河水把城市分成4块，于是，人们建造了7座各具特色的桥，把哥尼斯堡城连成一体，如图一所示．早在18世纪，这些形态各异的小桥吸引了众多的游客，他们在陶醉于美丽风光的同时，不知不觉间，脚下的桥触发了人们的灵感，一个有趣的问题在居民中传开．图一图二谁能够从两岸A，B，C，D四个陆地中的任一个地方出发一次走遍所有的7座桥，而且每座桥都无重复的只通过一次？这个问题看起来似乎不难，谁都乐意用这个问题来测试一下自己的智力．但是，谁也没有找到一条这样的路线．这个问题极大的刺激了人们的好奇心，许多人都热衷于

7、解决这个问题，然而始终没有人能够成功．“七桥问题”难住了哥尼斯堡城的所有居民．哥尼斯堡城也因“七桥问题”而出了名．......这就是数学史上著名的七桥问题．问题看来并不复杂，但就是谁也解决不了，也说不出所以然来．1736年，当时著名的数学家欧拉仔细研究了这个问题，他将上述四块陆地与七座桥间的关系用一个抽象图形来描述(见图二)，其中A、B、C、D四个陆地分别用四个点来表示，而陆地之间有桥相连者则用连接两个点的连线来表示，这样，上述的哥尼斯堡七桥问题就变成了由点和边所组成的如下问题：试求从图中的任一点出发，不重复的通

8、过每条边一次，最后返回到该点，这样的路线是否存在？这样问题就变得简洁明了了，同时问题也变得更一般、更深刻了．这样，七桥问题就转变为图论中的一笔画问题．即能不能不重复的一笔画出图二中的这个图形．原先人们是要求找出一条不重复的路线，欧拉想，既然成千上万的人都失败了，那么这样的路线也许根本就不存在．于是，欧拉就想：这样不重复的路线究竟存不存在？由于改变了一下提问的角度，欧拉抓住