哥尼斯堡七橋問題

一、 七橋漫步

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

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

這一別致的橋群，引來了眾多的游人，同時還引發了數學史上一項重要的研究。

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

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

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

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

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

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

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

于是一座儀態萬千的格尼斯堡古城在歐拉筆下就變成了一個結構簡單是幾何圖形。

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

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

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

歐拉當時發表這一結果時，震驚了當時的數學界。

三、引申與推廣

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

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

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