小三奧數(shù)格斯尼堡七橋問(wèn)題

《小三奧數(shù)格斯尼堡七橋問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第二講從哥尼斯堡七橋問(wèn)題談起　　故事發(fā)生在18世紀(jì)的哥尼斯堡城.流經(jīng)那里的一條河中有兩個(gè)小島，還有七座橋把這兩個(gè)小島與河岸聯(lián)系起來(lái)，那里風(fēng)景優(yōu)美，游人眾多.在這美麗的地方，人們議論著一個(gè)有趣的問(wèn)題：一個(gè)游人怎樣才能不重復(fù)地一次走遍七座橋，最后又回到出發(fā)點(diǎn)呢？　　對(duì)于這個(gè)貌似簡(jiǎn)單的問(wèn)題，許多人躍躍欲試，但都沒(méi)有獲得成功.直到1836年，瑞士著名的數(shù)學(xué)家歐拉才證明了這個(gè)問(wèn)題的不可能性?！　W拉解決這個(gè)問(wèn)題的方法非常巧妙.他認(rèn)為：人們關(guān)心的只是一次不重復(fù)地走遍這七座橋，而并不關(guān)心橋的長(zhǎng)短和島的大小，因此，島和岸都

2、可以看作一個(gè)點(diǎn)，而橋則可以看成是連接這些點(diǎn)的一條線(xiàn).這樣，一個(gè)實(shí)際問(wèn)題就轉(zhuǎn)化為一個(gè)幾何圖形（如下圖）能否一筆畫(huà)出的問(wèn)題了.那么，什么叫一筆畫(huà)？什么樣的圖可以一筆畫(huà)出？歐拉又是如何徹底證明七橋問(wèn)題的不可能性呢？下面，我們就來(lái)介紹這一方面的簡(jiǎn)單知識(shí)?！　?shù)學(xué)中，我們把由有限個(gè)點(diǎn)和連接這些點(diǎn)的線(xiàn)（線(xiàn)段或?。┧M成的圖形叫做圖（如圖（a））；圖中的點(diǎn)叫做圖的結(jié)點(diǎn)；連接兩結(jié)點(diǎn)的線(xiàn)叫做圖的邊.如圖（b）中，有三個(gè)結(jié)點(diǎn)：E、F、G，四條邊：線(xiàn)段EG、FG以及連接E、F的兩段弧.從圖（a）、（b）中可以看出，任意兩點(diǎn)之間都

3、有一條通路（即可以從其中一點(diǎn)出發(fā)，沿著圖的邊走到另一點(diǎn)，如A到I的通路為A→H→I或A→D→I…），這樣的圖，我們稱(chēng)為連通圖；而下圖中（c）的一些結(jié)點(diǎn)之間卻不存在通路（如M與N），像這樣的圖就不是連通圖。4/4　　所謂圖的一筆畫(huà)，指的就是：從圖的一點(diǎn)出發(fā)，筆不離紙，遍歷每條邊恰好一次，即每條邊都只畫(huà)一次，不準(zhǔn)重復(fù).從上圖中容易看出：能一筆畫(huà)出的圖首先必須是連通圖.但是否所有的連通圖都可以一筆畫(huà)出呢？下面，我們就來(lái)探求解決這個(gè)問(wèn)題的方法。　　為了敘述的方便，我們把與奇數(shù)條邊相連的結(jié)點(diǎn)叫做奇點(diǎn)，把與偶數(shù)條邊相連

4、的點(diǎn)稱(chēng)為偶點(diǎn).如上圖（a）中的八個(gè)結(jié)點(diǎn)全是奇點(diǎn)，上圖（b）中E、F為奇點(diǎn)，G為偶點(diǎn)。　　容易知道，上圖（b）可以一筆畫(huà)出，即從奇點(diǎn)E出發(fā)，沿箭頭所指方向，經(jīng)過(guò)F、G、E，最后到達(dá)奇點(diǎn)F；同理，從奇點(diǎn)F出發(fā)也可以一筆畫(huà)出，最后到達(dá)奇點(diǎn)E.而從偶點(diǎn)G出發(fā)，卻不能一筆畫(huà)出.這是為什么呢？　事實(shí)上，這并不是偶然現(xiàn)象.假定某個(gè)圖可以一筆畫(huà)成，且它的結(jié)點(diǎn)X既不是起點(diǎn)，也不是終點(diǎn)，而是中間點(diǎn)，那么X一定是一個(gè)偶點(diǎn).這是因?yàn)闊o(wú)論何時(shí)通過(guò)一條邊到達(dá)X，由于不能重復(fù)，必須從另一條邊離開(kāi)X.這樣與X連結(jié)的邊一定成對(duì)出現(xiàn)，所以X必

