第七講哥尼斯堡七橋問題

1、1第七講第七講 若干若干數(shù)學(xué)問題中的數(shù)學(xué)問題中的 數(shù)學(xué)文化數(shù)學(xué)文化哥尼斯堡哥尼斯堡七橋問題七橋問題 2016秋季數(shù)學(xué)教育碩士課程秋季數(shù)學(xué)教育碩士課程2016年年11月月172一、哥尼斯堡七橋問題一、哥尼斯堡七橋問題 現(xiàn)今俄羅斯的加里寧格勒是一座歷史名城，18世紀(jì)時稱為哥尼斯堡。當(dāng)時那里是東普魯士的首府，曾經(jīng)誕生和培育過許多偉大的人物。著名的哲學(xué)家、古典唯心主義的創(chuàng)始人康德，一直生活在那里。德國著名的數(shù)學(xué)家希爾伯特，也出生于此地。3 哥尼斯堡風(fēng)景秀美，碧波蕩漾的普累格爾河穿過該城；河中心有一座美麗的小島，島上商業(yè)繁榮，普累格爾河及其兩條支流把包含島在內(nèi)的全城分為四個區(qū)域，有七座橋橫跨普累格爾河及

2、其支流，連接了這四個區(qū)域。這一別致的橋群，古往今來，吸引著眾多的游人。4 5 當(dāng)?shù)氐木用裨?jīng)熱衷于下面一個有趣的問題：能不能找到一條路線了，使得散步時不重復(fù)地走遍這七座橋。 尋找滿意路線的問題引起了許多人的興趣，但結(jié)果卻沒有一個人能夠做到。不是少走了一座橋，就是重復(fù)走了一座橋。6 多次嘗試失敗后，有人寫信求教于當(dāng)時的數(shù)學(xué)家歐拉。歐拉在親自觀察了哥尼斯堡七橋后，認(rèn)真思考走法，但始終沒能成功，于是他懷疑七橋問題是不是原本就無解呢？這位年輕的瑞士數(shù)學(xué)家獨(dú)具慧眼，看出了這個似乎是趣味幾何問題的本質(zhì)。7 1736年，29歲的歐拉向圣彼得堡科學(xué)院遞交了哥尼斯堡的七座橋的論文，在解答問題的同時，開創(chuàng)了數(shù)學(xué)的

3、一個新的分支圖論。 歐拉通過對七橋問題的研究，不僅圓滿地回答了哥尼斯堡居民提出的問題，而且得到并證明了更為廣泛的有關(guān)一筆畫的三條結(jié)論，人們通常稱之為“歐拉定理”。8 在論文中，歐拉將七橋問題抽象出來，把每一塊陸地考慮成一個點(diǎn)，連接兩塊陸地的橋以線表示。并由此得到了如圖一樣的幾何圖形。 若我們分別用A、B、C、D四個點(diǎn)表示為哥尼斯堡的四個區(qū)域。這樣著名的“七橋問題”便轉(zhuǎn)化為是否能夠一筆不重復(fù)的畫出過此七條線的問題了。9 1011 理論上需要解決的問題是：找到“一個圖形是一筆畫”的充分必要條件，并對是一筆畫的圖形給出一筆畫的方法。 12 歐拉把圖形上的點(diǎn)分成兩類：如果以某點(diǎn)為端點(diǎn)的線有偶數(shù)條，就稱

4、此點(diǎn)為偶結(jié)點(diǎn)，如果以某點(diǎn)為端點(diǎn)的線有奇數(shù)條，就稱此點(diǎn)為奇結(jié)點(diǎn)。13 要想不重復(fù)地一筆畫出某圖形，除去起始點(diǎn)和終止點(diǎn)兩個點(diǎn)外，其余每個點(diǎn)，如果畫進(jìn)去一條線，就一定要畫出來一條線，從而都必須是偶結(jié)點(diǎn)。 于是“一筆畫”的必要條件是“圖形中的奇結(jié)點(diǎn)的個數(shù)為0或2”（當(dāng)起始點(diǎn)與終止點(diǎn)重合時，奇結(jié)點(diǎn)個數(shù)為0）。14 反之也對：如果圖形中的奇結(jié)點(diǎn)個數(shù)為0或2時，就一定能完成一筆畫。當(dāng)圖形中有兩個奇結(jié)點(diǎn)時，以其中一個為起始點(diǎn)，另一個為終止點(diǎn)，就能完成一筆畫。當(dāng)圖形中沒有奇結(jié)點(diǎn)時，從任何一個點(diǎn)起始都可以完成一筆畫（不會出現(xiàn)圖形中只有一個奇結(jié)點(diǎn)的情況，因?yàn)槊織l線都有兩個端點(diǎn)）。15 這樣，歐拉就得出了圖形是一筆畫

5、的充分必要條件：圖形中的奇結(jié)點(diǎn)個數(shù)為0或2。 再看哥尼斯堡七橋問題，圖形中有四個奇結(jié)點(diǎn)，因此該圖形不是一筆畫，難怪所有的嘗試都失敗了。16二、一筆畫 凡是由偶點(diǎn)組成的連通圖，一定可以一筆畫成。畫時可以把任一偶點(diǎn)為起點(diǎn)，最后一定能以這個點(diǎn)為終點(diǎn)畫完此圖。凡是只有兩個奇點(diǎn)的連通圖（其余都為偶點(diǎn)），一定可以一筆畫成。畫時必須把一個奇點(diǎn)為起點(diǎn)，另一個奇點(diǎn)為終點(diǎn)。其他情況的圖都不能一筆畫出。(奇點(diǎn)數(shù)除以二便可算出此圖需幾筆畫成。)1718二、一筆畫 姜伯駒先生的一筆畫和郵遞路線問題： 最短郵遞路線問題19三、拓?fù)鋵W(xué) 在上面的問題中，我們只研究圖形各部分位置的相對關(guān)系，而不考慮它們的大小和角度。萊布尼茨和歐拉為這種“位置幾何學(xué)”奠定了最初的基礎(chǔ)。龐加萊于19世紀(jì)末將其發(fā)展為一個系統(tǒng)的數(shù)學(xué)分支拓?fù)鋵W(xué)。 有人把拓?fù)鋵W(xué)說成是“橡皮幾何學(xué)”。20三、拓?fù)鋵W(xué) 平面上的歐拉公式：V+F-E=1。 空