七橋問題 Seven Bridges Problem

七橋問題 Seven Bridges Problem

  這個問題是被卡羅戈特利布·依勒(Carl Gottlieb Ehler, 1685–1753)這個人發現的,他是一個數學家,同時也是哥德尼斯堡(Königsberg)附近小鎮的準鎮長。哥德尼斯堡(Königsberg)這個小城鎮很有趣,城鎮裡被普瑞格爾河(Pregel River)貫穿,同時還包含了兩座小島在河中,並且有七座橋在小島的周圍使他們與河岸連接。這位數學家從小就常常在附近遊玩,並且對於這兩個小島和這些橋樑瞭若指掌,但是有一個問題一直困擾著他:是否有可能找出一條路線,可以達成在每座橋只經過一次的情況下經過所有的橋?1736年,當年29歲的數學家尤拉(Euler, 1707-1783)收到了卡羅的信,終於證明了七橋問題是無解的。

 

觀察可以一次走完的圖形和不能一次走完的圖形,有什麼不一樣的特性?

試試看自己動手設計題目,將會有意想不到的收穫!

 

原理思考

為什麼將圖形上的頂點分成奇數點和偶數點,可以證明這個圖形能否一筆畫完成?七橋問題為什麼沒有解?

 

尤拉在解決這個問題的時候,將圖形上的頂點分成奇數及偶數點,顧名思義,奇數點的意思就是,通過點上的線段數量是奇數;相對的,偶數點則代表通過點上的線段數量是偶數。尤拉發現奇數點的數量只能是0或是2。原因是因為偶數點連接的線段(路徑)有偶數條,為了符合線段不重複的規則,有進就要有出,一進一出剛好是2條(或是2的倍數)線段;奇數點則扣除有進有出的線段(等同於偶數點),還需要再加上一條線段,而在這條線段上的方向性,就決定了這個奇數點是一筆劃的終點或是起點。而終點或起點在一筆劃的規則中顯然只能各有一個,這就是為什麼奇數點的數量只能是0或2了。

符合尤拉圖原則的圖形,其偶數點上的路徑都是一進一出,成雙成對。
new七橋 01

符合尤拉圖原則的圖形,其奇數點如果最後一條路徑是出去,代表這一個奇數點是起點;相反的,如果最後一條路徑是進來,代表這一個奇數點是起點。
new七橋 02

尤拉將原本的地圖簡化成拓樸學上等價的圖示,用A, B, C, D四個點表示河川的南北兩岸以及兩座小島。從圖中可以發現,這個圖形的奇數點有4個,依照以上的原理,發現並不滿足尤拉圖的原則,因此沒有任何走法可以通過每個線段卻不重複。
new七橋 03

 

 

延伸問題
有沒有辦法畫出含有奇數個奇數點的圖形?為什麼? 

 

先不管是否能一筆畫通過,有沒有辦法畫出含有奇數個奇數點的圖形呢?我們先從兩個點開始,兩個點中間有兩條線相連時,兩個節點都會是偶數點。讓我們再加一條線試試看,兩個點都變成了奇數點。由此可知,每加上一條線,兩側的端點,都會改變奇偶性。因此有其中一個節點是奇數點的話,一定會有另外一個節點也是奇數點,因此在圖形中奇數點是無法單獨存在的。


new七橋 05 new七橋 04

 

參考資料

蔡承志(譯)(2014)。為什麼公車一次來3班?:生活中隱藏的81個數學謎題(原作者:R. Eastaway & J. Wyndham)。台北市:臉譜出版。(原著出版年:1998)

 

製作
盧楷文

 

指導老師
朱慶琪