七橋問題 Seven Bridges Problem

七橋問題 Seven Bridges Problem

  這個問題是卡羅·戈特利布·依勒(Carl Gottlieb Ehler, 1685–1753)發現的,他是一位數學家,同時也是哥德尼斯堡(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)

 

製作
盧楷文

 

指導老師
朱慶琪