柯尼斯堡七桥问题
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/5/5d/Konigsberg_bridges.png/300px-Konigsberg_bridges.png)
柯尼斯堡七桥问题(德语:Königsberger Brückenproblem;英语:Seven Bridges of Königsberg)是图论中的著名问题。这个问题是基于一个现实生活中的事例:当时东普鲁士柯尼斯堡(今日俄罗斯加里宁格勒)市区跨普列戈利亚河两岸,河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下,如何才能把这个地方所有的桥都走遍?
解决方式
莱昂哈德·欧拉在1735年提出,并没有方法能圆满解决这个问题,他更在第二年发表在论文《柯尼斯堡的七桥》中,证明符合条件的走法并不存在,也顺带提出和解决了一笔画问题[1]。这篇论文在圣彼得堡科学院发表,成为图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合,每一座桥视为一条线,桥所连接的地区视为点。这样若从某点出发后最后再回到这点,则这一点的线数必须是偶数,这样的点称为偶顶点。相对的,连有奇数条线的点称为奇顶点。欧拉论述了,由于柯尼斯堡七桥问题中存在4个奇顶点,它无法实现符合题意的遍历。
欧拉把问题的实质归于一笔画问题,即判断一个图是否能够遍历完所有的边而没有重复,而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。欧拉最后给出任意一种河──桥图能否全部走一次的判定法则,从而解决了“一笔画问题”。对于一个给定的连通图,如果存在超过两个的奇顶点,那么满足要求的路线便不存在了,且在n>0的情况下,有2n个奇顶点的图至少需要n笔画出。如果只有两个奇顶点,则可从其中任何一地出发完成一笔画。若所有点均为偶顶点,则从任何一点出发,所求的路线都能实现,他还说明了怎样快速找到所要求的路线。[1]
不少数学家都尝试去解析这类事例。而这些解析,最后发展成为了数学中的图论。
现在的七座桥
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Present_state_of_the_Seven_Bridges_of_K%C3%B6nigsberg.png/220px-Present_state_of_the_Seven_Bridges_of_K%C3%B6nigsberg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Old_cathedral_of_Kaliningrad_in_Russia.jpg/220px-Old_cathedral_of_Kaliningrad_in_Russia.jpg)
这七座桥之中,有两座已经在二战时的大轰炸中被损毁,另外两座则被改建成快速公路。其馀三座则原址保留,当中又有一座于1935年被重建[2]。换言之,欧拉当时的七座桥,现在只剩下五座,令奇顶点只剩下两个,所以可以一次过走完五座桥[3]。而从欧拉时代保存至今的就只有两座。
资料来源
- ^ 1.0 1.1 Janet Heine Barnett, Early Writings on Graph Theory: Euler Circuits and The KÄonigsberg Bridge Problem (页面存档备份,存于互联网档案馆)
- ^ Taylor, Peter. What Ever Happened to Those Bridges?. Australian Mathematics Trust. December 2000 [11 November 2006]. (原始内容存档于19 March 2012).
- ^ Stallmann, Matthias. The 7/5 Bridges of Koenigsberg/Kaliningrad. July 2006 [11 November 2006]. (原始内容存档于2008-12-01).