數學題庫下載題庫

柯尼斯堡七橋問題（Seven Bridges of Königsberg）是圖論中的著名問題。這個問題是基於一個現實生活中的事例：當時東普魯士柯尼斯堡（今日俄羅斯加里寧格勒）市區跨普列戈利亞河兩岸，河中心有兩個小島。小島與河的兩岸有七條橋連接。在所有橋都只能走一遍的前提下，如何才能把這個地方所有的橋都走遍？

萊昂哈德·歐拉在1735年提出，並沒有方法能圓滿解決這個問題，他更在第二年發表在論文《柯尼斯堡的七橋》中，證明符合條件的走法並不存在，也順帶提出和解決了一筆畫問題^[1]。這篇論文在聖彼得堡科學院發表，成為圖論史上第一篇重要文獻。歐拉把實際的抽象問題簡化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區視為點。這樣若...

柯尼斯堡七橋問題（Seven Bridges of Königsberg）是圖論中的著名問題。這個問題是基於一個現實生活中的事例：當時東普魯士柯尼斯堡（今日俄羅斯加里寧格勒）市區跨普列戈利亞河兩岸，河中心有兩個小島。小島與河的兩岸有七條橋連接。在所有橋都只能走一遍的前提下，如何才能把這個地方所有的橋都走遍？

萊昂哈德·歐拉在1735年提出，並沒有方法能圓滿解決這個問題，他更在第二年發表在論文《柯尼斯堡的七橋》中，證明符合條件的走法並不存在，也順帶提出和解決了一筆畫問題^[1]。這篇論文在聖彼得堡科學院發表，成為圖論史上第一篇重要文獻。歐拉把實際的抽象問題簡化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區視為點。這樣若從某點出發後最後再回到這點，則這一點的線數必須是偶數，這樣的點稱為偶頂點。相對的，連有奇數條線的點稱為奇頂點。歐拉論述了，由於柯尼斯堡七橋問題中存在4個奇頂點，它無法實現符合題意的遍歷。

 →  → 

歐拉把問題的實質歸於一筆畫問題，即判斷一個圖是否能夠遍歷完所有的邊而沒有重複，而柯尼斯堡七橋問題則是一筆畫問題的一個具體情境。歐拉最後給出任意一種河──橋圖能否全部走一次的判定法則，從而解決了「一筆畫問題」。對於一個給定的連通圖，如果存在兩個以上（不包括兩個）奇頂點，那麼滿足要求的路線便不存在了，且有n個奇頂點的圖至少需要n/2筆畫出。如果只有兩個奇頂點，則可從其中任何一地出發完成一筆畫。若所有點均為偶頂點，則從任何一點出發，所求的路線都能實現，他還說明了怎樣快速找到所要求的路線。^[1]

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

1. ^.0 1.1