加载中…
个人资料
天天天蓝
天天天蓝
  • 博客等级:
  • 博客积分:0
  • 博客访问:18,333
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

图论的产生和发展经历了二百多年的历史

(2006-09-15 10:38:35)

图论的产生和发展经历了二百多年的历史,大体上可分为三个阶段:

第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)

东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒,在波罗的海南岸)位于普雷格尔(Pregel)河的两岸,河中有一个岛,于是城市被河的分支和岛分成了四个部分,各部分通过7座桥彼此相通。如同德国其他城市的居民一样,该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题:从四部分陆地任一块出发,按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。

哥尼斯堡七桥问题看起来不复杂,因此立刻吸引所有人的注意,但是实际上很难解决。

瑞士数学家(Leonhard Euler)1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文,Euler也因此被誉为图论之父。

欧拉把七桥问题抽象成数学问题---一笔画问题,并给出一笔画问题的判别准则,从而判定七桥问题不存在解。Euler是这样解决这个问题的:将四块陆地表示成四个点,桥看成是对应结点之间的连线,则哥尼斯堡七桥问题就变成了:从ABCD任一点出发,通过每边一次且仅一次返回原出发点的路线(回路)是否存在?Euler证明这样的回路是不存在的。

第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题:迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852)Hamilton环游世界问题(1856)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络方程组的研究。1857年英国的凯莱(A.Cayley)也独立地提出了树的概念,并应用于有机化合物的分子结构的研究中。1936年匈牙利的数学家哥尼格(D.Konig)写出了第一本图论专著《有限图与无限图的理论》(Theory of directed and Undirected Graphs)。标志着图论作为一门独立学科。

第三阶段是1936年以后。由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现,大大促进了图论的发展。特别是电子计算机的大量应用,使大规模问题的求解成为可能。实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的,需要计算机的帮助才有可能进行分析和解决。目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用。

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:汇率
后一篇:句子的种类
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇汇率
    后一篇 >句子的种类
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有