資源描述：
《小三奧數(shù) 格斯尼堡七橋問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、第二講從哥尼斯堡七橋問題談起 故事發(fā)生在18世紀(jì)的哥尼斯堡城.流經(jīng)那里的一條河中有兩個小島，還有七座橋把這兩個小島與河岸聯(lián)系起來，那里風(fēng)景優(yōu)美，游人眾多.在這美麗的地方，人們議論著一個有趣的問題：一個游人怎樣才能不重復(fù)地一次走遍七座橋，最后又回到出發(fā)點呢？ 對于這個貌似簡單的問題，許多人躍躍欲試，但都沒有獲得成功.直到1836年，瑞士著名的數(shù)學(xué)家歐拉才證明了這個問題的不可能性?！ W拉解決這個問題的方法非常巧妙.他認(rèn)為：人們關(guān)心的只是一次不重復(fù)地走遍這七座橋，而并不關(guān)心橋的長短和島的大小，因此，島和岸都可以看作一個點，而橋則可以看成是連接這些點的一條線.這樣，一個實際問題就轉(zhuǎn)
2、化為一個幾何圖形（如下圖）能否一筆畫出的問題了.那么，什么叫一筆畫？什么樣的圖可以一筆畫出？歐拉又是如何徹底證明七橋問題的不可能性呢？下面，我們就來介紹這一方面的簡單知識?！ ?shù)學(xué)中，我們把由有限個點和連接這些點的線（線段或?。┧M成的圖形叫做圖（如圖（a））；圖中的點叫做圖的結(jié)點；連接兩結(jié)點的線叫做圖的邊.如圖（b）中，有三個結(jié)點：E、F、G，四條邊：線段EG、FG以及連接E、F的兩段弧.從圖（a）、（b）中可以看出，任意兩點之間都有一條通路（即可以從其中一點出發(fā)，沿著圖的邊走到另一點，如A到I的通路為A→H→I或A→D→I…），這樣的圖，我們稱為連通圖；而下圖中（c）的一些結(jié)
3、點之間卻不存在通路（如M與N），像這樣的圖就不是連通圖?！ ∷^圖的一筆畫，指的就是：從圖的一點出發(fā)，筆不離紙，遍歷每條邊恰好一次，即每條邊都只畫一次，不準(zhǔn)重復(fù).從上圖中容易看出：能一筆畫出的圖首先必須是連通圖.但是否所有的連通圖都可以一筆畫出呢？下面，我們就來探求解決這個問題的方法?！ 榱藬⑹龅姆奖?，我們把與奇數(shù)條邊相連的結(jié)點叫做奇點，把與偶數(shù)條邊相連的點稱為偶點.如上圖（a）中的八個結(jié)點全是奇點，上圖（b）中E、F為奇點，G為偶點。 容易知道，上圖（b）可以一筆畫出，即從奇點E出發(fā)，沿箭頭所指方向，經(jīng)過F、G、E，最后到達奇點F；同理，從奇點F出發(fā)也可以一筆畫出，最后到達
4、奇點E.而從偶點G出發(fā)，卻不能一筆畫出.這是為什么呢？ 事實上，這并不是偶然現(xiàn)象.假定某個圖可以一筆畫成，且它的結(jié)點X既不是起點，也不是終點，而是中間點，那么X一定是一個偶點.這是因為無論何時通過一條邊到達X，由于不能重復(fù)，必須從另一條邊離開X.這樣與X連結(jié)的邊一定成對出現(xiàn)，所以X必為偶點，也就是說：奇點在一筆畫中只能作為起或終點.由此可以看出，在一個可以一筆畫出的圖中，奇點的個數(shù)最多只有兩個?！ ≡谄邩騿栴}的圖中有四個奇點，因此，歐拉斷言：這個圖無法一筆畫出，也即游人不可能不重復(fù)地一次走遍七座橋.更進一步地，歐拉在解決七橋問題的同時徹底地解決了一筆畫的問題，給出了下面的歐拉定理
5、： ①凡是由偶點組成的連通圖，一定可以一筆畫成；畫時可以任一偶點為起點，最后一定能以這個點為終點畫完此圖?！ 、诜彩侵挥袃蓚€奇點（其余均為偶點）的連通圖，一定可以一筆畫完；畫時必須以一個奇點為起點，另一個奇點為終點。 ?、燮渌闆r的圖，都不能一筆畫出?！ ∠旅嫖覀兙蛠硌芯恳还P畫問題的具體應(yīng)用：例1觀察下面的圖形，說明哪些圖可以一筆畫完，哪些不能，為什么？對于可以一筆畫的圖形，指明畫法. 注意：在上面能夠一筆畫出的圖中，畫法并不是惟一的.事實上，對于有兩個奇點的圖來說，任一個奇點都可以作為起點，以另一個奇點作為終點；對于沒有奇點的圖來說，任一個偶點都可以作為起點，最后仍以這點作
6、為終點。例2下圖是國際奧委會的會標(biāo)，你能一筆把它畫出來嗎？一個圖能否一筆畫出，關(guān)鍵取決于這個圖中奇點的個數(shù).通過觀察可以發(fā)現(xiàn)，上圖中所有的結(jié)點都是偶點，因此，這個圖可以一筆畫出.畫時可以任一結(jié)點作為起點。例3下圖是某地區(qū)所有街道的平面圖.甲、乙二人同時分別從A、B出發(fā)，以相同的速度走遍所有的街道，最后到達C.如果允許兩人在遵守規(guī)則的條件下可以選擇最短路徑的話，問兩人誰能最先到達C？例4下圖是某展覽廳的平面圖，它由五個展室組成，任兩展室之間都有門相通，整個展覽廳還有一個進口和一個出口，問游人能否一次不重復(fù)地穿過所有的門，并且從入口進，從出口出？注意：本題中，必須以A分別作為起點和終
7、點.這就要求圖中必須沒有奇點，否則，若有兩個奇點，雖能一筆畫出，但與從入口入、出口出（即游人的出發(fā)和終止點都在展廳外）有矛盾，其他有多個奇點的情況則根本不可能一筆畫出。另外，通過前面的學(xué)習(xí)，大家已經(jīng)知道：一個圖如果能夠一筆畫出，則畫的方法不止一種，但各種方法大同小異.因此，本書中，一筆畫的問題，一般我們只給出一種畫法。例5一張紙上畫有如下圖所示的圖，你能否用剪刀一次連續(xù)剪下圖中的三個正方形和兩個三角形？例6下圖是一個公園的平面圖.要使游客走遍每條路而不重復(fù)，問出入口應(yīng)設(shè)在哪里？
