哥尼斯堡七橋問題

一、 七橋漫步

格尼斯堡城是由條頓騎士團在1308年建立，曾作為東普魯士的首府。第二次世界大戰(zhàn)后，成為前蘇聯(lián)最大的海軍基地。現(xiàn)在的格尼斯堡位于立陶宛和波蘭之間。在第二次世界大戰(zhàn)時，法軍經(jīng)這里入侵波蘭。后來蘇軍也從這里打進德國，所以格尼斯堡是一座名城。同時這里也誕生過許多偉大人物，其中包括18世紀著名的唯心主義哲學(xué)家康德和19世紀的大數(shù)學(xué)家希爾伯特。

但是，最早給這座城市帶來聲譽的橫跨布列格爾河，把格尼斯堡連成一體的七座橋梁。

這一別致的橋群，引來了眾多的游人，同時還引發(fā)了數(shù)學(xué)史上一項重要的研究。

一天又一天，這七座橋上走過了無數(shù)的行人，腳下的七橋觸發(fā)了人們的靈感，一個有趣的問題在民間傳開“能否在一次散步中每座橋都走一次，而且只能走一次，最后又回到原來的出發(fā)點？”這個問題看似簡單，人人都樂意去測試一下自己的智力，可是把全城人的智力加在一起，也沒有找到一條合適的路線。這個問題傳開以后，許多歐洲有學(xué)問的人也參與思考，同樣是一籌莫展。就這樣，格尼斯堡這個“七橋問題”給人們提供了豐富的樂趣和數(shù)學(xué)興味，因而使得這座波羅的海的海濱古城聞名遐邇。

二、歐拉與格尼斯堡七橋問題

1735年有幾名大學(xué)生寫信給當(dāng)時正在俄國彼得堡科學(xué)院任職的天才數(shù)學(xué)家歐拉，請他幫助解決。歐拉并未輕視生活中的小問題，他似乎看到了其中隱藏某種新的數(shù)學(xué)方法。

事實上，要走遍七座橋的所有走法有7！=5040種，要想一一試驗是不可能的，只能另找一種新方法。歐拉依靠他深厚的數(shù)學(xué)功底，運用嫻熟的變換技巧，經(jīng)過一年的研究，于1936年，29歲的歐拉向彼得堡科學(xué)院提交了一份為《格尼斯堡七橋》的論文，圓滿的解決了這一問題。歐拉不僅解決了七橋問題，而且他提出飛思想導(dǎo)致了一門新的數(shù)學(xué)分支——“圖論”的誕生。

歐拉是如何解決七橋問題的？又是如何證明要想一次走過七座橋是不可能的呢？歐拉的方法十分巧妙：

（1）不考慮4個地區(qū)的大小、形狀，不妨將它們看成是鏈接橋梁的4個點；

（2）不考慮橋梁的曲直、長短，不妨將它們看成連接4個點的7條線。

于是一座儀態(tài)萬千的格尼斯堡古城在歐拉筆下就變成了一個結(jié)構(gòu)簡單是幾何圖形。

于是七橋問題就變成了用筆不重復(fù)的（筆不離開紙面）畫出這個幾何圖形的問題，即“一筆畫”問題。如果可以畫出來，則必有一個起點和一個終點，如果這兩點不重合，則與起點或終點相交的線必為奇數(shù)條（稱為奇點），如果起點與終點重合，則與之相交的線必為偶數(shù)條（稱為偶點），而除了起點與終點外，其他點也必為偶點。據(jù)以上分析，如果一個圖形可以一筆畫出來，則必須滿足兩個條件：

（1）圖形必須是連通的，即任一點通過一些線一定能達到其他任意點。（2）圖中的奇點數(shù)只能是0或2.

回頭來看七橋問題，4個點全為奇點，故七橋問題無解。

歐拉當(dāng)時發(fā)表這一結(jié)果時，震驚了當(dāng)時的數(shù)學(xué)界。

三、引申與推廣

歐拉解決七橋問題的方法并不深奧，但他的新穎之處不僅在于另辟蹊徑的解題思路，更在于“一筆畫”問題雖然是一個幾何問題，可是這種幾何問題卻是歐幾里得幾何里沒有研究過的。

在“一筆畫”問題里，長度、角度、面積、體積都沒有了，四大塊陸地變成了四個點；連線的長短曲直、交點的方位都無關(guān)緊要，要緊的只是點線之間的相關(guān)位置或相互連接的情況，如下兩圖都沒有改變七橋問題“一筆畫”的性質(zhì)。

后來布勒格爾河上又架起第八座橋來——鐵路橋，這又使人們想起了那有趣的問題。雖然一次不重復(fù)走遍七座橋不可能，那八座橋呢？從圖中可以已看出，“奇點”只有兩個（D、C），所以可以一次不重復(fù)走遍八座橋。