柯尼斯堡七桥问题
![](http://178.128.105.246/cars-http-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://178.128.105.246/cars-http-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://178.128.105.246/cars-http-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).