哥尼斯堡七橋問題

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

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

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