图论的起源和发展.pdf

《图论的起源和发展.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、大众文艺大理论研究图论的起源和发展李冰（河北省唐山第五中学063000）摘要：图论是数学领域中发展最快的分支之一，数学史上著名试求从图中的任一点出发，通过每条边一次，最后返回到该的七桥问题欧拉只用了一步就证明了不重复地通过7座桥的路线是根点，这样的路径是否存在？于是问题就变得简洁明了多了，同时也本不存在的！这是拓扑学研究的先声。图的染色问题一直是图论研究更一般、更深刻。这样一来，七桥问题就转变为图论中的一个一笔的焦点问题。数学家赫伍德（Hedwood）成功地运用肯普的方法证明画问题。即能不能一笔不重复的画出图1．1(b)中的这个图形。了五色定理，即一张地图能够用五种或者更少的颜色染色。美国

2、伊利原先人们是要求找出一条不重复的路线，欧拉想，成千上万诺斯大学的黑肯（W.Haken）和阿佩尔（Appel），经过四年的艰苦的人都失败了，这样的路线也许根本不存在。于是，欧拉接下来工作，终于完成了四色猜想的证明。正是上述那些似乎没有多大意义着手判断：这样不重复的路线究竟存不存在？由于这么改变了一的游戏的抽象与论证的方法，开创了图论科学的研究。下提问的角度，欧拉抓住了问题的实质。最后，欧拉认真考虑了关键词：团论；染色体；四色猜想一笔画图形的结构特征。欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：图论是组合数学的—个分支，与其他的数学分支，如群论、每当用笔画一条线进入中间的一个点时，还

3、必须画一条线离开这矩阵论、概率论、拓扑学、数值分析等有着密切的联系（参见文个点。否则，整个图形就不可能用一笔画出。也就是说，单独考献[1]）。图论中以图为研究对象，图形中我们用点表示对象，察图中的任何一点（起点和终点除外），这个点都应该与偶数条两点之间的连线表示对象之间的某种特定的关系。事实上，任何线相连；如果起点与终点重合，那么，连这个点也应该与偶数条一个包含了某种二元关系的系统都可以用图形来模拟，而且它具线相连。有形象直观的特点。由于我们感兴趣的是两对象之间是否有某在七桥问题的几何图中，A、B、D三点分别与3条线相连，C种特定关系，所以图形中两点间连接与否尤为重要，而图形的位点与5条线

4、相连。连线都是奇数条。因此，欧拉断定：一笔画出置、大小、形状及连接线的曲直长短则无关紧要。这个图形是不可能的。也就是说，不重复地通过7座桥的路线是20世纪后，图论的应用渗透到许多其他学科领域。从20世根本不存在的！天才的欧拉只用了一步就证明了这个难题，从这纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发里我们也可以看到图论的威力有多么的强大！展，使图论成为数学领域中发展最快的分支之一。欧拉对七桥问题的研究，是拓扑学研究的先声。一、图论的起源1750年，欧拉又发现了一个有趣的的现象。欧拉得到了后人图论是一个古老的但又十分活跃的数学学科，也是一门很以他的名字命名的“多面体欧拉公式”。

5、正4面体有4个顶点、6有实用价值的学科，它在自然科学、社会科学等各领域均有很多条棱，它的面数加顶点数减去棱数等于2；正6面体有8个顶点、应用。近年来它受计算机科学蓬勃发展的刺激，发展极其迅速。12条棱，它的面数加顶点数减去棱数也等于2。接着，欧拉又考应用范围不断拓广，已渗透到诸如语言学、逻辑学、物理学、化察了正12面体、正24面体，发现都有相同的结论。于是继续深入学、电讯工程、计算机科学以及数学的其它分支中。研究这个问题，终于发现了一个著名的定理：1736年是图论的历史元年。这一年，欧拉（L•Euler）研究了哥尼斯堡城（Königsberg）的七桥问题，发表了图论的首篇论这个公式证明了多

6、面体只有正四面体、正六面体、正八面文。欧拉也因此被称为图论之父。体、正十二面体、正二十面体五种。这个定理成为拓扑学的第一古老而美丽的哥尼斯堡城濒临蓝色的波罗的海，是著名的个定理，这个公式被认为开启了数学史上新的一页，促成了拓扑哲学家康德（ImmanuelKant）的出生地，城中有一条普莱格尔学的发展。（Pregel）河，河的两条支流在这里汇合，然后横穿全城，流入二、图论的发展大海。河水把城市分成4块，于是，人们建造了7座各具特色的从19世纪中叶开始，图论进入第二个发展阶段。这一时期桥，把哥尼斯堡城连成一体，如图1．1(a)所示。图论问题大量出现，诸如关于地图染色的四色问题、由“周游世早在1

7、8世纪，这些形态各异的小桥吸引了众多的游客，游人界”游戏发展起来的哈密顿(W.Hamilton)问题等。在陶醉于美丽风光的同时，不知不觉间，脚下的桥触发了人们的图的染色问题一直是图论研究的焦点问题。最早记载染色问灵感，一个有趣的问题在居民中传开。题的是英国伦敦大学（UniversityofLondon）的数学教授德•摩根（D.Morgan）。A1852年，一位刚从伦敦大学毕业的学生费南西斯•古色利（F.Guthrie）在