5、為偶點(diǎn)，也就是說(shuō)：奇點(diǎn)在一筆畫(huà)中只能作為起或終點(diǎn).由此可以看出，在一個(gè)可以一筆畫(huà)出的圖中，奇點(diǎn)的個(gè)數(shù)最多只有兩個(gè)?！　≡谄邩騿?wèn)題的圖中有四個(gè)奇點(diǎn)，因此，歐拉斷言：這個(gè)圖無(wú)法一筆畫(huà)出，也即游人不可能不重復(fù)地一次走遍七座橋.更進(jìn)一步地，歐拉在解決七橋問(wèn)題的同時(shí)徹底地解決了一筆畫(huà)的問(wèn)題，給出了下面的歐拉定理：　?、俜彩怯膳键c(diǎn)組成的連通圖，一定可以一筆畫(huà)成；畫(huà)時(shí)可以任一偶點(diǎn)為起點(diǎn)，最后一定能以這個(gè)點(diǎn)為終點(diǎn)畫(huà)完此圖?！　、诜彩侵挥袃蓚€(gè)奇點(diǎn)（其余均為偶點(diǎn)）的連通圖，一定可以一筆畫(huà)完；畫(huà)時(shí)必須以一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)

6、為終點(diǎn)?！　、燮渌闆r的圖，都不能一筆畫(huà)出。　　下面我們就來(lái)研究一筆畫(huà)問(wèn)題的具體應(yīng)用：例1觀(guān)察下面的圖形，說(shuō)明哪些圖可以一筆畫(huà)完，哪些不能，為什么？對(duì)于可以一筆畫(huà)的圖形，指明畫(huà)法.4/4　　注意：在上面能夠一筆畫(huà)出的圖中，畫(huà)法并不是惟一的.事實(shí)上，對(duì)于有兩個(gè)奇點(diǎn)的圖來(lái)說(shuō)，任一個(gè)奇點(diǎn)都可以作為起點(diǎn)，以另一個(gè)奇點(diǎn)作為終點(diǎn)；對(duì)于沒(méi)有奇點(diǎn)的圖來(lái)說(shuō)，任一個(gè)偶點(diǎn)都可以作為起點(diǎn)，最后仍以這點(diǎn)作為終點(diǎn)。例2下圖是國(guó)際奧委會(huì)的會(huì)標(biāo)，你能一筆把它畫(huà)出來(lái)嗎？一個(gè)圖能否一筆畫(huà)出，關(guān)鍵取決于這個(gè)圖中奇點(diǎn)的個(gè)數(shù).通過(guò)觀(guān)察可以發(fā)現(xiàn)，上圖

7、中所有的結(jié)點(diǎn)都是偶點(diǎn)，因此，這個(gè)圖可以一筆畫(huà)出.畫(huà)時(shí)可以任一結(jié)點(diǎn)作為起點(diǎn)。例3下圖是某地區(qū)所有街道的平面圖.甲、乙二人同時(shí)分別從A、B出發(fā)，以相同的速度走遍所有的街道，最后到達(dá)C.如果允許兩人在遵守規(guī)則的條件下可以選擇最短路徑的話(huà)，問(wèn)兩人誰(shuí)能最先到達(dá)C？例4下圖是某展覽廳的平面圖，它由五個(gè)展室組成，任兩展室之間都有門(mén)相通，整個(gè)展覽廳還有一個(gè)進(jìn)口和一個(gè)出口，問(wèn)游人能否一次不重復(fù)地穿過(guò)所有的門(mén)，并且從入口進(jìn)，從出口出？4/4注意：本題中，必須以A分別作為起點(diǎn)和終點(diǎn).這就要求圖中必須沒(méi)有奇點(diǎn)，否則，若有兩個(gè)奇點(diǎn)，

8、雖能一筆畫(huà)出，但與從入口入、出口出（即游人的出發(fā)和終止點(diǎn)都在展廳外）有矛盾，其他有多個(gè)奇點(diǎn)的情況則根本不可能一筆畫(huà)出。另外，通過(guò)前面的學(xué)習(xí)，大家已經(jīng)知道：一個(gè)圖如果能夠一筆畫(huà)出，則畫(huà)的方法不止一種，但各種方法大同小異.因此，本書(shū)中，一筆畫(huà)的問(wèn)題，一般我們只給出一種畫(huà)法。例5一張紙上畫(huà)有如下圖所示的圖，你能否用剪刀一次連續(xù)剪下圖中的三個(gè)正方形和兩個(gè)三角形？例6下圖是一個(gè)公園的平面圖.要使游客走遍每條路而不重復(fù)，問(wèn)出