[數學]七橋問題

[數學]七橋問題

J+W 於 星期三 四月 20, 2005 8:27 pm


七橋問題
  
現今的加媢蝞瘞ョA舊稱哥尼斯堡,是一座歷史名城。
哥城景致迷人,碧波蕩漾的普累格河,橫貫其境。在河的中心有一座美麗的小島。普河的兩條支流,環繞其旁彙成大河,把全城分爲下圖所示的四個區域;島區(A),東區(B),南區(C)和北區(D)。有七座橋橫跨普累格河及其支流,其中五座把河岸和河心島連接起來,這一別致的橋群,古往今來,吸引了萓h的遊人來此散步!
左鍵: 點擊縮放; 右鍵: 觀看原圖
早在18世紀以前,當地的居民便熱衷於以下有趣的問題:能不能設計一次散步,使得七座橋中的每一座都走過一次,而且只走過一次?這便是著名的哥尼斯堡七橋問題。
讀者如果有興趣,完全可以照樣子畫一張地圖,親自嘗試。不過,要告訴大家的是:想把所有的可能線路都試過一遍是極爲困難的!因爲各種可能的線路不下於五千種,要想一一試過,談何容易!
問題的魔力,竟然吸引了天才的歐拉(Euler,1707∼1783)
西元1736年,29歲的歐拉向聖彼得堡科學院遞交了一份題爲《哥尼斯堡的七座橋》的論文,論文的開頭是這樣寫的:“討論長短大小的幾何學分支,一直被人們熱心地研究著,但是還有一個至今幾乎完全沒有探索過的分支;萊布尼茲最先提起過它,稱之‘位置的幾何學’。這個幾何學分支討論只與位置有關的關係,研究位置的性質,它不去考慮長短大小,也不牽涉到量的計算,但是至今未有過令人滿意的定義,來刻劃這門位置幾何學的課題和方法,……”
接著,歐拉運用他那僂籅瘍傽咩犍屆A如同下圖,把哥尼斯堡七橋問題變爲讀者所熟悉的,簡單的幾何圖形的“一筆畫”問題:即能否筆不離紙,一筆畫但又不重復地畫完以下的圖形?
讀者不難發現:右圖中的點A、B、C、D,相當於七橋問題中的四塊區域;而圖中的弧線,則相當於連接各區域的橋。
聰明的歐拉,正是在上述基礎上,經過潛心研究,確立了著名的“一筆畫原理”,從而成功地解決了哥尼斯堡七橋問題。不過,要弄清歐拉的特有思路,我們還得從“網B絡”的連通性講起。
所謂網路,是指某些由點和線組成的圖形,網路中的線弧都有兩個端點,而且互不相交。如果一個網路中的任意兩點,都可以找到網路中的某條弧線,把它們連接起來,那麽,這樣的網路就稱爲連通的。連通的網路簡稱脈絡。
顯然,上面的三個圖中,圖Ⅰ不是網路,因爲它僅有的一條弧線只有一個端點;圖Ⅱ也不是網路,因爲它中間的兩條弧線相交,而交點卻非頂點;圖Ⅲ雖是網路,但卻不是連通的。而七橋問題的圖形,則不僅是網路,而且是脈絡!
網路的點如果有奇數條的弧線交彙於它,這樣的點稱爲奇點。反之,稱爲偶點。
歐拉注意到:對於一個可以“一筆畫”畫出的網路,首先必須是連通的;其次,對於網路中的某個點,如果不是起筆點或停筆點,那麽,交彙於這樣點的弧線必定成雙成對,即這樣的點必定是偶點!
上述分析表明:網路中的奇點,只能作爲起筆點或停筆點。然而,一個可以一筆畫畫成的圖形,其起筆點與停筆點的個數,要麽爲0,要麽爲2。於是,歐拉得出了以下著名的“一筆畫原理”:
“網路能一筆畫畫成必須是連通的,而且奇點個數或爲0,或爲2。
當奇點個數爲0時,全部弧線可以排成閉路。”
現在讀者看到,七橋問題的奇點個數爲4。(見上圖)。因而,要找到一條經過七座橋,但每座橋只走一次的路線是不可能的!
下圖畫的兩隻動物世界的龐然大物,都可以用一筆畫完成。它們的奇點個數分別爲0和2。
需要順便提到的是:既然可由一筆畫畫成的脈絡,其奇點個數應不多於兩個,那麽,兩筆劃或多筆劃能夠畫成的脈絡,其奇點個數應有怎樣的限制呢?我想,聰明的讀者完全能回答這個問題。倒是反過來的提問需要認真思考一番:即若一個連通網路的奇點個數爲0或2,是不是一定可以用一筆畫畫成?結論是肯定的!並且有:“含有2n(n>0)個奇點的脈絡,需要n筆劃畫成。

原文網址:

http://zhjyx.hfjy.net.cn/Resource/Book/Edu/SZJY/TS007051/0001_ts007051.htm

相關網頁:
http://www.bud.org.tw/Winnie/mathnoodle12.htm
http://www.edp.ust.hk/math/history/8/8_12.htm
http://www.hkame.org.hk/bookmark2005/bkmk-3.html

更詳盡的解說

http://www.math.tku.edu.tw/mathhall/mathinfo/lwymath/Konigsberg.htm

http://xserve.math.nctu.edu.tw/people/cpai/carnival/bridge/3.htm

J+W
版 主
版 主
 
文章: 2165
註冊時間: 2003-12-30






數學故事