七橋問題Seven Bridges Problem
著名古典數(shù)學(xué)問題之一.在哥尼斯堡的一個(gè)公園里,有七座橋?qū)⑵绽赘駹柡又袃蓚€(gè)島及島與河岸連接起來(如圖).問是否可能從這四塊陸地中任一塊出發(fā),恰好通過每座橋一次,再回到起點(diǎn)?歐勒于1736年研究并解決了此問題,他把問題歸結(jié)為如下右圖的“一筆畫”問題,證明上述走法是不可能的.
有關(guān)圖論研究的熱點(diǎn)問題.18世紀(jì)初普魯士的柯尼斯堡,普雷格爾河流經(jīng)此鎮(zhèn),奈發(fā)夫島位于河中,共有7座橋橫跨河上,把全鎮(zhèn)連接起來.當(dāng)?shù)鼐用駸嶂杂谝粋€(gè)難題：是否存在一條路線,可不重復(fù)地走遍七座橋.這就是柯尼斯堡七橋問題.L.歐拉用點(diǎn)表示島和陸地,兩點(diǎn)之間的連線表示連接它們的橋,將河流、小島和橋簡化為一個(gè)網(wǎng)絡(luò),把七橋問題化成判斷連通網(wǎng)絡(luò)能否一筆畫的問題.他不僅解決了此問題,且給出了連通網(wǎng)絡(luò)可一筆畫的充要條件是它們是連通的,且奇頂點(diǎn)(通過此點(diǎn)弧的條數(shù)是奇數(shù))的個(gè)數(shù)為0或2.
當(dāng)Euler在1736年訪問Konigsberg,Prussia(now Kaliningrad Russia)時(shí),他發(fā)現(xiàn)當(dāng)?shù)氐氖忻裾龔氖乱豁?xiàng)非常有趣的消遣活動(dòng).Konigsberg城中有一條名叫Pregel的河流橫經(jīng)其中,這項(xiàng)有趣的消遣活動(dòng)是在星期六作一次走過所有七座橋的散步,每座橋只能經(jīng)過一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn).
Euler把每一塊陸地考慮成一個(gè)點(diǎn),連接兩塊陸地的橋以線表示.
后來推論出此種走法是不可能的.他的論點(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ù)無法完成.
歐拉的這個(gè)考慮非常重要,也非常巧妙,它正表明了數(shù)學(xué)家處理實(shí)際問題的獨(dú)特之處——把一個(gè)實(shí)際問題抽象成合適的“數(shù)學(xué)模型”.這種研究方法就是“數(shù)學(xué)模型方法”.這并不需要運(yùn)用多么深?yuàn)W的理論,但想到這一點(diǎn),卻是解決難題的關(guān)鍵.
接下來,歐拉運(yùn)用網(wǎng)絡(luò)中的一筆畫定理為判斷準(zhǔn)則,很快地就判斷出要一次不重復(fù)走遍哥尼斯堡的7座橋是不可能的.也就是說,多少年來,人們費(fèi)腦費(fèi)力尋找的那種不重復(fù)的路線,根本就不存在.一個(gè)曾難住了那么多人的問題,竟是這么一個(gè)出人意料的答案!
1736年,歐拉在交給彼得堡科學(xué)院的《哥尼斯堡7座橋》的論文報(bào)告中,闡述了他的解題方法.他的巧解,為后來的數(shù)學(xué)新分支——拓?fù)鋵W(xué)的建立奠定了基礎(chǔ).
七橋問題和歐拉定理.歐拉通過對(duì)七橋問題的研究,不僅圓滿地回答了哥尼斯堡居民提出的問題,而且得到并證明了更為廣泛的有關(guān)一筆畫的三條結(jié)論,人們通常稱之為歐拉定理.對(duì)于一個(gè)連通圖,通常把從某結(jié)點(diǎn)出發(fā)一筆畫成所經(jīng)過的路線叫做歐拉路.人們又通常把一筆畫成回到出發(fā)點(diǎn)的歐拉路叫做歐拉回路.具有歐拉回路的圖叫做歐拉圖.
此題被人教版小學(xué)數(shù)學(xué)第十二冊書收錄.在95頁.