哥尼斯堡七橋問題

1、世界數(shù)學名題哥尼斯堡七橋問題18世紀時，歐洲有一個風景秀麗的小城哥尼斯堡(今俄羅斯加里寧格勒)，那里的普萊格爾河上有七座橋。將河中的兩個島和河岸連結，城中的居民經(jīng)常沿河過橋散步，于是有人提出了一個問題：一個人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點？大家都試圖找出問題的答案，但是誰也解決不了這個問題。 這就是哥尼斯堡七橋問題，一個著名的圖論問題。1727年在歐拉20歲的時候，被俄國邀請請去圣彼得堡（原列寧格勒）的科學院做研究。他的德國朋友告訴了他這個曾經(jīng)令許多人困惑的問題。歐拉并沒有跑到哥尼斯堡去走走。他把這個難題化成了這樣的問題來看：把河岸和小島縮成一點，橋化為邊，

2、于是“七橋問題”就轉化成下圖中所畫圖形的一筆畫問題了， 這個圖如果能夠一筆畫成的話，對應的“七橋問題”也就解決了。 歐拉的這個考慮非常重要，也非常巧妙，它正表明了數(shù)學家處理實際問題的獨特之處把一個實際問題抽象成合適的“數(shù)學模型”。這種研究方法就是“數(shù)學模型方法”。這并不需要運用多么深奧的理論，但想到這一點，卻是解決難題的關鍵。接下來，歐拉運用圖中的一筆畫定理為判斷準則，很快地就判斷出要一次不重復走遍哥尼斯堡的7座橋是不可能的。也就是說，多少年來，人們費腦費力尋找的那種不重復的路線，根本就不存在。一個曾難住了那么多人的問題，竟是這么一個出人意料的答案！經(jīng)過研究，歐拉發(fā)現(xiàn)了一筆畫的規(guī)律。

3、他認為，能一筆畫的圖形必須是連通圖。連通圖就指一個圖形各部分總是有邊相連的，這道題中的圖就是連通圖。但是，不是所有的連通圖都可以一筆畫的。能否一筆畫是由圖的奇、偶點的數(shù)目來決定的。那么什么叫奇、偶點呢？與奇數(shù)（單數(shù)）條邊相連的點叫做奇點；與偶數(shù)（雙數(shù)）條邊相連的點叫做偶點。如下圖中的、為奇點，、為偶點。1凡是由偶點組成的連通圖，一定可以一筆畫成。畫時可以把任一偶點為起點，最后一定能以這個點為終點畫完此圖。例如下圖都是偶點，畫的線路可以是：2凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫成。畫時必須把一個奇點為起點，另一個奇點終點。例如下圖的線路是：3其他情況的圖都不能一筆畫出。歐拉后來推論出此種走法是不可能的。他的論點是這樣的，除了起點以外，每一次當一個人由一座橋進入一塊陸地（或點）時，他（或她）同時也由另一座橋離開此點。所以每行經(jīng)一點時，計算兩座橋（或線），從起點離開的線與最后回到始點的線亦計算兩座橋，因此每一個陸地與其他陸地連接的橋數(shù)必為偶數(shù)七橋所成之圖形中，沒有一點含有偶數(shù)條數(shù)，因此上述的任務無法完成.歐拉通過對七橋問題的研究，不僅圓滿地回答了居民提出的問題，而且得到并證明了更為廣泛的有關一筆畫的三條結論，人們通常稱之為歐拉定理。對于一個連通圖，通常