柯尼斯堡七橋問題(Seven Bridges of Konigsberg)是圖論中的著名問題,也是世界上第一個圖論問題,這個問題是基于一個現實生活中的事例:當時東普魯士柯尼斯堡(今日俄羅斯加裡甯格勒)市區跨普列戈利亞河兩岸,河中心有兩個小島。小島與河的兩岸有七條橋連接配接。在所有橋都隻能走一遍的前提下,如何才能把這個地方所有的橋都走遍?
柯尼斯堡平面圖(部分)
問題提出後,很多人對此很感興趣,紛紛進行試驗,但在相當長的時間裡,始終未能解決。利用普通數學知識,每座橋均走一次,那這七座橋所有的走法一共有5040種,這麼多情況,要一一試驗,會是很大的工作量。但怎麼才能找到成功走過每座橋而不重複的路線呢?因而形成了著名的“柯尼斯堡七橋問題”。
1735年,有幾名大學生寫信給當時正在俄羅斯的彼得斯堡科學院任職的天才數學家歐拉,請他幫忙解決這一問題。
1736年29歲的歐拉送出了《柯尼斯堡七橋》的論文,圓滿解決了這一問題,同時開創了數學新分支--->圖論!
歐拉把問題的實質歸于"一筆畫"問題,即判斷一個圖是否能夠周遊完所有的邊而沒有重複,而柯尼斯堡七橋問題則是一筆畫問題的一個具體情境。
抽象"七橋"
上圖右側部分,已進行了抽象,線代表橋,五邊形代表陸地(與陸地相連"橋的數量"用數字表示);
"一筆畫問題"規則抽象:
1.由于不能重複過橋,是以每經過一條線,就必須把剛剛經過的線擦掉;
2.我們每經過一次五角形,此五角形會擦去兩條邊;
3.五角形是我們的起點,也是終點!
綜上,"一筆畫問題"必須滿足的條件(二選一):