哥尼斯堡七桥问题

1、 七桥问题 1736年29岁的欧拉向圣彼得堡科 学院递交了哥尼斯堡的七座桥 的论文，在解答问题的同时，开创 了数学的一个新的分支图论与几 何拓扑，也由此展开了数学史上的 新历程。 莱昂哈德欧拉 莱昂哈德欧拉，瑞士数学家、自然科学家。1707年4月15日出生 于瑞士的巴塞尔，1783年9月18日于俄国圣彼得堡去世。欧拉出生 于牧师家庭，自幼受父亲的影响。13岁时入读巴塞尔大学，15岁 大学毕业，16岁获得硕士学位。欧拉是18世纪数学界最杰出的人 物之一，他不但为数学界作出贡献，更把整个数学推至物理的领 域。他是数学史上最多产的数学家，平均每年写出八百多页的论 文，还写了大量的力学、分析学、几何学

2、、变分法等的课本， 无穷小分析引论、微分学原理、积分学原理等都成 为数学界中的经典著作。欧拉对数学的研究如此之广泛，因此在 许多数学的分支中也可经常见到以他的名字命名的重要常数、公 式和定理。 此外欧拉还涉及建筑学、弹道学、航海学等领域。瑞 士教育与研究国务秘书查尔斯克莱伯曾表示：“没有欧拉的众 多科学发现，今天的我们将过着完全不一样的生活。”法国数学 家拉普拉斯则认为：读读欧拉，他是所有人的老师。 2007年，为 庆祝欧拉诞辰300周年，瑞士政府、中国科学院及中国教育部于 2007年4月23日下午在北京的中国科学院文献情报中心共同举办纪 念活动，回顾欧拉的生平、工作以及对现代生活的影响。 提

3、出时间 18世纪著名古典数学问题之一。在哥尼斯堡的一个公园 里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起 来(如图)。问是否可能从这四块陆地中任一块出发，恰 好通过每座桥一次，再回到起点？欧拉于1736年研究并 解决了此问题，他把问题归结为如右图的“一笔画”问 题，证明上述走法是不可能的。 有关图论研究的热点问题。18世纪初普鲁士的哥尼斯堡， 有一条河穿过，河上有两个小岛，有七座桥把两个岛与 河岸联系起来（如右上图）。有个人提出一个问题：一 个步行者怎样才能不重复、不遗漏地一次走完七座桥， 最后回到出发点。后来大数学家欧拉把它转化成一个几 何问题（如左图下）一笔画问题。他不仅解决了此 问题

4、，且给出了连通图可以一笔画的充要条件是：奇点 的数目不是0 个就是2 个（连到一点的数目如是奇数条， 就称为奇点，如果是偶数条就称为偶点，要想一笔画成， 必须中间点均是偶点，也就是有来路必有另一条去路， 奇点只可能在两端，因此任何图能一笔画成，奇点要么 没有要么在两端） 推断方法 当欧拉在1736年访问哥尼斯堡时，他发现当地的市 民正从事一项非常有趣的消遣活动。哥尼斯堡城中 有一条名叫普雷格尔河流横经其中，这项有趣的消 遣活动是在星期六作一次走过所有七座桥的散步， 每座桥只能经过一次而且起点与终点必须是同一地 点。 欧拉把每一块陆地考虑成一个点，连接两块陆地的 桥以线表示。 后来推论出此种走法

5、是不可能的。他的论点是这样 的，除了起点以外，每一次当一个人由一座桥进入 一块陆地（或点）时，他（或她）同时也由另一座 桥离开此点。所以每行经一点时，计算两座桥（或 线），从起点离开的线与最后回到始点的线亦计算 两座桥，因此每一个陆地与其他陆地连接的桥数必 为偶数。 最终成果 1736年，在经过一年的研究之后，29岁的欧拉提交了哥 尼斯堡七桥的论文，圆满解决了这一问题，同时开创了 数学新一分支-图论。 在论文中，欧拉将七桥问题抽象出来，把每一块陆地考虑 成一个点，连接两块陆地的桥以线表示。并由此得到了如 图一样的几何图形。 若我们分别用a、b、c、d四个点表 示为哥尼斯堡的四个区域。这样著名的

6、“七桥问题”便转 化为是否能够用一笔不重复的画出过此七条线的问题了。 若可以画出来，则图形中必有终点和起点，并且起点和终 点应该是同一点，由于对称性可知由b或c为起点得到的效 果是一样的，若假设以a为起点和终点，则必有一离开线 和对应的进入线，若我们定义进入a的线的条数为入度， 离开线的条数为出度，与a有关的线的条数为a的度，则a 的出度和入度是相等的，即a的度应该为偶数。即要使得 从a出发有解则a的度数应该为偶数，而实际上a的度数是5 为奇数，于是可知从a出发是无解的。同时若从b或d出发， 由于b、d的度数分别是3、3，都是奇数，即以之为起点都 是无解的 七桥问题和欧拉定理 欧拉通过对七桥问题的研究，不仅圆满地回答了哥尼斯堡居民提出的问 题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称 之为 欧拉定理。对于一个连通图，通常把从某结点出发一笔画成所经 过的路线叫做欧拉路。人们又通常把一笔画成回到出发点的欧拉路叫做 欧拉回路。具有欧拉回路的图叫做欧拉图。 一笔画 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起 点，最后一