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

《小三奧數(shù) 格斯尼堡七橋問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

2、化為一個(gè)幾何圖形（如下圖）能否一筆畫出的問題了.那么，什么叫一筆畫？什么樣的圖可以一筆畫出？歐拉又是如何徹底證明七橋問題的不可能性呢？下面，我們就來介紹這一方面的簡(jiǎn)單知識(shí)。　　數(shù)學(xué)中，我們把由有限個(gè)點(diǎn)和連接這些點(diǎn)的線（線段或?。┧M成的圖形叫做圖（如圖（a））；圖中的點(diǎn)叫做圖的結(jié)點(diǎn)；連接兩結(jié)點(diǎn)的線叫做圖的邊.如圖（b）中，有三個(gè)結(jié)點(diǎn)：E、F、G，四條邊：線段EG、FG以及連接E、F的兩段弧.從圖（a）、（b）中可以看出，任意兩點(diǎn)之間都有一條通路（即可以從其中一點(diǎn)出發(fā)，沿著圖的邊走到另一點(diǎn)，如A到I的通路為A→H→I或A→D→I…），這樣的圖，我們稱為連通圖；而下圖中（c）的一些結(jié)

3、點(diǎn)之間卻不存在通路（如M與N），像這樣的圖就不是連通圖?！　∷^圖的一筆畫，指的就是：從圖的一點(diǎn)出發(fā)，筆不離紙，遍歷每條邊恰好一次，即每條邊都只畫一次，不準(zhǔn)重復(fù).從上圖中容易看出：能一筆畫出的圖首先必須是連通圖.但是否所有的連通圖都可以一筆畫出呢？下面，我們就來探求解決這個(gè)問題的方法?！　榱藬⑹龅姆奖?，我們把與奇數(shù)條邊相連的結(jié)點(diǎn)叫做奇點(diǎn)，把與偶數(shù)條邊相連的點(diǎn)稱為偶點(diǎn).如上圖（a）中的八個(gè)結(jié)點(diǎn)全是奇點(diǎn)，上圖（b）中E、F為奇點(diǎn)，G為偶點(diǎn)?！　∪菀字?，上圖（b）可以一筆畫出，即從奇點(diǎn)E出發(fā)，沿箭頭所指方向，經(jīng)過F、G、E，最后到達(dá)奇點(diǎn)F；同理，從奇點(diǎn)F出發(fā)也可以一筆畫出，最后到達(dá)

4、奇點(diǎn)E.而從偶點(diǎn)G出發(fā)，卻不能一筆畫出.這是為什么呢？　事實(shí)上，這并不是偶然現(xiàn)象.假定某個(gè)圖可以一筆畫成，且它的結(jié)點(diǎn)X既不是起點(diǎn)，也不是終點(diǎn)，而是中間點(diǎn)，那么X一定是一個(gè)偶點(diǎn).這是因?yàn)闊o論何時(shí)通過一條邊到達(dá)X，由于不能重復(fù)，必須從另一條邊離開X.這樣與X連結(jié)的邊一定成對(duì)出現(xiàn)，所以X必為偶點(diǎn)，也就是說：奇點(diǎn)在一筆畫中只能作為起或終點(diǎn).由此可以看出，在一個(gè)可以一筆畫出的圖中，奇點(diǎn)的個(gè)數(shù)最多只有兩個(gè)?！　≡谄邩騿栴}的圖中有四個(gè)奇點(diǎn)，因此，歐拉斷言：這個(gè)圖無法一筆畫出，也即游人不可能不重復(fù)地一次走遍七座橋.更進(jìn)一步地，歐拉在解決七橋問題的同時(shí)徹底地解決了一筆畫的問題，給出了下面的歐拉定理

5、：　?、俜彩怯膳键c(diǎn)組成的連通圖，一定可以一筆畫成；畫時(shí)可以任一偶點(diǎn)為起點(diǎn)，最后一定能以這個(gè)點(diǎn)為終點(diǎn)畫完此圖。　?、诜彩侵挥袃蓚€(gè)奇點(diǎn)（其余均為偶點(diǎn)）的連通圖，一定可以一筆畫完；畫時(shí)必須以一個(gè)奇點(diǎn)為起點(diǎn)，另一個(gè)奇點(diǎn)為終點(diǎn)。　?、燮渌闆r的圖，都不能一筆畫出?！　∠旅嫖覀兙蛠硌芯恳还P畫問題的具體應(yīng)用：例1觀察下面的圖形，說明哪些圖可以一筆畫完，哪些不能，為什么？對(duì)于可以一筆畫的圖形，指明畫法.　　注意：在上面能夠一筆畫出的圖中，畫法并不是惟一的.事實(shí)上，對(duì)于有兩個(gè)奇點(diǎn)的圖來說，任一個(gè)奇點(diǎn)都可以作為起點(diǎn)，以另一個(gè)奇點(diǎn)作為終點(diǎn)；對(duì)于沒有奇點(diǎn)的圖來說，任一個(gè)偶點(diǎn)都可以作為起點(diǎn)，最后仍以這點(diǎn)作

6、為終點(diǎn)。例2下圖是國際奧委會(huì)的會(huì)標(biāo)，你能一筆把它畫出來嗎？一個(gè)圖能否一筆畫出，關(guān)鍵取決于這個(gè)圖中奇點(diǎn)的個(gè)數(shù).通過觀察可以發(fā)現(xiàn)，上圖中所有的結(jié)點(diǎn)都是偶點(diǎn)，因此，這個(gè)圖可以一筆畫出.畫時(shí)可以任一結(jié)點(diǎn)作為起點(diǎn)。例3下圖是某地區(qū)所有街道的平面圖.甲、乙二人同時(shí)分別從A、B出發(fā)，以相同的速度走遍所有的街道，最后到達(dá)C.如果允許兩人在遵守規(guī)則的條件下可以選擇最短路徑的話，問兩人誰能最先到達(dá)C？例4下圖是某展覽廳的平面圖，它由五個(gè)展室組成，任兩展室之間都有門相通，整個(gè)展覽廳還有一個(gè)進(jìn)口和一個(gè)出口，問游人能否一次不重復(fù)地穿過所有的門，并且從入口進(jìn)，從出口出？注意：本題中，必須以A分別作為起點(diǎn)和終

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