PDF《图论中的经典问题简介》

orld of Mathematics 数学烟云 W 数学文化/第3卷第2期67 图论是一门古老的数学分支,主要研究用某种方式 联系起来的若干事物之间的二元或多元关系.

关于图论 的文字记载最早出现在欧拉

1736 年的论著中,即著名的 哥尼斯堡七桥问题.图论中很多重要的结果都是在

19 世 纪得到的,大部分都跟电子网络相联系(电子工程可能 是图论成功运用的第一个领域) .直到

1936 年匈牙利数 学家 Konig 出版了第一本图论专著《有限图与无限图的 理论》 ,图论才以一个独立的数学学科出现在人们的视野 中.目前,由于研究方法和内容的不同,图论已产生了 若干分支,如代数图论、极值图论、随机图论、拓扑图论、 应用图论等.

20 世纪中叶以后,由于生产管理、军事、交通运输、 计算机网络等领域的需要,出现了很多的离散问题,而 图论可为离散问题的研究提供数学模型.近代电子计算 机的出现和发展,促使图论及其应用迅猛发展.图论与 线性规划、动态规划等优化理论的内容和方法相互渗透, 促进了组合优化理论和算法的研究.图论的引进改变了 计算机科学、网络等领域的面貌.当前应用图论来解决 化学、物理学、生物学、运筹学、网络理论、信息论、 控制论、经济学、社会科学等学科的问题,已显示出极 大的优越性.同时,对图论中古老问题以及经典问题(如 最短路问题、旅行售货商问题、中国邮递员问题等)的 研究,促进了图论本身的发展.著名数学家金芳蓉教授 在《信息时代的图论》 (Graph Theory in the Information Age, 2010)一文中指出 : 图论发展正处于一个新的征程, 成为信息革命的核心部分. 著名数学家、沃尔夫奖获得者 Lovasz 教授在《图论

45 年的发展》 (Graph Theory Over

45 Years,2011)一 文中写道 : 在过去的十年里,图论已经变得越来越重 要,无论是它的应用还是它跟数学其他分支的紧密联系 方面. 在文章中,通过对图论跟组合优化(离散优化) 、 计算机科学、概率论、代数、拓扑、网络等其他学科之 间联系的描述,详细地回答了 今天图论在数学中占有 什么样的地位? 这一问题. 本文我们将简单的介绍图论中的几个经典的问题. 1. 哥尼斯堡七桥问题 风景秀丽的哥尼斯堡城(今俄罗斯加里宁格勒)是德 国的一座历史名城,也是哥德巴赫的出生地.普莱格尔 河贯穿整个哥尼斯堡小城,这条河有两条支流,它们环 绕一个小岛,在这两条支流上有七座桥(见下图)将岛 与河岸连接.城里的居民晚饭后喜欢到这里散步,久而 久之,就有了这样一个问题 :一个人怎样才能一次走遍 七座桥,每座桥只走过一次,最后回到出发点?大家都 试图找出问题的答案,但是谁也解决不了这个问题. 于是问题就被送到了正在俄国圣彼得堡 (原列宁格勒) 的科学院做研究的大数学家欧拉手里.1736 年29 岁的欧 拉向圣彼得堡科学院递交了 《哥尼斯堡的七座桥》 的论文. 欧拉并没有跑到哥尼斯堡去走走,他将陆地和小岛用点表 示,而将七座桥用线表示,于是七桥问题就等价于下图中 图形的一笔画问题了.欧拉用严格的数学方法证明了这种 画法是不存在的.对于类似的更一般的图形,欧拉也找到 了一个简便的原则,可以判定它能否一笔画出 : ? ? ? 图论中的经典问题简介 史永堂 orld of Mathematics 数学烟云 W 数学文化/第3卷第2期68 它们是连通的, 且奇顶点 ( 通过此点边的条数是奇数 ) 的个数为