柯尼斯堡七桥问题

柯尼斯堡七桥问题（德语：Königsberger Brückenproblem；英语：Seven Bridges of Königsberg）是图论中的著名问题。这个问题是基于一个现实生活中的事例：当时东普鲁士柯尼斯堡（今日俄罗斯加里宁格勒）市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？

欧拉时代的柯尼斯堡地图，显示了当时七座桥的实际位置。河流和桥梁使用特别的颜色标记出来。

解决方式

莱昂哈德·欧拉在1735年提出，并没有方法能圆满解决这个问题，他更在第二年发表在论文《柯尼斯堡的七桥》中，证明符合条件的走法并不存在，也顺带提出和解决了一笔画问题[1]。这篇论文在圣彼得堡科学院发表，成为图论史上第一篇重要文献。欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数，这样的点称为偶顶点。相对的，连有奇数条线的点称为奇顶点。欧拉论述了，由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历。

  →   →  

欧拉把问题的实质归于一笔画问题，即判断一个图是否能够遍历完所有的边而没有重复，而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。欧拉最后给出任意一种河──桥图能否全部走一次的判定法则，从而解决了“一笔画问题”。对于一个给定的连通图，如果存在超过两个的奇顶点，那么满足要求的路线便不存在了，且有n个奇顶点的图至少需要   笔画出。如果只有两个奇顶点，则可从其中任何一地出发完成一笔画。若所有点均为偶顶点，则从任何一点出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。[1]

不少数学家都尝试去解析这类事例。而这些解析，最后发展成为了数学中的图论。

现在的七座桥

 
现在的加里宁格勒地图，绿色表示现存的桥梁，红色表示已毁损的桥梁。
 
图中柯尼斯堡主教座堂旁边的桥是两条自欧拉时代保存至今的桥梁之一。

这七座桥之中，有两座已经在二战时的大轰炸（英语：bombing of Königsberg in World War II）中被损毁，另外两座则被改建成快速公路。其余三座则原址保留，当中又有一座于1935年被重建[2]。换言之，欧拉当时的七座桥，现在只剩下五座，令奇顶点只剩下两个，所以可以一次过走完五座桥[3]。而从欧拉时代保存至今的就只有两座。

资料来源

  1. ^ 1.0 1.1 Janet Heine Barnett, Early Writings on Graph Theory: Euler Circuits and The KÄonigsberg Bridge Problem （页面存档备份，存于互联网档案馆）
  2. ^ Taylor, Peter. What Ever Happened to Those Bridges?. Australian Mathematics Trust. December 2000 [11 November 2006]. （原始内容存档于19 March 2012）. 
  3. ^ Stallmann, Matthias. The 7/5 Bridges of Koenigsberg/Kaliningrad. July 2006 [11 November 2006]. （原始内容存档于2008-12-01）.