柯尼斯堡七桥问题

柯尼斯堡七桥问题（德語：Königsberger Brückenproblem；英語：Seven Bridges of Königsberg）是图论中的著名问题。这个问题是基於一個現實生活中的事例：當時東普魯士柯尼斯堡（今日俄羅斯加里寧格勒）市区跨普列戈利亚河两岸，河中心有兩個小島。小島與河的兩岸有七條橋連接。在所有橋都只能走一遍的前提下，如何才能把这个地方所有的橋都走遍？

歐拉時代的柯尼斯堡地圖，顯示了當時七座橋的實際位置。河流和橋樑使用特別的顏色標記出來。

解決方式

莱昂哈德·欧拉在1735年提出，並沒有方法能圓滿解決這個問題，他更在第二年发表在论文《柯尼斯堡的七桥》中，證明符合条件的走法並不存在，也順帶提出和解決了一筆畫問題^[1]。这篇论文在聖彼得堡科學院發表，成为圖論史上第一篇重要文獻。歐拉把實際的抽象問題簡化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區視為點。這樣若從某點出發後最後再回到這點，則這一點的線數必須是偶數，这样的点称为偶顶点。相对的，连有奇数条线的点称为奇顶点。欧拉论述了，由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历。

  →   →  

欧拉把问题的实质归于一笔画问题，即判断一个图是否能够遍历完所有的边而没有重复，而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。歐拉最後給出任意一種河──橋圖能否全部走一次的判定法則，从而解决了“一笔画问题”。对于一个给定的连通图，如果存在超過两个的奇顶点，那么滿足要求的路線便不存在了，且有n个奇顶点的图至少需要 ${\displaystyle \lceil {\frac {n}{2}}\rceil }$  笔画出。如果只有兩個奇顶点，則可從其中任何一地出發完成一笔画。若所有点均为偶顶点，則從任何一点出發，所求的路線都能實現，他還說明了怎樣快速找到所要求的路線。^[1]

不少數學家都嘗試去解析這类事例。而這些解析，最後發展成為了數學中的圖論。

現在的七座橋

 

現在的加里寧格勒地圖，綠色表示現存的橋樑，紅色表示已毀損的橋樑。

 

圖中柯尼斯堡主教座堂旁邊的橋是兩條自歐拉時代保存至今的橋樑之一。

這七座橋之中，有兩座已經在二戰時的大轟炸（英语：bombing of Königsberg in World War II）中被損毀，另外兩座則被改建成快速公路。其餘三座則原址保留，當中又有一座於1935年被重建^[2]。換言之，歐拉當時的七座橋，現在只剩下五座，令奇頂點只剩下兩個，所以可以一次過走完五座橋^[3]。而從歐拉時代保存至今的就只有兩座。

资料来源

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